This project can be completed by one person or by a team of two. If you choose to work in a team, submit the names of the team members at classtime, Monday, November 20.
Stacks, linked lists, queues, and trees appear in implementations of game-playing programs. Here is a tic-tac-toe variant that gives you the opportunity to use one or more of these data structures. If you solve this assignment, you can readily apply your knowledge (and much of the solution) to more challenging games, like checkers and chess.
The playing board is 4-by-4 and starts empty:
--------------- | | | | | --------------- | | | | | --------------- | | | | | --------------- | | | | | ---------------The human player inserts X's into the board, and the computer inserts O's. The two players alternate at inserting their markers; the human plays first. For example, after 3 plays by the human and two by the computer, we might have this configuration:
current_board = --------------- | | | | | --------------- | X | X | O | | --------------- | | X | O | | --------------- | | | | | ---------------Each player tries to place three or four of her markers in a row, aligned either vertically or horizontally or diagonally. Three markers in a row score 3 points; four markers in a row score 6 points.
Play proceeds until all squares are filled; the player with the higher score at the final board configuration ``wins.''
Here is a simple example of such a formula:
strength(Board b, Player p) =
( p's current score on b )
- ( opponent's current score on b )
+ ( empty spaces adjacent to 2 of p's markers on b )
- ( empty spaces adjacent to 2 of opponent's markers on b )
The formula takes into account the current score as well as the possibility
of future scoring. The formula is a bit simplistic, but it will
do for now. Given such a formula, we can calculate the value of a
possible next move by inserting a piece into an empty space and calculating
the strength of the new board.
For example, it is O's turn to move in the above board---call the board current_board. For the record,
strength(current_board, O) = 0 - 0 + 2 - 3 = -1which suggests that the X-player has a slight advantage at this point. Let's consider two possible next moves for O and the strengths of the resulting boards:
board1 = board2 = --------------- --------------- | | | | | | | | | | --------------- --------------- | X | X | O | | | X | X | O | | --------------- --------------- | | X | O | | | | X | O | | --------------- --------------- | | | O | | | | O | | | --------------- --------------- strength(board1, O) = 3 - 0 + 1 - 2 = 2 strength(board2, O) = 0 - 0 + 3 - 2 = 1The strength formula suggests that the first move is slightly better than the second. For this reason, the O-player might take the first move.
Of course, a computer player would use the strength formula to calculate the strengths of all possible next moves before selecting a best move.
A player of any game does better if she considers how her opponent might react to her move. A computer player can be programmed to do this---the computer searches into the future two moves, that is, that for each possible O-move by the computer, all possible opponent's X-moves are calculated too. The board positions for the computer's next move and the opponent's response moves can be drawn as this search tree:
current_board (as above)
next / | \
possible
O moves: board1 board2 .... board11
/ ... \ / ... \ / ... \
possible X
responses: b1_1 ... b1_10 b2_1 ... b2_10 b11_1 ... b11_10
The tree shows that,
given the current board situation, there are 11 possible
next moves for O. (Why 11 possible next moves? Look again at
current_board---there are 11 empty spaces.)
For each possible O-move, X might respond in
10 different ways.
This means there are 11*10 = 110 possible boards to consider.
Obviously, it is best for computer player, O, to make a move now that is likely to lead it to a strongest board position two moves from now. This requires that the computer player search the above space of all possible 2-move sequences and calculate the strength values of all the resulting boards.
Here is a crude algorithm for doing this:
total_strength_for_move_K = strength(bK_1, O) + strength(bK_2, O)
+ .... + strength(bK_N , O)
average_strength_for_move_K = total_strength_for_move_K / N
The computer player can be made even smarter by searching into the future for the next 3 moves. Then, the computer player selects the move that leads to the strongest board position three moves from now. The search tree gets larger still:
current_board (as above)
next / | \
possible
O moves: board1 board2 .... board 11
/ ... \ / ... \ / ... \
possible X
responses: b1,1 ... b1,10 b2,1 ... b2,10 b11,1 ... b11,10
/...\ /...\ /...\ /...\ /...\ /...\
possible
O moves: 1***9 1****9 1****9 1****9 1****9 1****9
But the same principle lies underneath: generate all the
3-move sequences, calculate the resulting board strengths, and
select as the next move the one whose average board strength is
maximal in 3 moves.
Of course, a search of 4- or 5-move sequences will be even better, but ultimately, the time it takes the computer to search the sequences slows down the game and frustrates the human player. Also, a computer that searches far into the future may be such a good player that the human almost always loses! For this reason, computer games come with ``skill levels.'' A skill level is basically a limit on the length of the sequence of moves that is searched by the computer when it must move.
You should build the game in stages; complete each stage before starting the next:
A pretty graphical interface is not required; it is acceptable to have input and output handled in the command window. (If you want to use a graphical interface, this is fine, but don't spend a lot of time on it, because your grade will not be based on the interface.)
After experimenting with this version of the game, improve the strength function so that the computer player plays better. (The strength function defined earlier is too simplistic to help the computer play well in the initial rounds of the game.)
This step is most interesting, because you will have to save in the data structure (stack or queue or ... ) objects of this format:
class MoveSequence
{ private MoveList proposed_sequence_of_moves;
private Board board_after_the_proposed_sequence_of_moves;
...
}
You might review the travelling-salesman assignment to see how
objects like this can be saved in a data structure, like a stack.
For this assignment, a queue might be more appropriate, however.
Create the .jar file, Project.jar, and submit at http://www.cis.ksu.edu/classes/300/Assign/submit.html.