Game-Trees FPGA implementation (Othello Game)

Short Description

MinMax game tree search with alpha-beta pruning implemented in FPGA.
Rules and heuristics implemented for Reversi/Othello game. The system is capable of analyzing ~5M game states/second @50MHz. (no selective search).
RTL design Verilog 2001 compliant.
VGA output, pushbuttons input (for playing), using Spartan3E Starter Kit board.

General Features

Description

A Game Tree is a directed graph whose nodes are states of a game. A game state is a configuration of the game on a specific time. The complete game tree of a game consists of all possible game states, from the initial game position to the every possible end-game position, containing all transitions from a game state. Of course, when analyzing a game you cannot look at every game state to choose the best move using reasonable time resources, so this problem is intractable.

Anyway, AI for such games are based on searching only a partial game tree starting from the current game position and going a few plies deep, than based on a function that will heuristically evaluate the game state, you will pick a good, hopefully the best, move. Generally, increasing the search depth will improve your chance to pick the best move. (In rare cases this is not true).

The well-known algorithm to search a game tree and choosing the best move, is MinMax. This search method will start from a game state considered initial game state and expand it to generate all possible next-states, and then for every new state will generate the next game states and so on, until a specific depth is reached. When a leaf-node is reached, we can consider that to be an end-game state (because we cannot see deeper), and we will evaluate it. Evaluation of a game state should return a score reflecting the win-lose quantity. Then, going backwards in game tree, we have to maximize or minimize this value. For example, for your point of view, you will have to maximize your wining score and minimize mine. So from a game state you will pick the move which is best for you and worst for me. When it's mine turn, I will maximize my winning score and so on. MinMax will consider playing both roles, alternating. This mathematical model works very well for turn based games like chess, reversi/othello, checkers, etc.

An improvement for this search is alpha-beta pruning. The difference is that will not search all branches from the partial game tree. This improvement is also implemented in this system.