Prolog中的游戏树模对称性 [英] Game Tree modulo Symmetry in Prolog
问题描述
让我们为井字游戏设计一个游戏树.如何有人会在 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
推荐答案
使用算法的改编here,我获取
一个更短的解决方案,只有 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.
井字游戏的 Prolog 代码
通过 findall 得分,返回随机获胜策略
通过对称减少移动次数
https://gist.github.com/jburse/928f060331ed7d5307a0d3fcd6d4aae9#file-tictac4-请
这篇关于Prolog中的游戏树模对称性的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!