Prolog中的博弈树模对称 [英] Game Tree modulo Symmetry in Prolog

问题描述

让我们为 Tic-Tac-Toe 设计一个游戏树.如何有人会在 Prolog 中计算这个结果吗:

Lets work out a game tree for Tic-Tac-Toe. How would one compute this result in Prolog:

考虑8种对称性，假设计算机(X)启动并播放确定性，那么只需要 49 个表条目！

Taking the 8 symmetries into account, and assuming computer (X) starts and plays deterministic, then only 49 table entries are needed!

• 1 个空板条目
• 2 件 5 个条目
• 4 件 21 个条目
• 18 个条目，共 6 件
• 8 个条目 4 个条目

https://stackoverflow.com/a/61298546/502187

推荐答案

使用算法的改编这里，我得到
只有 37 个游戏位置的更短的解决方案:

Using an adaptation of the algorithm here, I get
a shorter solution with only 37 game positions:

?- init(X), best(X, x, L, W), 
   findall(Z, inside(L, Z), A), 
   sort(A, B), length(B, N).
B = [[[-, -, -], [-, x, -], [-, -, -]], [[x, -, o], 
[-, x, -], [-, -, -]], [[x, -, o], [-, x, x], [-, -, o]], 
[[x, o, -], [-, x, -], [-, -, -]], [[x, o, -], [-, x, -], 
[-, o, x]], [[x, o, -], [-, x, -], [x, -, o]], [[x, o, -], 
[-, x, o], [-, -, x]], [[x, o, -], [-, x, x], [o, -, -]], 
[[x, o, -], [o, x, -], [-, -, x]], [[x, o, o], [-, x, -], 
[-, -, x]], [[x, o, o], [-, x, -], [x, -, -]], [[x, o, o], 
[-, x, o], [x, -, x]], [[x, o, o], [-, x, x], [-, -, -]], 
[[x, o, o], [-, x, x], [o, x, -]], [[x, o, o], [-, x, x], 
[x, o, -]], [[x, o, x], [-, x, -], [o, x, o]], [[x, o, x], 
[-, x, -], [x, o, o]], [[x, o, x], [o, x, -], [o, -, x]], 
[[x, o, x], [o, x, -], [x, -, o]], [[x, x, -], [-, x, o], 
[o, o, x]], [[x, x, -], [-, x, o], [o, x, o]], [[x, x, -], 
[o, x, -], [o, x, o]], [[x, x, -], [o, x, o], [o, -, x]], 
[[x, x, o], [-, x, -], [o, -, -]], [[x, x, o], [-, x, -], 
[o, o, x]], [[x, x, o], [-, x, -], [o, x, o]], [[x, x, o], 
[-, x, o], [-, o, x]], [[x, x, o], [-, x, o], [o, x, -]], 
[[x, x, o], [o, x, -], [-, x, o]], [[x, x, o], [o, x, -], 
[o, x, -]], [[x, x, o], [o, x, o], [-, x, -]], [[x, x, o], 
[o, x, o], [x, o, x]], [[x, x, o], [o, x, x], [o, x, o]], 
[[x, x, o], [o, x, x], [x, o, o]], [[x, x, o], [x, x, o], 
[o, o, x]], [[x, x, x], [o, x, -], [o, -, o]], 
[[x, x, x], [o, x, o], [o, x, o]]],
N = 37 

但是由于 best/4 使用 random_member/2 来做出选择
确定性的，通过重新运行，得到的结果也会更长.

But since best/4 uses random_member/2 to make the choice
deterministic, by rerunning, one gets also longer results.

井字游戏的序言代码
通过findall得分，返回随机获胜策略
通过对称减少移动次数
https://gist.github.com/jburse/928f060331ed7d5307a0d3fcd6d4aae9#file-tictac4-pl"请

这篇关于Prolog中的博弈树模对称的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！