Improvement to the Game's Data Structures
To improve the speed of the search the following improvements on the game state internal representation have been added:
- A list of black dies, yellow dies in the class Board for faster access to this information. The number of dies not in gutter for each player, and the same thing for each separate class of die (D8, 6, 4)
- Instead of performing several deep clone at each search iteration, only one GameState object can be used because it is possible to reverse a move. GameState.applyMove return a CompiledMove, for which the inverse (CompiledMove.inverse) can be computed and passed to GameState.applyCompiledMove.
The tests ran with MinMaxSearchAlgorithm (which uses the improvement described above) against DCMinMaxSearchAlgorithm (which use "deep cloning") show the significant speed improvements brought by these techniques (more than 40 % speed up on my machine).