标签: tic-tac-toe

一点背景:作为一种在C++中学习多节点树的方法,我决定生成所有可能的TicTacToe板并将它们存储在一棵树中,这样从一个节点开始的分支都是可以跟随该节点的板,以及节点是一步到位的板.在那之后,我认为使用该树作为决策树编写AI来玩TicTacToe会很有趣.

TTT是一个可以解决的问题,一个完美的玩家永远不会丢失,所以我第一次尝试AI时编码似乎很简单.

现在,当我第一次实现AI时,我回过头来为每个节点添加两个字段:X将赢得的次数和O将在该节点下的所有子节点中获胜的次数.我认为最好的解决方案就是让我的每一步动作都选择AI,然后选择最能赢得次数的子树.然后我发现虽然它在大部分时间都是完美的,但我找到了可以击败它的方法.这对我的代码来说不是问题,只是我用AI选择它的路径的问题.

然后我决定让它选择具有计算机最大胜利或人类最大损失的树,以较多者为准.这使它表现更好,但仍然不完美.我仍然可以击败它.

所以我有两个想法,我希望得到更好的输入:

1)而不是最大化赢或输,而是我可以为胜利分配1,为平局分配0,为亏损分配-1.然后选择具有最高值的树将是最佳移动,因为下一个节点不能是导致丢失的移动.这是电路板生成中的一个简单更改,但它保留了相同的搜索空间和内存使用量.要么...

2)在棋盘生成期间,如果有一个棋盘使X或O在下一步中获胜,则只会产生阻止该胜利的孩子.不会考虑其他子节点,然后生成将在此之后正常进行.它缩小了树的大小,但后来我必须实现一个算法来确定是否有一个移动获胜,我认为这只能在线性时间内完成(我认为让板子生成慢很多？)

哪个更好,还是有更好的解决方案？

我决定编写一个小程序来解决TicTacToe,以便尝试一些修剪技术对一个琐碎游戏的影响.使用minimax解决它的完整游戏树最终只有549,946个可能的游戏.通过alpha-beta修剪,评估所需的状态数量减少到18,297.然后我应用了一个转换表,将数字降至2,592.现在我想看看这个数字有多低.

我想申请的下一个改进是战略性削减.基本思想是结合具有同等战略价值的国家.例如,在第一步中,如果X首先发挥作用,那么在选择一个角落而不是另一个角落时,没有任何战略上的差异(假设你的对手发挥得最佳).在相同的情况下,板的中心也是如此,中心也很重要.通过仅减少到显着状态,最终只有3个状态用于第一步而不是9的评估.这种技术应该非常有用,因为它修剪了游戏树顶部附近的状态.这个想法来自CMU的一个小组创建的GameShrink方法,只是我试图避免编写一般形式,只是做了将技术应用于TicTacToe所需的东西.

为了实现这一点,我修改了我的哈希函数(对于转置表)来枚举所有策略上等效的位置(使用旋转和翻转函数),并且仅返回每个板的最低值.不幸的是,现在我的计划认为X可以在第一次出局时从空板上强行取胜5次.经过长时间的调试会议后,对我来说很明显,程序总是返回最低战略意义的移动(我将最后一个移动存储在转置表中作为我的状态的一部分).有没有更好的方法可以添加此功能,或者使用我已经完成的确定适用于当前情况的正确移动的简单方法？

我无法理解如何更新tic tac toe游戏的Q值.我读了所有这些,但我无法想象如何做到这一点.我读到Q值在游戏结束时更新,但我不明白,如果每个动作都有Q值？

我目前正在为一项作业制定一个tic tac toe程序.我遇到的问题是当我计算我的球员('X'球员或'Y'球员)时,它似乎在计算两个球员的数量.例如,在第三场比赛之后,它看到了三场比赛,并将其视为胜利者,尽管只完成了一场比赛的两场比赛和另一场比赛的一场比赛.

public class TicTacToeApp
 {
    public static void main(String[] args)
    {
          TicTacToeView view = new TicTacToeView();
          TicTacToeModel model = new TicTacToeModel();
          TicTacToeViewController controller = new             
          TicTacToeViewController(view,model);
          view.setVisible(true);
    }
 }
public class TicTacToeModel 
{

    double xpos,ypos,xr,yr;
    char[][] position = {{' ',' ',' '},
                         {' ',' ',' '},
                         {' ',' ',' '}};


   public void computePos(int row, int col, int h, int w)
   {
      xpos=(col+0.5)*w/3.0;
      ypos=(row+0.5)*h/3.0;
      xr=w/8.0;
      yr=h/8.0;
   }

public boolean isEmpty(int xpos, int ypos)
{

  if(position[xpos][ypos]==' ')
     return true;

  return …

我想生成一个文本文件,其中包含所有19,683个 Tic-Tac-Toe板布局,结构为0 =空白,1 = X,2 = O.不幸的是,数学不是我的强项,我似乎找不到任何例子在任何地方.

这不是我向你保证的作业.我打算通过Minimax计算器运行此数据,以生成包含RGB值的图像,RGB值表示基于电路板设置的最佳移动.我正在开发一个不支持函数的平台Tic-Tac-Toe(它是事件驱动的)所以我会将我的电路板转换为游戏中的数字,然后在图像中查找像素的RGB,以指示最佳移动是.这是一个厚颜无耻的解决方法,但不需要比145x145像素图像更多的RAM(145x145 = 21,025,因此每个像素代表基于电路板的推荐移动有效).这也意味着我不必咀嚼CPU时间,这是另一个优点.

我知道这已被问了很多,我已经搜索了其他代码,但我看到的大部分内容似乎都没有完美无缺(永不丢失),而且简单,优雅,高效.我无法确定哪种解决方案适合该描述.

我见过的解决方案是:

(1)使用minimax进行alpha-beta修剪.这对我来说似乎很复杂,对于这么简单的游戏可能没必要？它可能太复杂了吗？如果没有,我需要做很多硬编码还是我误解了算法？

(2)使用维基百科的伪代码策略编写代码...我不确定如何实现它.例如,它只是说"检查叉子".大多数这些检查是通过拥有一系列的winsLines并检查它们是否被填充或类似的东西来完成的？如果没有,有人可以给我提示有关如何在伪代码中实现检查的数据结构或任何基本提示:http://en.wikipedia.org/wiki/Tic-tac-toe#Strategy.我也看过算法给'X'方形和'O'方形赋予数值然后用和来决定胜利者,但我不明白为什么这个特别有用.

还有其他任何合理的解

我正在实现m,n,k -game,tic-tac-toe的通用版本,其中m是行数,n是列数,k是玩家需要放置的块数连续获胜.我已经实现了一场胜利的检查,但是如果没有球员可以赢得比赛,我还没有想出一个令人满意的方法来检查董事会是否满满的.换句话说,棋盘上可能有空位,但不能以一名球员获胜的方式填补.

我的问题是,如何有效地检查这个？以下算法是我能想到的最好的算法.它检查两个条件:

A.遍历所有4个方向的所有电路板位置(从上到下,从右到左,以及两个对角线方向).如果说k = 5,并且找到4(= k -1)个连续的空槽,则停止检查并报告"无关系".这没有考虑到例如以下情况:

OX----XO    (Example 1)

其中a)有4个空的连续槽(-)在两个之间的某个地方X,b)接下来O轮到它了,c)在棋盘上有少于四个其他空位,没有玩家可以通过将棋子放到那些位置来获胜,并且d)在所示的槽中也不可能在任何其他方向上获胜而不是水平.现在我们知道这是一个平局因为O最终会阻止最后一次获胜的可能性,但错误的是它还没有报告,因为有四个连续的空位.那没关系(但不是很好).当检查算法通常早期发现这种情况时,检查这种情况会在开始时提供良好的加速,但随着更多的碎片放在板上,它会变慢.

B.如果不满足该k -1连续空时隙条件,则算法将在所有4个方向上连续地再次检查时隙.假设我们目前正在从左到右进行检查.如果在某个时刻X遇到一个并且它前面有一个O或-(空槽)或一个板边框,那么就开始计算连续X的和空槽的数量,计算在第一个遇到的时间X.如果一个人可以数到5,那么就知道有可能X获胜,并且报告"没有平局".如果在连续5次O之前X遇到一个前面的a X,X则从我们开始计数的地方开始,从左到右不能赢得那5个时段.例如:

X-XXO    (Example 2)
12345

在这里,我们开始检查位置1,数到4,并遇到了一个O.在这种情况下,人们会O以同样的方式继续遇到,这次尝试找到5个连续O或空的插槽.在另一种情况下,当计数X或空槽O时,在计数到5之前会遇到前面有一个或多个空槽的情况.例如:

X-X-O    (Example 3)
12345

在这种情况下,我们将再次从O位置5 继续,但添加到新计数器(连续O的或空的插槽)前面的连续空插槽的数量O …

我正在关注官方网站上的 React Js 教程，该教程帮助我们构建了一个井字棋游戏。方框是通过对所有方框进行硬编码来创建的，如下所示：

render(){
  return (
    <div>
      <div className = "board-row">
        {this.renderSquare(0)}
        {this.renderSquare(1)}
        {this.renderSquare(2)}
      </div>
      <div className = "board-row">
        {this.renderSquare(3)}
        {this.renderSquare(4)}
        {this.renderSquare(5)}
      </div>
      <div className = "board-row">
        {this.renderSquare(6)}
        {this.renderSquare(7)}
        {this.renderSquare(8)}
      </div>
    </div>
  );
}

我设法通过使用 for 循环来缩短代码，如下所示：

render(){
  let sqrRen = [];
  for(let i = 0; i < 9; i=i+3){
    sqrRen.push(<div className = "board-row">
      {this.renderSquare(0+i)}
      {this.renderSquare(1+i)}
      {this.renderSquare(2+i)} 
    </div>);
  }
  return (
    <div>
        {sqrRen}
    </div>
  );
}

但我还想使用另一个 for 循环生成每行中的正方形，如下所示：

render(){
  let sqrRen = [];
  for(let i = …

我正在尝试用 pygame 制作一个井字游戏，我想知道我将如何处理这里的逻辑，这是我目前所拥有的。视频 < 我只有当我点击中间按钮时它才会在屏幕上显示播放器 2 x 然后悬停在我鼠标上的图像将变成 O 以让播放器 1 转但我的问题是我将如何做这样的逻辑，如果玩家 1 连续得到 3 或玩家 2 连续得到 3我真的很困惑，我需要有人陪我扔它

我现在的井字游戏代码

import pygame,random
pygame.init()

# draw our window
window = pygame.display.set_mode((500,540),pygame.NOFRAME)
pygame.display.set_caption("Tic Tac TOE")



MANUAL_CURSOR = pygame.image.load('nw.png').convert_alpha()


MANUAL_CURSOR2 = pygame.image.load('nOW.png').convert_alpha()



bg = pygame.image.load("ticO.png")
fps = 40

clock = pygame.time.Clock()

class button():
    def __init__(self, color, x,y,width,height, text=''):
        self.color = color
        self.x = x
        self.y = y
        self.width = width
        self.height = height
        self.text = text
        self.over = False

    def draw(self,window,outline=None): …

我很好奇我是否使用了太多的if/else if语句.我正在使用javascript编写一个tic-tac-toe程序,并确定计算机是否应该阻止我使用的播放器大约9 if语句和我在确定是否连续3时使用大约9.

例如:

if(r1c1V === xOrO && r1c2V === xOrO && r1c3V === xOrO)
{
    is3InARow = true;
}
else if(r2c1V === xOrO && r2c2V === xOrO && r2c3V === xOrO)
{
    is3InARow = true;
}
else if(r3c1V === xOrO && r3c2V === xOrO && r3c3V === xOrO)
{
    is3InARow = true;
}
.
.
.
.

等等.

所以我的问题是,我是否使用过多if语句？或者没有更好的方法来做到这一点？我的朋友告诉我,我不应该使用那么多if语句,但我不确定他是否真实,我能理解为什么在某些情况下它会更慢或更糟,但我不确定.

提前致谢!!