Checkers-AI

A checkers (or draughts) game with an AI algorithm (for more information, see #AI Algorithm), written in Rust.

Rules: English draughts

A rather simple UI, running in a terminal:

Table of content

• Getting started
• AI Algorithm
• License

Getting started

Installation

# Clone the repository:
git clone git@github.com:rreemmii-dev/Checkers-AI.git

cd Checkers-AI

Ensure you have cargo installed

Run

cargo run --release

AI Algorithm

General idea

The idea is to run several negamax searches using alpha–beta pruning, each in a different thread.

Thus, the AI runs in two parts:

1. A shallow multithreaded depth-first search (DFS), in which the AI goes 2 moves deep.

2. A negamax search at the end of each branch of the initial DFS.

Compute a board score

As the negamax exploration is run with a limited depth, a way to compute the score of a board is required.

First, a score has to be chosen for each piece:

• 1 point for a man
• 2 points for a king

Then, a coefficient has to be chosen, representing how close is the game to be a draw (either by 3 repetitions, or by playing 2 * 40 moves without capture nor promotion). A coefficient of 50 reduces players' effective score by half. The following functions where chosen (rather arbitrarily):

License

Distributed under the MIT License. See LICENSE.md