4 ms·

The video is definitely worth watching, but that's an excellent summary, thank you. It seemed to me that there might be a trade-off (when selecting a square in

The video is definitely worth watching, but that's an excellent summary, thank you. It seemed to me that there might be a trade-off (when selecting a square in the game) between squares that have a high probability of containing a ship/squid and squares that are a good choice for carrying out a binary search of the remaining possible board states. Presumably, though, the remaining board states are sufficiently random that no square is significantly better than any other in terms of the binary search.

abetusk 6y ago
Yeah, that's an interesting point. I think the information gained from the first sacrificial game is enough to reduce the search space so they can plow through the remaining games. There's obviously some tradeoff for a generalized system. I guess the framework for this is some type of "best choice problem" to find optimal strategy switching? [1] [1] https://en.wikipedia.org/wiki/Secretary_problem https://en.wikipedia.org/wiki/Secretary_problem
nullc 6y ago
I implemented a solver for the computer hacking minigame in fallout 3 (? whatever one is the oldest with the hacking minigame)-- it was sort of a 'mastermind' but with words. My solver eventually always won, without anything as fancy as reverse engineering the game. But to get there I had to both choose the option that maximized the information gain and look ahead many moves to make that estimation accurate-- the choices were non-independent so a simple entropy estimate (e.g. picking the choice closest to 50% on their heatmap) won't necessarily give the best play. Sometimes the move that distinguished the answer list the best was was not the first move in the pair (or n-tuple) of moves that best distinguished the list. By lookahead I mean for each ultimate answer, play out the game many moves taking all (or a pruned set of choices) and measure how much narrowing you get after several moves conditional on the first move. IIRC without the lookahead the entropy based play was worse than playing the most likely choice, and with just the most likely choice my solver wasn't good enough to always win without retrying, so I had an incentive to overcome the local minima of using just the most likely. Something similar might apply to this, as the geometry of the targets makes the choices non-independent. But it sounds like taking the most likely choice is good enough in this game so perhaps they stopped their development there.

abetusk 6y ago

Yeah, that's an interesting point. I think the information gained from the first sacrificial game is enough to reduce the search space so they can plow through the remaining games. There's obviously some tradeoff for a generalized system. I guess the framework for this is some type of "best choice problem" to find optimal strategy switching? [1] [1] https://en.wikipedia.org/wiki/Secretary_problem https://en.wikipedia.org/wiki/Secretary_problem

nullc 6y ago

I implemented a solver for the computer hacking minigame in fallout 3 (? whatever one is the oldest with the hacking minigame)-- it was sort of a 'mastermind' but with words. My solver eventually always won, without anything as fancy as reverse engineering the game. But to get there I had to both choose the option that maximized the information gain and look ahead many moves to make that estimation accurate-- the choices were non-independent so a simple entropy estimate (e.g. picking the choice closest to 50% on their heatmap) won't necessarily give the best play. Sometimes the move that distinguished the answer list the best was was not the first move in the pair (or n-tuple) of moves that best distinguished the list. By lookahead I mean for each ultimate answer, play out the game many moves taking all (or a pruned set of choices) and measure how much narrowing you get after several moves conditional on the first move. IIRC without the lookahead the entropy based play was worse than playing the most likely choice, and with just the most likely choice my solver wasn't good enough to always win without retrying, so I had an incentive to overcome the local minima of using just the most likely. Something similar might apply to this, as the geometry of the targets makes the choices non-independent. But it sounds like taking the most likely choice is good enough in this game so perhaps they stopped their development there.