Description
Assignment Goals
● Familiarize yourself with solving games using AI.
● Practice implementing a minimax algorithm.
● Develop an internal state representation in Python and get familiarized with
classes in Python.
Summary
In this assignment, you’ll be developing an AI game player for a game called Teeko.
As you’re probably aware, 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) is called Solved Games. Teeko is an example
of such a game, and this week you’ll be implementing an AI 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! (this includes diagonals, not just left, right, up, and down one
space.) — until one player wins. Note, the game has no “wrap-around” similar to other
board games, so a player can not move off of the board or win using pieces on the other
side of the board.
Win conditions summarized for Teeko:
● Four same colored markers in a row horizontally, vertically, or diagonally.
● Four same colored markers that form a 2×2 box.
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. The skeleton code appears in
game.py.
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 and classes in Python (if you
are new to this, then you can refer to this tutorial). There are several TODOs that you
will complete to make a more “intelligent” player. You are allowed to implement helper
functions but please do not change the signature (parameters/name etc) of the
functions given in the starter code.
MAKE SURE TO USE PYTHON VERSION 3.10.6
(You can check your python version by running python3 –version on the terminal)
Make Move
The make_move(self, 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.
The following section will provide you with the steps that you should be implementing as
a part of this exercise. You will be implementing several helper functions for your
make_move method to work (for the helper functions, the parameters do not have to be
the exact same as the write-up shows because none of those functions are directly
tested).
You may assume that your program is always the max player.
1. Generate Successors
Define a successor function (e.g. succ(self, 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.
CS 540 Homework 9
2. Evaluate Successors
Using game_value(self, 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).
Finish coding the diagonal and 2×2 win condition checks for the game_value method.
Define a heuristic_game_value(self, state) function to evaluate non-terminal
states. For some hints, check out the Games II Lecture Slides (you should call the
game_value method from this function to determine whether the state is a terminal
state before you start evaluating it heuristically.) This function should return some
floating-point value between 1 and -1.
3. Implement Minimax
Follow the pseudocode recursive functions on the slides of our class lecture,
incorporating the depth cutoff to ensure you terminate in under 5 seconds.
● Define a max_value(self, state, depth) function where your first call
will be max_value(self, curr_state, 0) and every subsequent
recursive call will increase the value of depth.
● 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 (try Python’s time library) 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.
CS 540 Homework 9
Evaluating 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 the 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.
Using the minigrader
You have been provided with a minigrader in the form of a python executable. It is
named minigrader.pyc. Make sure that the minigrader and the game.py file is in the
same folder and run the following command on the terminal:
python3 minigrader.pyc
Note that scoring 100 points on the minigrader does not guarantee 100 points on the
actual grader.
Submission Notes
Please submit your files in a zip file named hw9_.zip, where you replace
with your netID (your wisc.edu login). Inside your zip file, there should be only
one file named: game.py.
As usual make sure there is no code outside of functions and the provided main
statement and no extra prints. The standard regrade policy for the course as specified in
HW4 applies. Make sure to test your submission on the CS Linux machines!
The
minigrader we’ve provided contains most of the tests this time, so your performance on
the minigrader will be highly accurate and so regrade requests will be more strict. If your
code does not pass the minigrader, you likely won’t get a regrade.
CS 540 Homework 9
