c - 在 TIC TAC TOE 游戏中生成下一步 Action 的最快方法

Question

在 X 和 0 的游戏中(即 TIC TAC TOE(3X3))，如果您为此编写程序，则可以快速地由计算机生成走法。我的意思是这应该是最快的方法。

当时我所能想到的就是将所有棋盘配置存储在一个哈希中，以便获得最佳移动位置是一个 O(1) 操作。
每个棋盘格可以是 0,1 或 2。
0 代表空方 block 。 1 代表 X & 2 代表 0。

所以每个方格都可以用这三个中的任何一个填充。大约有 3^9 板配置。

简单来说，我们需要一个大小为 3^9 的散列。对于哈希，我们可以使用 base 3 表示。意味着基数 3 中的每个数字将有 9 位长，每个数字对应于每个方 block 。要在散列中搜索，我们需要找到这个 9 位数字的十进制表示形式。现在，每个方 block 都可以与行号和列号相关联。为了唯一地识别每个正方形，我们可以再次使用基数 3 表示。假设 SQ[1][2] 将以 3 为底数为 12，相当于十进制的 5。

因此，我们有效地设计了一种算法，该算法的速度足以在 O(1) 中计算出下一步。

但是，面试官坚持要降低空间复杂度，因为DOS系统没有那么大的内存。

我们如何在不改变时间复杂度的情况下降低空间复杂度？
请帮助我，以免我以后错过此类问题。

Answer 1

对于像这样的小游戏，另一种解决方法是预先计算潜在的游戏树并将其存储在表中。

首先看人类开始的情况，她显然有 9 个不同的开始位置。一个游戏表将包含 9 个入口点，然后每个入口点都指向正确的响应 - 您可以使用 this question 中概述的指南计算响应 - 以及人类响应的下一级表。这次只有 7 种可能的回答。对于下一个级别，将有 5 个，然后是 3 个，然后只有 1 个。表中总共将有 9 * 7 * 5 * 3 * 1 = 945 个条目，但是可以通过实现对称性(即旋转)来压缩和翻转的颜色。

当然，计算机启动的情况原则上是相似的，但 table 实际上更小，因为计算机可能希望从播放中间部分开始 - 或者至少避开某些位置。