代码之家 › 专栏 › 技术社区 › Mostowski Collapse ninesided

如何在Prolog中预计算制胜策略

game-engine prolog search

Mostowski Collapse ninesided · 技术社区 · 4 年前

假设我们手边有井字游戏。我们想要从获胜的移动只有一个是选择和存储在树中。

下一个获胜的动作,又是树上唯一的一个,

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

在Prolog中这样做,这样就可以计算一棵这样的树相当快的井字游戏和给定的开始配置?

0 回复 | 直到 4 年前

DuDa William Halliday 4 年前

我会这样做(从min-max改编):

我的选择是白色节点,其他玩家的选择是黑色节点。

如果游戏结束了,把这片叶子标记为 won , tie 或 lost .
如果黑色节点不是叶子,并且其所有子节点都标记为“keep”all childnodes,则将该节点标记为其子节点中最差的cenario( 迷路的 领带 之前 赢了 )
如果白色节点 :复制标记。
一个标记 化作 ,忽略剩余的未标记子节点(无需遍历)。标记为 赢了 .
如果白色节点 赢了 结束结束 迷路的 赢了 或者没有未标记的节点保留上述2条规则。否则,遍历未标记的子对象以重复此过程。
将最终的树形成嵌套列表(遍历树时)

输出如下所示:

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

我一开始只有一个选择:使用move 1 . 那么布莱克就有选择了 2 , 3 , 4 和 5 ,这些都是黑人可能的举动。如果他愿意的话 2. ,我选择 4. 3. 和 5. . 如果他愿意的话 ,我选择 3.

Mostowski Collapse ninesided 4 年前

这是布丁的一些佐证。可以将aggregate\u all/3用于min/max,下面是对代码的一点修改 here . 但是下面的代码还没有返回一个成功的策略。它只返回第一步和分数:

% 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)).

?- 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

现在,我们该如何着手,存储一个成功的策略,并选择一个成功的策略?这里的一个想法是用findall/3替换聚合的\u all/3。这应该给我们一个成功策略的多分支:

% 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)).

我们对单个分支使用随机\成员/2。重新运行以获得不同的正确结果:

?- 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

开源:

井字游戏的Prolog代码
通过聚合得分,返回第一步
https://gist.github.com/jburse/928f060331ed7d5307a0d3fcd6d4aae9#file-tictac2-pl

https://gist.github.com/jburse/928f060331ed7d5307a0d3fcd6d4aae9#file-tictac3-pl