如何在井字游戏中设置表格的分数？

Question

我有表和Generate_moves（）等一些函数，但最低运算法则工作，我需要设置表的分数，使计算机选择最好的表。

 public int Score() 
     { 
      if (Turn == "X") 
      { 
       if (gameWon("X")) return 100; 
       if (gameWon("O")) return -100; 
       if (gameDrawn()) return 0; 

       return n - canWin("X"); 
      } 

      if (Turn == "O") 
      { 
       if (gameWon("O")) return 100; 
       if (gameWon("X")) return -100; 
       if (gameDrawn()) return 0; 

       return n - canWin("O"); 
      } 

      return -1; 
     } 

我canWin(string)返回一个数字，告诉我，我有多少两个X或O都在直线或列，但我怀疑这是一个伟大的，为什么要设置表的分数。

如果我有表：

X - X 
0 X 0 
- - 0 

比分应该是一样的

X - - 
0 - X 
0 0 X 

和应大于

X - X 
0 - - 
- 0 - 

而且我没有任何想法如何让分数功能告诉我不同​​的分数。我如何实现方法Score来告诉我这个？

编辑：

如果计算机是先用X和我带O

X - -  X - -  X - -  X - - 
- - - -> 0 - - -> 0 X - -> 0 X - 
- - -  - - -  - - -  - - 0 

现在我怎样才能使计算机选择下一个最好的选择是

X - X 
0 X - 
- - 0 

Answer 1

Tic- Tac-Toe对于电脑来说是一个相对容易的游戏 - 因为branch factor和可能性的数量相对较小，因此：最好是创建最简单的[计算]可能的音调抽象函数，并让minmax达到最深的水平，即游戏树的叶子，这些都是一定的胜利/损失/平局。

如果你还在寻找一个启发式的，你可以使用number of rows/cols/diagonals with exactly 2 "X"s and left square is empty

尽管如此，我仍然认为[这一特定问题]一个极小极大算法返回-1损失，1胜0所有其他可能性会更好 - 因为它可以更快地达到游戏的叶子，因此在任何启发式的情况下都会更加明了。

Answer 2

其中一种可能性... Score =剩余路数（仍然可以填充到获胜状态的行数，列数或对角数）为x获胜 - 每个状态不是叶子（最终状态） 对于叶子状态你只有分数= 1,0或-1

Answer 3

我认为你是过于复杂的事情。有少40万可能井字棋游戏 - 事实上，井字棋是很简单的，你可以记下每一个可能的游戏中最好的移动在纸张

单张纸

即使像minmax这样简单的算法也是矫枉过正的 - 只需通过蛮力检查所有可能的移动。现代PC上只需要几毫秒。

Answer 4

要回答你的第二个问题：

现在我怎么可以让电脑选择的下一个最好的选择是......

这是极大极小算法的任务。它偷看游戏树的最佳举动。对于井字游戏，您不需要非常复杂的评估功能，如果玩家赢得或0，则足以返回正面或负面价值。如果你愿意，你可以通过评估一名球员是否能在下一步中获胜来扩展它。更复杂的评估功能，您需要具有更大分支因子的游戏，并且游戏树可以更深入（不仅仅是9步）。
我的经验^*是，在游戏树搜索中进一步深入到更好的结果比由于更聪明的评估函数而达不到此层（同一时间）更好。由于简单的评估，或者由于复杂的评估，因此不需要进行如此深入的搜索，因此区分深度搜索并不容易。 有很多其他显著增强了极大极小算法是有希望的，不要卡住首先想到的一个复杂的评估：

• Alpha-Beta Pruning
• Iterative Deepening
• Transposition Table

之后您仍然可以改进评估功能。对评估的一些其他想法：也许最好在函数makeMove中做一些工作，在这里你只需要检查一行（而不是全部）行，一列和一个或两个对角线。然后，在当前董事会旁边，保留从此检查中获得的信息。这些信息包括，如果这是一个胜利的举动（设置得分），或者如果从另一个玩家的下一个移动被迫（记住下一个玩家必须移动的移动，getMoves将只返回这个）。最后但并非最不重要的，如果一列/一排和一个对角线包含强制移动，则玩家以两步移动（保持得分）。

祝您好运，您的评估功能！

_{*前一段时间我的工作是评估Connect-Four-Game-Engine的功能。评估连接四块电路板的最佳方法是分析詹姆斯·D·艾伦（James D. Allen）的关键词Expert Play in Connect-Four的“威胁分析”一章中所描述的奇怪甚至威胁。该算法分析了主要和次要威胁。删除次要威胁分析部分后，alpha-beta搜索表现更好！}

Answer 5

我知道你在说什么。你需要的是一个很好的启发式功能。你可以从这里找到启发式功能（我没有尝试任何人）：

Solve Tic Tac Toe with the MiniMax algorithm

Visualgos: Tic-Tac-Toe