Last AI Lab

The primary objectives of this lab are to:

• finish and consolidate the MCTS code for checkers
• set up an evaluation of your code
• prepare your report for evaluation

Evaluation criteria

You will be evaluated based on:

• the code for your MCTS implementation
• a synthetic report presenting the results of your engine evaluation
  • this should be the README.md of you repository, starting with your names

The report should present:

• the experiments you have conducted and the associated results (as tables or graphs), matching the instructions at the end of the Lab3 subject. In particular, you should:
  • have a relative evaluation of your own engine (under different configuration) allowing you to select the best configuration
  • have an absolute evaluation of your engine (against baseline and with associated metric)
• a discussion of the results (why is a given configuration better than another, ...)

The report should:

• NOT explain the basic functioning of the checkers implementation or of the MCTS algorithm (we know how it works)
• state what differs in your implementation from the basic implementation (different heuristic, specific parameter, ...)
  • in other words, what you contributed with respect to the simplest implementation (or some known limitation/bug of your implementation)

The report may (optional):

• provide details on extra work that you have done in the context of the labs, related or not to MCTS and checkers.
  • for instance, if you have implemented an adaptation of alpha-beta pruning to the expectimax for 2048, we want to know about it (even if your evaluation turns out deceiving)
  • some hints of what can be done is given below, in the going further section.

Going further

A well conducted and functional MCTS implementation with associated evaluation is sufficient to obtain the average grade. However, there are a number of things that you can do in order to improve your grade and skills:

• MCTS: there are various things that can be done to exploit the graph structure of the MCTS search which are not done for the basic implementation. The datastructure you exploit is compatible with graphs, but is not fully exploited. This MCTS for graph article goes over the specific of MCTS in tree vs graph with lined section being a potentially easy gain (to be measured)
• minimax: implement alpha-beta pruning for checkers
• checkers: improve the evaluation function of checkers to account for runaway pawns (pawns that have a free path to become a queen) or quiescence (if there are possible captures in the evaluated state, simulate them before running your evaluation, avoiding given a high score to a situation where you have just captured a pawn but will be captured in the next turn).
  • this evaluation function can be used for either minimax or mcts
• 2048: add a form of pruning to the search:
  • ignore states that are highly unlikely (require four 4 tiles in a row to occur)
  • exploit alpha-beta pruning principles to the search (hint: the contribution of each move to the expectation term is capped by the maximum value and its probability)
• 8-puzzle: evaluate on much larger puzzles, requiring memory-limited methods (e.g. iterative deepening A*, beam search)