This tutorial uses Tic-Tac-Toe (or Naughts and Crosses, for those who prefer the Queen's English) to illustrate the min-max game strategy. It serves to jump start the Othello project.
Copy the package
~comp212/public_html/01-spring/labs/12/TicTac/
and the directory
~comp212/public_html/01-spring/labs/12/players/
into your own directory.
The design of this program is the same as that of the Othello program.
To see how the application behaves, compile
DumbPlayer.java
, and run the command
java DumbPlayerPlay against
DumbPlayer
to see if you can beat it!
Now run SmartPlayer0
and play against it.
(No, we didn't provide the course code for this.)
You probably will notice a non-trivial delay in the first move.
SmartPlayer0
uses the min-max strategy to search and evaluate
the full game tree in order to make its moves.
This is why the first move is slow.
This tutorial will lead you through the process of coding
SmartPlayer.java
to implement the min-max strategy as
illustrated by SmartPlayer0
.
Here again is the min-max strategy discussed in class.
Let's call the players John and Mary. When John is to make a move, we assume he will moves in a way that is best for him. What's best for John is based on some numerical value that he associates with each of next possible moves. As John considers all the possible futures, the possible board positions represent nodes in a game tree. How are the value of each board position calculated? Here is one such possible computation.
For each of the leaf of the game tree, John assigns a value of 1 if he wins, 0 if he ties, and -1 if he loses. I.e., he defines a pay-off function P:
Now, John assigns values to interior nodes:
To implement the above, for the sake of speed, we copy much
of the functionality of TTEngine.java
,
the logic of playing Tic-Tac-Toe into SmartPlayer.java
.
What you need to do is to study the code for the method
NextMove(...)
and fill in the code for
>eval(...)
.
Exercises:
Examine the code and comments inside of eval(...)
and complete it.
NOTE:
SmartPlayer.eval()
returns an int
representing the min-max value. SmartPlayer.NextMove()
then has to recompute some of the min-max values again to find
the move whose min-max value matches with best min-max value found.
This is unnecessary because we can compute the min-max value and keep
track of the move yielding the best min-max value in the same computation.
SmartPlayer2.eval()
shows how this is done.
In order to avoid playing the same sequence of moves in
different games, write the code for the method
randomize
to randomize the array (OK, so it's really
a Vector
) of legal moves.
Look at the code in DumbPlayer.java
to see how
this can be done.