Which strategic board game would you recommend for learning how to develop artificial intelligence?

We had to program a board game using a 32-bit computer and Lisp in an Artificial Intelligence elective course I attended. Tic-tac-toe (5x5) was the easiest game to select, while checkers was the most difficult. We realized that most teams who choose checkers would not accomplish anything worthwhile in time due to the time limit, but tic-tac-toe was too basic, so we tried something in the center.

Nine Men’s Morris was the game we chose. It is made out of a twenty-four-point grid. Each player starts with nine pieces and must strive to form ‘mills’ (three pieces lined up horizontally or vertically) in order to eliminate an opponent’s pieces from the game until only two remain. The game features three stages in which the laws of movement change: in the first, the pieces can be put in any vacant spot; in the second, the pieces can only move to nearby locations; and in the third, the losing player (with just three pieces remaining) can ‘fly’ the pieces to any unoccupied position.

We utilized the Alpha-beta pruning algorithm, which performed well. For fun, we tried it against the one in the Assassin’s Creed game.

Othello (aka Reversi). Chips on the board are black on one side, white on the other. Start with each player having 2 on the board in the center of an 8x8 grid, the two being diagonal from each other. Players take turns placing one of their chips so there’s one of theirs on either end of any other chips (theirs and/or opponents), which causes those to be turned into the player’s chips. Try to get the most chips on the board to yours. It’s better to search it because I have a hard time describing it in detail so it’s easy to understand.