The "hello world" of the artificial intelligence world is tic-tac-toe. Sticking to the tradition, we will also use this as our subject game, although the architecture and approach extend well beyond this simple example (for example, Global Thermonuclear War; for other use cases, refer to John Badham's War Games).

Tic-tac-toe is a two-player game of Xes and Os. The board is a 3 x 3 grid. One player has the symbol O and the other has the symbol X, and the play alternates. On a turn, a player places their symbol in any open cell in the grid. If by placing their symbol, it completes a horizontal, vertical, or diagonal line of three contiguous symbols, that player wins. If all cells are filled without forming a line of three, then the game is a tie.

A common approach to developing Artificial Intelligence programs for games with alternating turns is to explore the game tree recursively searching for the game state that evaluates best for the current player (or worse for...