minimax for tic-tac-toe

Question

I'm trying to solve tic-tac-toe with a simple minimax algorithm. Simple, but should cover a lot of the language. What I have so far:

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

The win condition is then basically: win(Player, [X1,X2,X3|_]) :- X1==Player,X2==Player,X3==Player. etc for all eight variants. draw is just a simple check whether all variables are bound.

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

Now I can generate all possible moves by simple backtracking: move(Player, Board, X, Y). which should basically be all what I need for minimax (obviously a simple utility function that returns 1 if the computer wins, 0 in case of a draw and -1 if the human wins, that's easy). I just have no idea how to implement it and all examples I find on the net are rather complicated and not well explained.

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

Answer 1

Well, as you already have your move/4 predicate, I would start with collecting all moves that are possible:

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

And then it's simply a matter of assessing each move, isn't it? For that I would write a predicate like board_player_move_value/4 that, given a board and a move of a given player, determines how good the move is for this player. It is this predicate that likely depends on further moves that are possible (for the other player) at this stage, and this is where minimax takes place. For example, if this move wins the game, it's a good move. If the other player can win in the next move, it's a bad move etc. I would use this predicate to build a collection of terms of the form Value-Move, use keysort/2 to sort them, and then pick one of the moves with the best value, where "best" depends on whether I'm trying to find a move for the minimizing or the maximizing player.