Minimax for tic-tac-toe

Question

I am trying to solve tic-tac-toe with a simple minimax algorithm. Simple, but should cover a lot of language. What I still have:

The board is presented as an array of 9 (unrelated) variables that are either set to x or o .

The winning condition in this case is mainly: win(Player, [X1,X2,X3|_]) :- X1==Player,X2==Player,X3==Player. etc. for all eight options. draw simply checks if all variables are bound.

The move offers are also simple: move(Player, [X|_], 0, 0) :- var(X), X=Player. again for all possible positions (I will leave code reuse for a later program :)).

Now I can generate all possible moves with a simple backtrace: move(Player, Board, X, Y). , which should basically be all that I need for minimax (obviously, a simple utility function that returns 1 if the computer wins, 0 in the event of a tie and -1 if the person wins, this is easy). I just don’t know how to implement it, and all the examples that I find on the network are quite complex and not entirely clear.

Note. I'm fine with n ^ 2 or worse runtime behavior - it's really not about efficiency. And yes, I know how to write minimax in lisp, python, java - I just don’t know how to "port" this code to the prolog.

Answer 1

Well, since you already have the move / 4 predicate, I would start by collecting all the possible moves:

findall(XY, move(Player, Board, X, Y), Moves)

And then it's just a matter of evaluating each move, isn't it? To do this, I would write a predicate like board_player_move_value/4 , which, given the board and the course of this player, determines how good it is for this player. It is this predicate that probably depends on further moves that are possible (for another player) at this stage, and it is here that minimax occurs. For example, if this move wins the game, this is a good move. If the other player can win the next turn, this is a bad move, etc. I would use this predicate to create a set of terms of the Value-Move form, using the keysort / 2 key sorting for this, and then select one of the steps with the best value, where “better” depends on whether I try to find a move for minimizing or maximizing player.