Brock University
Department of Computer Science

Fall 2011 Instructor: Vlad Wojcik

Assignment # 2: Due 07 Nov 2011, 4 PM.

THE PROBLEM: A serious game of Tic-Tac-Toe

As children, probably all of us have played a game of Tic-Tac-Toe. It is a simple game, played on a 3x3 grid. Two players take turns and put Xs and Os correspondingly on the nine fields of the grid. The player who gets first three of his marks aligned (horizontally, vertically, or diagonally) wins.

We will play a generalized game of NTTT, played on a NxN grid (where N > 2). As before, players strive to align their marks, but this time the game is played until all fields of the grid are taken. Only then the values of alignments are tallied and the winner is declared.

The NTTT game is a generalization of 3TTT, but is a bit more complicated.

Consider the snapshot beside of a the game of 6TTT. Both Xs and Os made five moves. Who is ahead?

That depends how we count the values of each alignment. Specifically:

1. If we decide that each alignment is of equal value, then clearly Os lead, having secured two alignments, while Xs have one;
2. If we decide that the value of each alignment equals the number of tokens (i.e. Os or Xs) in the alignment, then currently the game is at a draw (Xs have one alignment of value 5, while Os have two alignments of values 2+3);
3. However, we may agree that making a longer alignment is markedly more difficult than making a short one. Perhaps we should decide that the value of an alignment of n tokens is 2**(n-1), i.e. the value of an alignment of two tokens is 2, the value of three aligned tokens is 4, and five aligned tokens are valued at 16... In that case Xs clearly lead, having earned 16 points, while Os have only 6 points...

We conclude here that there are infinitely many games of NTTT possible, because there are infinitely many values of N > 2, and there are infinitely many ways of evaluating the alignments.

THE PROGRAM:

Write a C++ or an Ada 2005 program (supported by a brief design document) that would play any game of NTTT. This program should consist of two parts: the main program and the game playing thread or task. The main program would provide a simple (ASCII) interface to the user, while the thread / task would "think" about the strategy, regardless whether it is its turn to move or not. This approach may enhance the interactivity of the game, as NTTT may be pretty CPU hungry for large N.

Upon launching the game, the main program would ask the user for the value of N, level of difficulty D (being the number of plies in the game tree), who is to go first, and what alignment evaluation function is to be used. Having gotten these answers, the main program should launch a suitable game playing thread / task. That thread / task should have three determinants (the value of N, the difficulty level D, and whether it goes first). That thread / task should also be generic: it should accept an alignment evaluation function as a generic parameter.

The main program should be responsible for:

* The dialogue with the human player;
* The dialogue with the game playing task;
* Displaying simple (ASCII) game interface, showing the state of the grid;
* Tallying the alignments for both players as game progresses;
* Announcing the winner;
* Terminating the game when needed.

The game playing thread / task should be responsible for:

* Accepting the moves of a human player (communicated to it by the main program);
* Informing the main program about its moves;
* Playing the NTTT game using any of the three alignment evaluation functions mentioned above, with possibility of introducing new such functions later;
* Being as responsive as possible: "thinking" about its likely next move while attentively waiting for the next human move.

SUBMISSION FORMAT:

Both hardcopy (paper) and electronic submission is required.

Hardcopy submission: Your submission envelope with the standard Cover Page should contain all relevant printouts and supporting documentation, demonstrating your design and flawless behaviour of your program. The envelope should be dropped in the submission box on or before deadline date / time.

Electronic submission: Please create a directory on Sandcastle and place within it all the files (and only the files) to be submitted. To submit issue the command submit3f00, which is interactive in its nature. Obviously, you are allowed to submit your assignment only once. Should you encounter difficulties, please report them to Mr. Cale Fairchild.

Similarly, the electronic submission should be performed on or before deadline date / time.

PENALTIES:

Possible lateness in assignment submission is counted in days, each period of a day ending at 4 PM. The penalty for late submission of assignments is 25% up to three days (or a part of a day). After that period the penalty is 100%.

While honest cooperation between students is considered appropriate, the Department considers plagiarism a serious offense. For clarification on these issues you are directed to the statement of Departmental Policies and Procedures.

Instructor: Vlad Wojcik
Revised: 1 November, 2011 10:31 PM
Copyright © 2011 Vlad Wojcik