I'm playing around with writing an ai for a game of perfect information, like chess, but not chess. It has a significantly more complicated game board, and copying it for every iteration of the minmax algorithm would slaughter performance. So, I'm wondering if anyone knows of any articles/resources/etc on how to avoid having to copy the game board each time. Right now I'm considering converting the game board into an AI internal format that's suitable for generating and storing deltas on the board. (So instead of storing the move, and storing a cloned and modified copy of the board, it's store the move, and store what changed on the board.) However, I'm still not certain this would be the best way to go about it... Perhaps even an algorithm other than minmax? (are there other perfect-information game-playing algorithms?)

Yeah, store the delta of the board.

On chess for example you store the start position and piece, end position and piece (pieces for pawn upgrade), the removed piece and its position (for en passant). So with these 6 bits of information you can undo a move.

now dependent on your game you have to find something to do this too.

C-junkie,
another way to look at it is: don't store the board, just make the move and undo the move on return. Only one board needed for the whole analysis, and the information to undo the move should be very simple.

Minimax is a vaste area ... look for NegaScout and MTD(f), move ordering, Trasposition tables, (Multi)ProbeC, killers ... and all kinds of prunning. Dramatic improvements can be achieved with the correct ones.

Quote: Original post by DeepButi
C-junkie,
another way to look at it is: don't store the board, just make the move and undo the move on return.

So stunningly simple, and I didn't think of it. Thanks!

Quote: Minimax is a vaste area ... look for NegaScout and MTD(f), move ordering, Trasposition tables, (Multi)ProbeC, killers ... and all kinds of prunning. Dramatic improvements can be achieved with the correct ones.

Right, I was only looking for ways to avoid slaughtering performance by duplicating a massive board, and I think I found it!

In code I've seen, people don't typically make a copy of the board (although it isn't usually a big issue for games like chess, a minor linear slowdown in an exponential problem). Typically people make a stack (usually a simple C array) of only the info that needs to be backed up (or info which is more efficient to backup). For instance, in chess you can bidirectionally incrementally update the side to move (it doesn't need to be backed up). The color is just toggled back and forth, white, black, white, black, irregardless of whether you are making or retracting a move. The castling rights, on the other hand, must be backed up. You can't incrementally recompute the previous castling rights when undoing a move, so it has to be backed up.

There are lots of algorithms which are used for searching game trees, but the most popular ones fall into a small number of categories (and pretty much everything is just an optimization on minimax, depth first search). You have basic minimax (or negamax, same thing), which will search (for a uniform tree) B^D nodes where B is the branching factor (number of legal moves per node), and D is the search depth. Then you have alpha-beta which is equivalent to minimax in that it provably produces the same score as minimax, but will only search between B^D nodes (worst case, same as minimax) and sqrt(B^D) nodes, depending upon how well the moves are ordered at each node (i.e. it is much more efficient if you have a "good guess" handy). After this, it is mostly variations on the theme of minimal-window alpha-beta searching, which include principle-variation-search (PVS) and negascout (which, for practical purposes is the same thing as PVS), and Memory-enhanced-Test-Driver (MTD) based algorithms like MTD(f). These algorithms (PVS, negascout, MTD(f)) typically provide some small linear improvement above alpha-beta (~10-20%). Other methods are out there, such as best-first algorithms like SSS* and B*. Unfortunately, the drawback of breadth-first/best-first tree search algorithms is that you need an infinite amount of memory for them to work in practical situations. Interestingly enough, SSS* and B* can be implemented as a form of MTD search. The last few algorithms are kind of special case algorithms, not generalized game playing algorithms like the rest. In this category we have conspiracy number search family, and the proof number search family. They can be used in some situations to find quick results, such as finding very deep forced checkmates in chess in very few nodes, or to get a sort of pseudo-confidence level for how sure you can be about a "good guess" that you have. And of course, depending upon the game, there are a multitude of enhancements to any of these algorithms. For instance, in go they use a lot more of things like ANNs, GAs, and so on, while in games like checkers or chess the brute force tree search approach has yet to meet a serious rival.

I'm not sure I would call something like prob-cut or multi-prob-cut an algorithm per se. It is really a heuristic method of forward pruning the search tree (i.e. theoretically unsound, unstable). The difference is that an algorithm like alpha-beta does backward pruning, i.e. it only prunes sub-trees that is has proven to be irrelevant to the final result of the search.

BTW, are you able to share with us what game you are working on? I can't think of many where having to copy the board state when making/undoing moves would "slaughter performance". You could be playing go on a 1000x1000 board, but then copying that board around is the least of your worries since your branching factor is one million :-)