search

schrum2 / MM-NEATv2

MM-NEAT version 2.0 is no longer supported. Please get MM-NEAT 3+ from https://github.com/schrum2/MM-NEAT
Other
11 stars 5 forks source link

Alpha-Beta pruning for Minimax #353

Closed schrum2 closed 7 years ago

schrum2 commented 7 years ago

Minimax will unnecessarily search certain portions of the game tree which are guaranteed to be irrelevant. There is an approach called alpha-beta pruning which ignores these branches. I describe it in this video, https://youtu.be/A7AO152vy50, and you can also find code online in various places.

Create a separate BoardGamePlaying agent that extends the BoardGamePlayerMinimax. Call it BoardGamePlayerAlphaBetaPruningMinimax. The only thing that this class should really need to do is override the minimax method, which I have converted from private to protected inside of BoardGamePlayerMinimax. I believe you will also need to pass additional parameters to the minimax method to make it work, so what I want you to do is include these parameters in the original BoardGamePlayerMinimax method signature, but ignore them inside of that class. Those extra parameters will only be used inside of the new BoardGamePlayerAlphaBetaPruningMinimax version of minimax

schrum2 commented 7 years ago

See comment made in this commit: 22389dd21d057bd5e688e1698cc65acafd783339

schrum2 commented 7 years ago

Make a unit test for the alpha-beta pruning version. Do so in the following way:

Notice that I added a Random instance to the random board game player. This is set to be RandomNumbers.randomGenerator by default, so that any given experiment can be recreated with the right random seed. However, since the Random instance is stored locally, this also means that any class in the same package will be able to replace the random instance with a new Random instance.

The reason this is useful is that minimax and alpha-beta should play the game in exactly the same way. The only difference is efficiency. So, you can assign the random instance in the random board game player to be a new Random(0) and then have it play a game against standard minimax. This will lead to some given outcome. Then, you can reset the random player's random instance to new Random(0) again and have it play against the alpha-beta version. The final outcome should be identical! Repeat this process in a loop for all random seeds from 0 to 100, asserting that the final minimax outcome is the same as the final alpha-beta outcome. Feel free to use the piece differential evaluation function in the tree search agents.

By the way, please also move all BoardGamePlayers into boardGame.agents, but move the tree search variants into a sub-package boardGame.agents.treesearch

schrum2 commented 7 years ago

Once the unit tests described above are successful, replace all uses of minimax in batch files with the alpha-beta version (it is strictly better in every sense).

DarwinJohnson commented 7 years ago

The Minimax Players in the BoardGame Batch Files have been replaced with AlphaBetaMinimax Players. The AlphaBetaMinimax has been proven to make the same decisions as the Minimax.