预计算Prolog中的任意获胜策略 [英] Precompute arbitrary Winning Strategy in Prolog

问题描述

可以说我们手边有井字游戏.我们想要以树的形式预先计算出获胜策略.从获胜的举动中，只选择一个并存储在树中.

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---*- ..
             \

等等，一个，多个，一个，多个等.一个在Prolog中执行此操作，以便可以计算一棵这样的树井字游戏和给定的开始配置是否很快?

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?

推荐答案

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

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

我的选择是白色节点，其他玩家的选择是黑色节点.

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

• 形成深度优先的求解树.
• 如果游戏结束，则将此叶子标记为 won ， tie 或 lost .
如果黑色节点不是叶子并且其所有子节点都被标记为:"keep"，则为"keep".所有子节点，将节点标记为其子节点中最差的情况(在 tie 之前在 won 之前 lost )
• 如果白色节点只有一个孩子左:请复制标记.
• 如果一个白色节点具有一个标记为的子节点，并且被标记为 won ，则忽略剩余的未标记子节点(无需遍历).标记为 won .
• 如果一个白色节点具有两个标记的子代:仅保留最好的子代，则优先选择 won 而不是 tie 而不是 lost .如果标记是 won 或没有留下未标记的节点，则上述2条规则成立.否则，遍历未标记的孩子以重复此过程.
• 标记仅对minmax重要，对选择树不重要.
• 为每个子节点存储达成目标的举动
• 将最后一棵树作为嵌套列表(遍历树)

• 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)

输出看起来像这样:

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

我开始并且只有一个选择:使用move 1 .然后，黑色具有选项 2 ， 3 ， 4 和 5 ，这些都是黑色的可能移动方式.如果他选择 2 ，我选择 4 .黑色现在具有选项 3 和 5 .如果他选择 5 ，我选择 3 ，依此类推.确保有足够的可用内存；)

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 ;)

这篇关于预计算Prolog中的任意获胜策略的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！