Adversarial Search

Due:

11:00pm, Friday October 22, 2021

Description

Write a program based on the Minimax algorithm that implements an AI player for the game of Teeko. The game rules can be found on the Wikipedia page for Teeko

Here is an image of a Teeko board:

Image source

The program must read a string representing a game state from standard input and output a valid move on standard output; the program must flush the buffer after writing to standard output. The program should terminate when an end-of-file is read from standard input. Additionally, the program must be executable.

A game state string has the following form:

R 3 8 13 24 2 4 5 10

which is a character followed by eight integers separated by spaces and ending in a new line. The first character is represents the current player and is ether ‘B’ for black or ‘R’ for red. The first four integers are the positions of the black pieces and the last four integers are the positions of the read pieces. During the drop phase, unplaced positions are represented as zeros. For example, the initial state of the game is:

B 0 0 0 0 0 0 0 0 

A move is represented as two integers separated by spaces and ending in a new line where the first integer corresponds to the current piece position and the second integer corresponds to the moved position. For example, to move a piece from 13 to 8, the move is:

13 8

During the drop phase, the current piece position is represented as a zero. For example, to put a piece on the position 9 during the drop phase, the move is:

0 9

There are two files in the starter code: teeko-engine.py and random-player.py. The teeko-engine.py program takes two command line arguments which correspond to programs for the black player and red player respectively. To play a game with two players that make random moves, first make the programs executable:

chmod u+x teeko-engine.py
chmod u+x random-player.py

Then run the teeko-engine.py program like this:

./teeko-engine.py ./random-player.py ./random-player.py

The game states are written to a file named teeko.log which might be useful for debugging purposes.

Getting the Assignment

The starter code for the assignment is on the Linux server at the path:

/export/home/public/schwesin/csc447/projects/project2-handout

Turning in the Assignment

You must turn in the following files:

1. player.x
2. README

The README file should be a plain ASCII text file (not a Word file, not an RTF file, not an HTML file) describing your design decisions. This should also detail your choice of evaluation function. One or two English paragraphs should suffice. Spelling, grammar, capitalization and punctuation all count.

To submit the assignment, execute the command:

    make submit

from within the assignment directory.

Grading Criteria

Grading (out of 100 points):

• 70 points — Performance (based on a 10 second move limit and a 100 turn game)
  • 70 points — average performance versus other submissions
  • 60 points — successfully beats a weak non-random player
  • 50 points — successfully beats the random player
• 15 points — for a clear description in your README
  • 15 — thorough discussion of design decisions; a few paragraphs of coherent English sentences should be fine
  • 8 — vague or hard to understand; omits important details
  • 0 — little to no effort, or submitted an RTF/DOC/PDF file instead of plain TXT
• 15 points — for code cleanliness
  • 15 — code is mostly clean and well-commented
  • 8 — code is sloppy and/or poorly commented in places
  • 0 — little to no effort to organize and document code

Note: if your solution is based on pseudo-code from a source other than the textbook or the lecture slides, then you must cite the source of the pseudo-code. Otherwise, you will receive a grade of zero for this assignment.