CS 57100: Artificial Intelligence

Assignment 3: Agents / Deterministic Games

Due 11:59pmEDT Tuesday, 27 September 2022

Please turn in a PDF through Gradescope, as well as submitting code separately in Gradescope. Make sure that you mark the start/end of each question in Gradescope. Assignments will be graded based on what you mark as the start/end of each question. Please typeset your answers (LaTex/Word/OpenOffice/etc.)

1. Search Strategies (programming assignment)

For this question you will be implementing an agent that plays a generalized tic-tac-toe. For those not familiar, the environment is an n×n grid, the rules are that you may place a piece on any unoccupied square, and the goal is to get k of your pieces in a row.

You are to first implement an optimal, deterministic strategy agent using α-β search. Note that this is a communicating agent: Your actuator is to write your move to a file (xmoves.txt for player x, omoves.txt for player o), with the move format player - x or o - followed by a number 1, 2, 3, ... for the row, letter a, b, c, ... for the column, and newline. e.g., x1a means to place an x in the upper left corner.) Your sensor is to read the opponent's move from their file.

There is a bit of systems issues in the programming - you need to wait for the opponent's move using some for of blocking file read or other means of waiting until the opponent has made their move. How you do this will vary depending on your programming environment, but this will enable communicating players written in different programming languages.

You must follow the rules (e.g., you can't place a piece outside the board or on an occupied square.)

Your code should be called from the command line as ttt n k [xo] - if x, you go first, if o you go second. When complete (either one player wins, or a draw where the board is full with no winner) you should terminate with writing win, lose, or draw to stdout.

Part 1: α-β

Please report on the following. Report on the requested outcome and anything else you find interesting about the test.

Try playing your code against itself and report the outcomes. Give at least one example (n and k) where x wins, and one example where you end up with a draw. Are there any case where o wins?
Try with n=8, k=4. Report on the outcome.
How does your system scale? Is there a board size where the time required is unreasonable?

Part 2: Alternative Strategy

Implement a strategy that you think may either be able to beat your strategy from Part 1, or that may run much faster than your Part 1 strategy on large n. Report on:

How your part 2 strategy does against your part 1 strategy. Give at least one case where your part 2 strategy shows some advantage. Are there any cases where your part 1 α-β pruning is better?
Run your part 2 strategy in competition with that of at least one other student. Give a brief (1-3 paragraph) discussion of the outcomes.

2. Simultaneous Tic-Tac-Toe

The player that goes first or second may have an advantage in this game. Imagine we did this instead as a simultaneous game, where both players try their move at the same time. If the players choose the same square, the move is void and they try again. Note: You do NOT have to implement this.

Would this be a good pure strategy game? Why or why not?
Work out a mixed strategy for the (3,2) game - a 3x3 board, where you must get two in a row. What is the minimax value of the game for each player?

3. Continuous multi-dimensional search

Problem to be deferred to a future assignment