Precompute arbitrary Winning Strategy in Prolog

Question

Lets say we have the Tic-Tac-Toe game at hand. And we want to precompute a winning strategy in the following way as a tree. From the winning moves only one is select and stored in the tree.

The many loosing moves the opponent has, all are stored in the tree, so that we can blindly use the tree to guide us to our next winning move, which is than again only one in the tree,

       /
  o---*- ..
       \     /
        o---*- ..
             \

and so on, one, multiple, one, multiple etc.. How would one do this in Prolog so that computing one such tree can be done quite quickly for Tic-Tac-Toe game and a given start configuration?

Miculek

The tree you describe shows the evolution of all possible games. However, it contains high amount of duplication (state of the game after A-B-C-D is the same than after C-D-A-B). Tic-tac-toe has only 3^9=19k different states, less if we consider symmetries. – Nitpicking

N = 37 is enough, see here https://mcmap.net/q/1166067/-game-tree-modulo-symmetry-in-prolog . Maybe even less? – Miculek

Answer 1

I would do it like this (adapting from min max):

My choices are white nodes, other player's choices are black nodes.

• Form a solving tree depth-first.
• If the game has ended mark this leaf as won, tie or lost.
• If a black node is not a leaf and all of its children are marked: "keep" all childnodes, mark the node as the worst cenario from its children (lost before tie before won)
• If a white node has only one child left: copy the marking.
• If a white node has one marked child which is maked as won, ignore the left over unmarked child-nodes (no traversing necessary). Mark as won.
• If a white node has two marked children: keep only the best child, prefer won over tie over lost. If the mark is won or there are no unmarked nodes left the 2 above rules hold. Otherwise traverse an unmarked child to repeat this process.
• the marking is only important for the minmax, not for the choice-tree.
• for every childnode store the move to reach it
• form the final tree as nested list (while traversing the tree)

Output would look like this:

[[1,
   [2,[4,
         [3,[..],[..]],[5,[3,[..],[..],[..]]]
         ]],
   [3,[4,[5,..],[2,..]]],
   [4,..],
   [5,..]
]]

I start and have only one option: using move 1. Then black has the options 2, 3, 4 and 5, where these are all possible moves for black. If he chooses 2, I choose 4. Black now has option 3 and 5. If he chooses 5, I choose 3 and so on. Be sure to have enough RAM available ;)

Houdini

Can it be done with answer set programming (ASP) ? – Miculek

@MostowskiCollapse I guess so because graphs are easier to handle (in my oppinion), assuming you want to have a precomputet graph and not a tree – Houdini

I am fine with graphs, a tree is a special case of a graph. So who would object to graphs? – Miculek

@MostowskiCollapse you might know this xkcd comic already? – Houdini

N = 37 is enough, see here https://mcmap.net/q/1166067/-game-tree-modulo-symmetry-in-prolog . Maybe even less? – Miculek

Answer 2

Here is some proof of the pudding. One can use aggregate_all/3 for min/max, here is a little adaptation of the code here. But the code below does not yet return a winning strategy. It only returns a first move and a score:

% best(+Board, +Player, -Move, -Score)
best(X, P, N, W) :-
  move(X, P, Y, N),
  (win(Y, P) -> W = 1;
    other(P, Q),
    (tie(Y, Q) -> W = 0;
     aggregate_all(max(V), best(Y, Q, _, V), H),
     W is -H)).

We can check the moves and scores we get for a position:

?- best([[x, -, o], [x, -, -], [o, -, -]], x, N, W).
N = 2,
W = -1 ;
N = 5,
W = 1 ;
N = 6,
W = -1 ;
N = 8,
W = -1 ;
N = 9,
W = -1

Now how would we go about and store a winning strategy and choose a winning strategy? One idea here is now to replace the aggregate_all/3 by a findall/3. This should give us the multi branches of a winning strategy:

% best(+Board, +Player, -Tree, -Score)
best(X, P, N-R, W) :-
  move(X, P, Y, N),
  (win(Y, P) -> R = [], W = 1;
    other(P, Q),
    (tie(Y, Q) -> R = [], W = 0;
     findall(M-V, best(Y, Q, M, V), L),
     max_value(L, -1, H),
     (Q == x ->
         filter_value(L, H, J),
         random_member(U, J),
         R = [U];
         strip_value(L, R)),
     W is -H)).

We use random_member/2 for the single branches. Rerun to get different correct results:

?- best([[x, -, o], [x, -, -], [o, -, -]], x, N, W), W = 1.
N = 5-[2-[6-[]], 6-[9-[]], 8-[9-[]], 9-[6-[]]],
W = 1 ;
No

?- best([[x, -, o], [x, -, -], [o, -, -]], x, N, W), W = 1.
N = 5-[2-[8-[6-[9-[]], 9-[6-[]]]], 6-[9-[]], 8-[6-[]], 9-[6-[]]],
W = 1 ;
No

Open source:

Prolog code for the tic-tac-toe game
score via aggregate, return first move
https://gist.github.com/jburse/928f060331ed7d5307a0d3fcd6d4aae9#file-tictac2-pl

Prolog code for the tic-tac-toe game
score via findall, return random winning strategy
https://gist.github.com/jburse/928f060331ed7d5307a0d3fcd6d4aae9#file-tictac3-pl

Miculek