Problem B
2D Tic-tac-toe
In this problem, you will implement a program that plays the game of Tic-Tac-Toe. Your goal is to implement a strategy that allows your program to win (or not lose) as often as possible. You will be provided a skeleton which generates a list of valid moves for you to choose from (see section ).
There is an square board $H$, consisting of $16$ cells. Two players, $X$ and $Y$, take turns marking blank cells in $H$. The first player to mark 4 cells along a row wins. Here by a row we mean any 4 cells, whose centres lie along a straight line in $H$. So, any horizontal, vertical and diagonal row is winning.
In this assignment, our goal is to find the best possible move for player $X$ given a particular state of the game.
Kattis will give your agent a number of board states and will ask for the best move for each state, at which point you have 0.25 seconds to provide an answer (if you fail to make a move within this time limit, your Kattis submission will generate a Run Time Error and exit with signal SIGXCPU). You will be scored based on these answers. The states are selected in or near the end game and the states represents situations where the answer makes a big difference for the outcome of the game. Note that you are not playing a full game as you would when you play against a friend or yourself.
Assignment
Your assignment consists of writing a program that plays tic-tac-toe as player X.
However, you are not going to start from scratch. You will receive a skeleton in Java or C++, which will take care of board representation, and calculating the possible moves from each board position. This way, you can focus on implementing the strategy for deciding which is the best move to make, where the core AI lies for this problem.
Provided code
The code skeletons (with compilation instructions inside in the READMEs) can be found in Canvas. Download C++ here: https://kth.instructure.com/files/1088493/download?download_frd=1 and Java here: https://kth.instructure.com/files/1088494/download?download_frd=1
A basic program is provided for you in each of the supported programming languages. The program, as it is provided, is fully functional, but plays a random legal move each turn. You must implement a better strategy. The given programs are written in such a way that they are easy to understand, which is not always the most efficient.
You should modify the player class and you may also create any number of new classes and files. The files included in the skeleton may be modified locally but keep in mind that they will be overwritten on kattis (except for player.cpp/hpp).
Testing outside Kattis
You can test your agent by making it play against the agents of your friends or against itself. The first step is to make sure that you can consistently beat the agent that is defined by the skeleton. This agent picks a random move from all available moves in every iteration.
The agents use standard input and output to communicate. The Moves made are shown as unicode-art on std err if the parameter verbose is given. The following sections show how you can test your agent on a Unix/Linux/Mac OS X system. If you use Windows, please read further down.
To play in a single terminal
Assume that “agentX” is your C++ agent, which is in the current directory together with another agent called “agentY”. First, you have to set up a pipe for them to communicate with:
mkfifo pipe
which you do once only.
Now you can make your agents play with
./agentX init verbose < pipe | ./agentY > pipe
The agent that is started with "init" will play as "O" (exactly one of them has to issue "init").
If you want to test a Java client with one of these you would do
java Main init verbose < pipe | ./agentX > pipe
Testing in two terminals
To play in two different terminals (so that we can tell who does what in an easier way) you would have to create two pipes with
mkfifo pipe1 pipe2
which you do only once.
In Terminal 1:
./agentX init verbose < pipe1 > pipe2
In Terminal 2:
java Main verbose > pipe1 < pipe2
If you run in two different terminals or directories, make sure that you use the same named pipes for both agents. That is, if agent1 writes to pipe1 (">") then agent2 must read ("<") from the same file. You can specify the full path of the pipe to make sure that you use the same pipes.
Note that if you work on for example computers that use the AFS filesystem, you cannot create named pipes like above. However, you can create your named pipes in the /tmp directory.
mkfifo /tmp/mypipe
and then replace pipe above with /tmp/mypipe
Windows users
If you want to run your code in Windows with the above technique, you can use Cygwin.
C++
If you want to be able to compile your C++ code in cygwin you should obtain the gcc-g++ package. You can find it easy with the search function on the screen that lets you select additional packages during the installation.
Java
Install the JDK on your Windows machine. In cygwin you need add the path to the java executables with something like
export PATH=\$PATH:/cygdrive/c/Program Files/Java/jdk1.7.0\_80/bin/
Advanced use
You can run your agent directly in the terminal without any pipe, for example, for debugging/testing purposes. Start the agent
./agent verbose
and then paste in a board state message in the terminal and press ENTER. When you run an agent in verbose mode you see the board state message together with the graphical representation. This what you should pass into your agent. You can also do this by putting such a message into a file (make sure to have an end of line) and do
java Main verbose < file.txt
The start state is represented by the following string:
...xxo....o....o 0_5_2 x
where the first 16 characters describe the board state, "0" says that the state is not final, "5" says that the previous player marked the cell 5, "2" says that it was the second player (player O), and "x" is the mark for the next player.
Input
You will be given a game state which consists of a board, whose turn it is, and what the last move was.
Output
Your agent program should output the next game state in the same format. This is taken care of for you by the skeleton.