CS540 P6: Game AI

As you’re probably awareLinks to an external site., there are certain kinds of games that computers are very good at, and others where even the best computers will routinely lose to the best human players. The class of games for which we can predict the best move from any given position (with enough computing power) are called Solved GamesLinks to an external site.. Teeko is an example of such a game, and this week you’ll be implementing a computer player for it.

How to play Teeko

Teeko is very simple:

It is a game between two players on a 5×5 board. Each player has four markers of either red or black. Beginning with black, they take turns placing markers (the “drop phase”) until all markers are on the board, with the goal of getting four in a row horizontally, vertically, or diagonally, or in a 2×2 box as shown above.

If after the drop phase neither player has won, they continue taking turns moving one marker at a time—to an adjacent space only!—until one player wins.

Program Specification

This week we’re providing a basic Python class and some driver code, and it’s up to you to finish it so that your player is actually intelligent.

Here is our partially-implemented game: teeko_player.pyDownload teeko_player.py

(If your computer doesn’t like downloading .py files, grab teeko_player.py.txt Download teeko_player.py.txtand remove the .txt extension.)

If you run the game as it stands, you can play as a human player against a very stupid AI. This sample game currently works through the drop phase, and the AI player only plays randomly.

First, familiarize yourself with the comments in the code. There are several TODOs that you will complete to make a more “intelligent” player.

Make Move

The make_move(state) method begins with the current state of the board. It is up to you to generate the subtree of depth d under this state, create a heuristic scoring function to evaluate the “leaves” at depth d (as you may not make it all the way to a terminal state by depth d so these may still be internal nodes) and propagate those scores back up to the current state, and select and return the best possible next move using the minimax algorithm.

You may assume that your program is always the max player.

Generate Successors

Define a successor function (e.g. succ(state)) that takes in a board state and returns a list of the legal successors. During the drop phase, this simply means adding a new piece of the current player’s type to the board; during continued gameplay, this means moving any one of the current player’s pieces to an unoccupied location on the board, adjacent to that piece.

Note: wrapping around the edge is NOT allowed when determining “adjacent” positions.

Evaluate Successors

Using game_value(state) as a starting point, create a function to score each of the successor states. A terminal state where your AI player wins should have the maximal positive score (1), and a terminal state where the opponent wins should have the minimal negative score (-1).

1. Finish coding the diagonal and 2×2 box checks for game_value(state).
2. Define a heuristic_game_value(state) function to evaluate non-terminal states. (You should call game_value(state) from this function to determine whether state is a terminal state before you start evaluating it heuristically.) This function should return some float value between 1 and -1.

Implement Minimax

Follow the pseudocode recursive functions on slide 14 of this presentationLinks to an external site., incorporating the depth cutoff to ensure you terminate in under 5 seconds.

1. Define a Max_Value(state, depth) function where your first call will be Max_Value(curr_state, 0) and every subsequent recursive call will increase the value of depth.
2. When the depth counter reaches your tested depth limit OR you find a terminal state, terminate the recursion.

We recommend timing your make_move() method (use Python’s time libraryLinks to an external site.) to see how deep in the minimax tree you can explore in under five seconds. Time your function with different values for your depth and pick one that will safely terminate in under 5 seconds.

Testing Your Code

We will be testing your implementation of make_move() under the following criteria:

1. Your AI must follow the rules of Teeko as described above, including drop phase and continued gameplay.
2. Your AI must return its move as described in the comments, without modifying the current state.
3. Your AI must select each move it makes in five seconds or less.
4. Your AI must be able to beat a random player in 2 out of 3 matches.

We will be timing your make_move() remotely on the CS linux machines, to be fair in terms of processing power.