2

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

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

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

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

因此，我们有效地设计了一种算法，该算法足够快以计算 O(1) 中的下一步动作。

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

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

4

4 回答 4

3

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

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

当然，电脑启动的情况原则上是相似的，但桌子实际上更小，因为电脑可能会想从播放中间部分开始 - 或者至少避免某些地方。

于 2012-06-15T21:20:30.190 回答
1

没有 3^9 种不同的板配置。正如 tomdemuyt 所说，有 9 个！不同的棋盘配置，即先有9个选择，然后有8个选择，之后有7个选择，以此类推。

此外，我们可以通过考虑对称性来进一步降低空间复杂度。例如，对于第一步，在 [0,0] 中放置 X 与在 [0,2]、[2,0] 和 [2,2] 中放置 X 相同。我相信这减少了9！到 9!/4

我们甚至可以通过计算在最后一步（第 9 步）之前哪些棋盘配置获胜来减少这种情况。我不知道号码，但可以在 Stack Overflow 表弟http://en.wikipedia.org/wiki/Tic-tac-toe上找到详细说明

于 2012-06-15T21:11:53.083 回答
0

3^9 的假设是错误的。例如，这将包括一个只有 X 的棋盘，这是不可能的，因为两个玩家每轮都放置一个 X 或一个 O。

我最初的想法是有 (9*8*7*6*5*4*3*2) * 2 种可能性。第一个玩家有 9 个选择，第二个玩家有 8 个选择，第一个玩家有 7 个等等。我放 * 2 因为你可能有不同的最佳动作，具体取决于谁开始。

现在 3^9 是 19863 和 9！是 362880，所以显然这不是更好的解决方案，许多“不同的场景”实际上最终看起来完全一样。尽管如此，许多 19863 板设置无效的基本想法仍然存在。

这段代码可能可以用一个简单的公式代替，它告诉我这是你想要移动的位置数。

<script>

a = permuteString( "X........" ); document.write( Object.keys(a).length + "<br>" );console.log( a );
a = permuteString( "XO......." ); document.write( Object.keys(a).length + "<br>" );console.log( a );
a = permuteString( "XOX......" ); document.write( Object.keys(a).length + "<br>" );console.log( a );
a = permuteString( "XOXO....." ); document.write( Object.keys(a).length + "<br>" );console.log( a );
a = permuteString( "XOXOX...." ); document.write( Object.keys(a).length + "<br>" );console.log( a );
a = permuteString( "XOXOXO..." ); document.write( Object.keys(a).length + "<br>" );console.log( a );
a = permuteString( "XOXOXOX.." ); document.write( Object.keys(a).length + "<br>" );console.log( a );

//Subset of the Array.prototype.slice() functionality for a string
function spliceString( s , i )
{
    var a = s.split("");
  a.splice( i , 1 );
    return a.join("");
}

//Permute the possibilities, throw away equivalencies
function permuteString( s )
{
    //Holds result
    var result = {};

    //Sanity
    if( s.length < 2 ) return [];

    //The atomic case, if AB is given return { AB : true , BA : true }
    if( s.length == 2 )
    {
        result[s] = true;
        result[s.charAt(1)+s.charAt(0)] = true;
        return result;
    }

    //Enumerate
    for( var head = 0 ; head < s.length ; head++ )
    {
        var o = permuteString( spliceString( s , head  ) );
        for ( key in o )
            result[ s.charAt( head ) + key ] = true;
    }
    return result;
}


</script>

这给出了以下数字： 第 1 步：9 第 2 步：72 第 3 步：252 第 4 步：756 第 5 步：1260 第 6 步：1680 第 7 步：1260

所以总共 5289 步，这甚至没有检查已经完成的游戏或对称性。

这些数字允许您通过数组查找移动，您可以通过循环所有可能的游戏来自己生成这个数组。

T。

于 2012-06-15T20:53:38.627 回答
0

Tic Tac Toe 游戏非常简单，优化算法可以由 Tinker Toys（一种棍子和紧固件品牌）制造的机器实现。由于这种结构所封装的硬件复杂性水平低于 1970 年代典型的微处理器，所以在大多数情况下，找出已经进行了什么动作所需的时间将超过找出下一步动作所需的时间。可能最简单的方法是有一个表格，根据给定玩家的标记（2^9，或 512 个条目）的存在或不存在，将指示哪些方格会将两行转换为三行一行。首先查找移动中玩家拥有的棋子；如果任何可以完成三连胜的方格未被对手占据，则将其占据。否则查找对手的棋子组合；任何出现的尚未被占用的方格都必须被占用。否则，如果该中心可用，则接受它；如果只取中点，则取角。否则占优势。

向 4x4x4 Tic Tac Toe 提出问题可能会更有趣，因为这代表了足够的复杂性，以至于 1970 年代的计算机实现通常每次移动需要很多秒。虽然今天的计算机比 Atari 2600 等计算机快数千倍，但计算水平至少超出了微不足道的水平。

如果将游戏扩展到 4x4x4，那么在速度、RAM 和代码空间之间进行权衡会有很多可能性。与有 8 条获胜线的原始游戏不同，4x4x4 版本有 (IIRC) 76。如果一个人跟踪每条线处于 8 个状态之一[如果一个人获胜则为 10 个]，并且对于每个空方格，一个人跟踪通过它的获胜线有多少处于什么状态，应该可以根据该信息制定一些非常快速的启发式方法。可能有必要使用穷举搜索算法来确保启发式算法实际上会获胜，但是一旦验证了启发式算法，它们应该能够比穷举搜索运行得更快。

于 2014-04-20T21:35:25.350 回答