... and we're back just in time for me to continue talking about performance-related ideas in Reversi AI. In this case, I'm going to keep it pretty short and talk about a couple of simple things that made a surprising difference.

Small-scale optimizations

Caching results

Values like the number of pieces for each player and the positions of valid moves for each player are data that are used pretty often. Instead of calculating it every time it's needed, just keep the data around until it's changed. This is basically the first step of iteratively calculating values.

Another manifestation of this technique is pre-calculating values. Quite often the same values are calculated again and again. Instead of recalculating them, calculate them once at the beginning of the program and then use these pre-calculated values. Depending on how static these values are, you can often just supply them as constants or a pre-defined static table in the application, completely obviating the need for runtime calculation. Opening and closing books are more complicated examples of where this may fit in for a game.

There are cases where caching data can be bad. For example, one of the experiments I tried was to keep around the evaluated move trees such that I wouldn't have to recalculate them all. One of the (many) problems with this is that it is a lot of data... so much that it may get pushed to virtual memory on the hard drive. Hard drives are so slow that it would be pretty disastrous for performance if you had to use it... computers are so fast now that you can probably recalculate the data in the time it'd take to be read from the disk. Example: A fast hard drive (non-SSD) will have an average latency greater than 2ms. Let's say a computer can process 1 billion instructions a second (not unreasonable for a 3 GHz processor), which means 2 million instructions run in the time it took to read the data from the disk. You can do a lot in 2 million instructions.

Use compatible data structures everywhere

Rather than dealing with (x,y) sets for positions or moves, a position can be one 64-bit number with a single bit set that represents the location: a bitboard. This makes it very easy to use with the rest of the bitboards, especially since the "valid moves" calculation results in a bitboard. As long as you don't have to convert back and forth often, it is very convenient and efficient.

After that short post, we're heading into the home stretch. Next time: Wrapping it up.


There are no comments on this post.