Logic Programming

Nine Board Tic Tac Toe

Nine Board Tic Tac Toe is a variant of Tic Tac Toe played on nine boards arranged in a 3x3 grid. The first player's can go anywhere on the board; all moves thereafter are placed in empty spaces on the board corresponding to the square filled on the previous move. For example, if a mark is placed in the upper-left square of a board, the next mark must be placed in some cell of the upper-left board. If a player cannot move because the indicated board is full, the next move may go on any board. Victory is attained by getting three in a row on any board. This makes the game considerably longer and more involved than Tic Tac Toe, with a definite opening, middle game, and endgame.

A sample state of the game is pictured below. As you can see, the X and O players have each made several plays. It is X's turn to play, and he is required to in the middle board on the left.

To describe this game, we can use the symbols x, o, and blank to represent marks on the board (the two players and the "empty mark"), and we use the digits 1, 2, 3 as indices for row and columns of cells and rows and columns of sub-boards.

We use a single 5-place predicate location to represent the state of the board. For example, the sentence cell(1,2,3,1,x) means that the board in the first row and second column contains an x in its third row and first column. We use the binary predicate current to designate the current board. For example, the sentence current(2,3) means that the board in the second row and third column is current. We use the unary predicate control to describe whose turn it is to play. For example, the sentence control(x) means it is X's turn to play.

In addition to this basic vocabulary, we use the 4-ary operator mark to represent a move in the game. The action mark(1,2,3,1) refers to the action of placing the mark of the player in control in the third cell and first column of the board in the first row and second column.

Your task on this assignment is to define the effects of the mark operation on cell, current, and control.

To make things easier for you, we have created a specialized editor for game rules. Click here to load the editor. This one looks like the usual game, but it contains some additional features to help you with your work.

Below the sheet on the left is a box that shows the data corresponding to the current state of the game. As you move, the data in this box changes. Note that you cannot modify this data directly. You can change it only by clicking in cells.

Below the sheet on the right is a box containing the rules defining the mark operation (initially empty). Unlike the situation with the data box, you can modify the rules shown here. Simply click in the box and enter your rule set. Once you are happy with your rule set, click Save and the new rules will take effect.