A Checkers playing Artificial Intelligence, utilizing multiple game playing AI techniques.
Skip to the bottom for a quick start guide to play.
The AI player can take advantage of two different AI algorithms. The first is Alpha-Beta Tree Search with a board position scoring heuristic. The second is Monte-Carlo Tree Search (MCTS) with Upper Confidence Bounds (UCB). In their current implementations, Alpha-Beta is much more efficient and is a much stronger player.
Using Minimax with Alpha-Beta pruning, the tree search was able to achieve tree depths between 5 and 10 within 15 seconds. The achievable depth varies throughout the game because the branching factor fluctuates.
There is an implementation of Alpha-Beta taking advantage of multiprocessing. It doesn't seem to make a big difference in tree search depths.
I am looking into adapting a Convolution Neural Network (CNN) to assist MCTS, or Alpha-Beta, or to play entirely on it own. The plan would be to use Supervised training with the board scoring heuristic as the training metric. After the CNN converges on the Alpha-Beta player's skill level, Reinforcement Learning would be used to further improve the CNN.
Download this repository:
git clone https://github.com/pWhitS/CheckersAI.git
Alternatively, download the ZIP file above and extract it.
Run the game in a terminal simple by using:
$ python run.py
The game is setup to run by default as, Human player vs. AI player
How to Play:
The AI player moves on its own. You just have to wait for it to finish thinking.
For human players, when you are done thinking, first select the piece you want to move, then select the move location. Standard checkers moving rules apply.
To select a piece or a move location input a column-row pair, such as: A5, C7, H6, or D0. You will be prompted for each as shown below.
After each move, the updated board is printed.
A jump can be performed by simply selecting the location beyond the jump piece. For example: D4 to B2, as in the example below. Also, multiple jumps of arbitrary length can be achieved by inputing multiple, space delimited, move locations. An example is shown below as well.
Single Jump:
Multiple (Triple) Jump:
How to Win, Lose, or Draw:
- Capture all of your opponent's pieces.
- Force your opponent to have no legal remaining moves.
- A draw occurs after no captures have taken place for 40 moves.