Search code examples
performanceoptimizationtreechess

Would a minmax / negamax tree perform significantly better if the stored states contained little information?

I'm working on a chess AI and have concerns for the performance later down the road.
Right now, my negamax tree contains every game state as you would expect, though each state stores the entire board in ASCII form, along with the fitness and methods.
Would the tree perform better if I were to trim the stored information down to, say, just the moved piece? For example, instead of storing the entire ASCII board, store just "b2a2" (b2 moved to a2). Thanks.

Solution

  • Short answer: Yes, storing only the moves should be faster.

    Long answer:

    At each position, you have to have access to the current board. In general, chess engines use a data structure for the board, which includes a MakeMove and UnmakeMove operation. Then it is sufficient to store only the moves.

    Technically, it is possible to avoid implementing a real UnmakeMove operation by internally keeping a stack of the positions. Then UnmakeMove just pops the stack. On some older architectures, this used to be very fast. If I'm not mistaken, Cray Blitz used that technique in the 80s.

    Today, all engines that I know implement an UnmakeMove operation, as on todays machines cache efficiency is very important. Keeping a stack of positions puts too much pressure on the cache, so it is avoided.

    By the way, as you mentioned that you are using an ASCII representation of the board, I would encourage you to read the Board Representation article on the chessprogramming wiki. Using an efficient representation of the board is crucial for performance.