tictac Test Program

Tic-tac-toe is the classic toy example for min-max search [13]. The search space of the game is small enough so that a full depth search can be deployed. End positions in the game can be valued -1, 0 and +1 depending on whether the opponent wins, a tie has been reached or the current player wins.

Since the valuation is tri-state we have implemented the min-max search via negation. The predicate best/3 should indicate that from the given position there is a move that puts the given player in a position with a winning strategy. This can be used to play the game. We can for example pose the following query and will get the following answers:

      ?- best([[x,o,-],[-,x,-],[-,-,o]], x, X).
  X = [[x, o, -], [x, x, -], [-, -, o]] ; X = [[x, o, -], [-, x, -], [x, -, o]] ; No

We can easily verify that the computed positions are indeed winning positions:

Picture 16: Search Tree Excerpt

In one test iteration we will verify that from start the first player has no winning strategy. This can be verified in that the following query fails:

      ?- init(X), best(X,x,_).