Examing gamespace via candidate moves

Computer Chess involves two algorithms.

1. Evaluate a position
2. Identify “Good” moves

The latter are called “Candidate moves.” Once you write a program to do both, you are (basically) done. On your turn, identify candidate moves, then for each candidate adjust the position, apply opponents candidates moves, and min-max. Obviously this brushes a lot under the rug … evaluating a position is not easy, either.

Most games will only have one best move in a position, but there could be a large number of good moves that are slightly inferior to the best move (and it may be beyond a players ability to determine what is best). And not all games will have a single best move at each point. (Games involving bluffing, simultaneous decisions, auctions, and other elements can confuse the mix).

Poor games widen the gap between first and second. A consistently inferior move is annoying, especially if its an ‘inorganic’ move. For example, a Puerto Rico Building that is grossly overpriced and never useful. A game chock full of those is one to avoid.

This is a roundabout way of continuing the ongoing discussion about a single way to win. Consider Puerto Rico (which I have iconoclastic thoughts on, remember). Even though I consider it an optimization game, almost every decision present several reasonable candidate moves. Almost every building shows up (not every game, but you don’t see a chess player capturing a lagging pawn with his queen for a long term sacrifice … but it shows up in World Championship play once in a while. (I don’t remember the exact players, but the game was from the ’53 candidates tournament, written up by Bronstein).

Not every move has to be tough, but not every move should be formulaic. A reasonable chess game has 40 moves (say) and if you know openings to ~8 moves, and you have a few forced exchanges and routine moves, then say you have 25 moves. (And the openings still have choices, but more stylistic). In Puerto Rico you have perhaps 12 role selections, plus building and shipping (and fields). Granted, some percentage of them will be obvious (most shipping, most fields, some buildings and roles) but you still get a good number of moves.

Le Havre? 42 moves (in a three player game) plus some building decisions and loan pay backs. But the number of moves where I feel there are multiple reasonable decisions feels much lower. Typically I stop with about 3 rounds at the end and plot my final 7-8 moves as one clump (allowing for some disruption for timing as a contingency). The opening is often “Take the best stack” or “Build a building” or “Occupy the marketplace.” Since often 1-2 of these are not valid moves, its simple.

St. Pete also seems to have a large number of automatic moves. (Again, without the expansion). One point is that If I have the wrong evaluation function (“Moving Knights never works”) then I may discount valid candidate moves. Tom explicitly mentions that possibility in his comment regarding groups with a single strong player. See Point C in this comment). I suppose, with Le Havre, that could be the case, but I rarely have to tank in Le Havre.

There’s another interesting option … a game may have one clearly best situational move based on position, but evaluating positions (not moves) may be difficult to discern without enough experience. (Or may simply be impossible in a reasonable amount of time). War of the Ring strikes me as the ‘best’ example of this, although it isn’t perfect. But even in a game like this, you have the delight of evaluation, then once you are done you simply pick the best move based on your condition. Consider St. Pete, if you mainly decide when to shift from economy to VPs, as an example.

Back to computers — they do candidate moves by a set of rules. A chess computer should consider all moves that capture, all checks, and any move that sets up a threat (I believe a common algorithm looks at the first move and assumes that your opponent passes … would your second move be brutal? If so, it’s a candidate).

I’m told that an advance in Go AIs is the idea of just selecting moves and then doing a monte-carlo simulation of the position (randomly playing pieces) and that that works reasonable well for ‘strategic’ placements (not for tactical fighting, of course).

In a new game, I’ll cycle through all the options and then pick. But as I get better, typically I’ll just focus on a few candidates and explore them deeply. This is (apparently) typical. If I play well, I’ll ‘automatically’ (ie, intuitively) pick the reasonable candidates. Of course, I can miscalculate or have a blind spot.

The “One way to win” games may be interesting or not. In Puerto Rico, evaluating the position and the ‘look ahead’ features are difficult. For Le Havre? Not so much. Automobile? I’m playing less intuitively, so its an open question, but my gut is that the space isn’t too deep. St. Pete took lots of games, but I don’t pause to weigh multiple candidate moves often…

Anyway, just another way of stating and viewing the issue…