Tic-tac-toe is the classic toy example for min-max search . 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:
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,_).