The International Checkers Game

The lab will focus on the most common variant of checkers (at least in France): Internation Checkers (sometimes called draughts).

If you are unfamiliar with checkers, you can check the International Checkers Rules.

Unlike some other variants (notably american checkers):

• the game is played on a 10x10 board
• pawns (aka pieces/checkers) can only move forward
• pawns can capture forward and backward
• when a capture is possible, the player must play the move that captures the most adversaries
• a queen (aka king) appears when the player reaches the opposite end of the board
• a queen can move freely multiple steps in one direction

Setting up

This labs should be done in groups of 1 or 2 students (but 3 is tolerated in case there is an uneven number of students and you don't want to be alone).

To get the base code for the lab, you should:

• choose your group members
• head to the lab's github classroom
  • create a team or join an existing one
  • team name should follow the convention {GROUP} {SURNAME1} / {SURNAME2} -- LAB3
    • IMPORTANT: the name must be different that the one used for LAB2, hence the -- LAB3 at the end.
  • accept the assignment
• TROUBLESHOUTING: if github classroom is in a bad mood, you can get the base code from this repository.

This process will create a new repository for your group with the base code for the lab. The repositories are private, and only the members of the group and the teachers can see them.

You can now clone the repository and start working on the lab

Provided code

You are provided with an implementation of the board and rules (board.rs) and of a simple AI engine (minimax.rs). Below is a highlight of the main parts (note: you do not have to understand everything in the board implementation).

• board.rs: "simple" implementation of the board and basic rules for International checkers. It notably contains the following elements:
  • > Color: enum with White and Black variants
  • Cell representation of the content of a cell of the board Empty and White/Black-Pawn/Queen
  • Position: position of a valid cell on the board. Its implementation is fairly low-level but you access its coordinates (coords())
  • Dir: one of the four possible directions for moving UpLeft, UpRight, ...
  • Move Elementary movement on the board: number of cells traversed in a single direction. If the moves is over an adversary's piece, it results in capture
  • > Action: a sequence of Moves from a given position. Represents any possible action available to the player, from a single pwn displacement to multiple captures.
  • > Board: board representation (implementation detail: using a padded array)
    • turn: indicates which player is to play next (white/black)
    • num_ply: number of turns already played
    • init(): creates the initial board
    • count(): count the number of occurrences of a particular cell value
    • is_draw(): true iff the game is considered a draw
    • actions(): return all the valid actions available to the current player
    • apply(): returns the board resulting from applying the (assumed valid) action
• minimax.rs: very primitive implementation of minimax (in its negamax variant)
  • select(...): will return the best action according to a minimax search of a fixed depth (defined in the MinimaxEngine), ignoring any deadline given to it.
• mcts.rs: skeleton for the implementation of MCTS (more below)
• engine.rs: Interface for abstracting over different engines (mcts or minimax). It defines an Engine trait (similar to a Java interface) that allow abstracting over different kind of engines.

Testing

• ▢ In the main file, simulate a few games between two minimax engines.
  • the main::example_game() function is the main one there

Monte Carlo Tree Search (MCTS)

The objective of the lab is to implement the MCTS method for the checkers games. We will split it in several steps.

Scoring

• ▢ Implement the mcts::white_score() function.
  • The function can freely assume that it is only evaluated on a final board, that is: the game is a draw or the current player has no available actions.
  • It must compute the score from the point of view of the white player
  • Useful methods/attributes on Board: is_draw(), actions() and turn

Rollouts

• ▢ Implement the mcts::rollout() function.

Starting from the board given as parameter, the function should

1. select a random action among the valid ones
2. generate the resulting state
3. repeat 1./2. until the board is final (no actions left, indicative of draw or loss)
4. return white's evaluation of the final board

#![allow(unused)]
fn main() {
use rand::seq::IndexedRandom; // makes the `choose` method visible on `Vec`

let ints: Vec<i32> = vec![1, 2, 3];
let choosen: Option<&i32> = ints.choose(&mut rand::rng());
}

• ▢ Test your rollout: function:
  • in the main.rs, call you rollout function a large number of times
    • what is the average value of the calls (hint: should be close to 0.5)
    • How many rollouts can you do in 1 second (hint: should be several tens of thousands in release mode)

Basic MCTS Engine

MCTS graph

The mcts.rs file contains several basic datastructures that you will use for the implementation of the algorithm.

• Node: a node of the MCTS graph that has already been evaluated with a rollout.
  • board: (s) the state of the game this node represents
  • count: (N(s)) number of times this node has been selected
  • out_edges: outgoing edges for all valid actions available on the state. Each OutEdge contains
    • the corresponding action (a)
    • the number of times the action was visited (N(s,a))
    • the evaluation of the target state (Q(s,a))
  • initial_eval: (U(s)) result of the initial rollout
  • eval: (Q(s)) estimated utility of the nodes computed from children states' utilities

The Node structure essentially represents a node of the MCTS tree with all associated metadata and outgoing edges. The MctsEngine structure allow finding the Node associated to a given Board.

Playout implementation

For implementing MCTS you have three methods to implement

• ▢ playout: recursively update the board (s) and returns its updated evaluation (Q(s))
  • if the state was never visited before (not in the graph), it should evaluate it with a rollout and add it to the graph
    • the Node::init(...) will probably prove useful
  • otherwise, it should
    • select an action (see select_ucb1 below)
    • perform a recursive playout for the resulting state
    • update the evaluation (see update_eval below)
• ▢ select_ucb1: selects the best action according to UCB1 (course playout algorithm, line 6)
  • from the node associated with the board (s) it should:
    • compute the UCB1 score for each action
    • return the action with the highest UCB1 score
    • it should use the exploration_factor (C) from the MctsEngine structure
• ▢ update_eval: updates the node (eval and counts) at the end of a playout (course algorithm, lines 10-12)
  • It given the board (s) that should be updated, the action (a) that was taken and the evaluation of next state (Q(s,a))
  • it must update the counts (N(s), N(s,a)) and store the given action_eval (Q(s,a)) on the corresponding edge
  • recompute and update the node's evaluation (Q(s))
  • it should return the updated evaluation (Q(s))

ABCDEFGH   White  (0 plies)
1  b . b b
2 . . . b
3  . . . w
4 . . . .
5  . . . .
6 . b w .
7  . . w .
8 w w w .

After 1000 playouts:
Q: 0.78091437    (N: 1000)       <- Q(s) and N(s)
     301 C8 B7   [0.87960243]    <- Q(s,a), here for the action "C8 B7"
     230 C8 D7   [0.84222764]
     184 F7 G6   [0.8040308]
     103 E6 D5   [0.693204]
      86 E6 F5   [0.6523256]
      49 A8 B7   [0.48979592]
      46 E8 D7   [0.47826087]
      -- -----   ------------
      ^    ^         ^
      |    |         Evaluation for this action (Q(s,a))
      |    Action (a)
      Number of samples per action (N(s,a))

MCTS Main Loop

With all those ingredients, you should be able to implement the main MCTS loop in the select method.

• ▢ implement the select method
  • until the deadline is not passed, do playouts from the current state
  • return the action with the most selections

#![allow(unused)]
fn main() {
let time_remaining: bool = Instant::now() < deadline;
}

Evaluating you engines

Variations of your engine

There are a number of elements that can be tuned and may affect the performance of your engine:

• the exploration_weight parameter
• the evaluation function: the initial implementation is based on a rollout but you could
  • use the average over more than one rollout (more accurate but potentially costly)
  • use arbitrary evaluation function instead of a rollout (notably, the one used by minimax)
• the time allowed for MCTS at each turn

Evaluation set up

Engine evaluation is typically done over a number of games against another engine, to compute the average score of an engine against another in a statistically meaningful manner.

When evaluating your engine you can do so against either:

• a baseline solver: a solver with well understood performance. These include:
  • the random solver that acts randomly at each turn (not implemented for you)
  • the minimax solver with a given depth
  • any of the above two can be made artificially stronger by placing them in a favorable situation (e.g. removing pieces from their opponent)
• another configuration of your solver

Performance characterization

In addition to evaluating your solver against others, you should provide some metrics sheding some light on the functionning of your solver. This may notably include:

• number of playouts per second
• average playout depth (number of actions selected before reaching a leaf of the tree)
• length of the principal variation in the tree. The principal variation is the game that would have been played if both players were to follow the MCTS policy (always selecting the action with the most playout) until reaching a tree leaf. It is deemed as the most likely by the MCTS search, and this metric would tell how far did the algorithm explored this path
  • at the end of the principal variation, the node would have very few selection and are thus of low confidence, you may restrict this principal variation to stop as soon as an action was selected less that a number of time (e.g. 100), indicating that the algorithm is not yet convinced of the value of this action.

These metrics may differ between start, middle and end games, and should be computed for several representative states of these categories.

Playing against each other

I haven't had time to provide a mechanism to automatically export an agent. If you want to test against someone else's AI, and they are willing to share the code you can:

• copy their engine's code (mcts.rs) into a renamed_file in your repository
  • e.g. src/uce_mcts.rs where UCE (Unbeatable Checkers Engine) is the name of the engine
• declare the code as a module to the rust compiler
  • add pub mod uce_mcts; at the top of your main.rs
• use their engine from the imported module, e.g.,
  • let black_engine = uce_mcts::MctsEngine::new(1.);