algorithm - mips汇编保存数据的方法

Question

我对如何解决某些问题有一些疑问。我正在尝试使用程序集设置井字游戏，并且正在尝试实现作为玩家玩的计算机。我正在寻找主要将数据保存到变量的方法，我可以附加一个变量字符串，我会在其中添加每个玩家玩过的单元格的所有变量。

我该怎么做，有没有一种方法可以创建一个数组来保存我可以动态更改和分配的信息？

Answer 1

我建议将调用堆栈用作堆栈数据结构，或者更简单地创建递归函数。

递归自然有助于对可能的移动进行详尽搜索，修剪任何导致强制丢失的分支。形式上，这称为 Minimax 搜索(寻找下一步)。 https://www.cs.cornell.edu/courses/cs312/2002sp/lectures/rec21.htm

如果您找到了获胜的一步，您将返回该事实，并且调用者知道它正在考虑的棋盘位置会让对手强制获胜。您希望您的功能避免让对手强行获胜，并采取可能导致自己强行获胜的行动(如果有的话)。例如Tic Tac Toe recursive algorithm .

---

我建议使用固定大小的数据结构来表示棋盘状态。你的好选择是

• 一个 9 字节的字符数组，例如空格、“X”和“O”(填充到 12，以便您可以使用 3x lw 复制它)。即在 C 中，struct board { alignas(4) char b[9]; };。您复制了整个结构。

• 2x 位图(一个用于 X，一个用于 O)，用于所谓的“位板”。 (在国际象棋引擎中，一个 64 位位图有一个位对应棋盘上的每个方 block 。在 3x3 井字棋中，完整棋盘只需要 9 位寄存器)。然后你可以想出 bit-hacks 来测试 3-in-a-row，比如 b & 0b111 == 0b111 (with andi and beq) 检查顶行是否都是一个标记。

  您可以通过执行 X|O 并寻找仍为零的位来找到板上剩余的空位。

• 每个位置 2 位的单个位板(总共 18 位，大于 MIPS 立即数)。通过这种方式连续查找 2 个空的第 3 个位置可能会更容易。