标签: tic-tac-toe

我正在开发tic-tac-toe游戏,我需要算法来检查游戏何时结束(谁赢了).在3x3游戏中,我会检查每个可能的胜利情况(有8个功能).但是在7x7中(连续需要4个符号或者是对角线),很多可能的胜利模式.

我读到了Tesauro的TD-Gammon计划,并希望将其用于tic tac toe,但几乎所有的信息对我来说都是高中生无法访问的,因为我不知道术语.

这里的第一个等式,http://www.stanford.edu/group/pdplab/pdphandbook/handbookch10.html#x26-1310009.2

给出了"一般监督学习范式".它表示等式左边的w sub t是时间步t的参数向量."时间步长"究竟是什么意思？在设计用于输出电路板状态值的tic tac toe神经网络的框架内,时间步长是指给定游戏中播放的片段数量吗？例如,由字符串"xoxoxoxox"表示的板将在时间步骤9处并且板"xoxoxoxo"将在时间步骤8处？或者时间步骤是指自培训开始以来经过的时间量？

由于w sub t是给定时间步长的权重向量,这是否意味着每个时间步都有自己的评估函数(神经网络)？因此,要仅通过一次移动来评估电路板状态,您必须输入不同的NN,而不是通过两次移动来馈送电路板状态？我想我在这里误解了一些东西,因为据我所知,Tesauro只使用一个NN来评估所有的董事会状态(尽管很难找到关于TD-Gammon的可靠信息).

为什么输出的梯度取决于w而不是w sub？

提前感谢您澄清这些想法.我将不胜感激任何关于我的项目的建议或对易读阅读材料的建议.

我想问一下是否有可能在tic tac toe挑战中获胜？因为法官机器人知道每一个技巧,并且他知道如何失败,技巧就会移动.我只能在两个回合中打平比赛.如果有可能的话,请你们给我一个暗示吗？

考虑到所有情况,可以很容易地解决一个小的(3x3,4x4)井字游戏.但是,例如,你有一个30x30的tic-tac-toe.在这种情况下,您将使用什么算法来决定下一个最佳移动？

Minimax + alpha-beta修剪是我所知道的一种方式.

是否有其他方式更有效/更高效但更酷？

我知道这不是一个非常有趣的游戏.我说30x30只是为了问我想要什么,即哪种算法在这类游戏中效果最好,其中为完美解决方案考虑的案例数量非常高,因此不可行.

我有一个完整的tic tac toe游戏板.这是3 x 3.我不是真的要求代码(虽然这会有所帮助),但是哪种算法最适合看谁赢了？另一种表达它的方法是,我应该研究哪些算法对于看谁赢了会有用？

唯一真正想到的是蛮力.只是测试所有的可能性,但我知道必须有一个更好的方法.

我一直在尝试使用多层感知器和反向传播来编写一个用于tic tac toe的AI.我的想法是训练神经网络成为电路板状态的准确评估函数,但问题是即使在分析了数千个游戏之后,网络也没有输出准确的评估.

我正在使用27个输入神经元; 3x3板上的每个方块与三个输入神经元相关联,这三个输入神经元接收0或1的值,具体取决于方块是否具有x,o或空白.这27个输入神经元向10个隐藏的神经元发送信号(我任意选择10个,但我也试过了5个和15个).

对于训练,我已经让程序通过使用当前评估函数对自己进行比赛来生成一系列游戏,以选择被认为是每一方的最佳移动.在生成游戏之后,NN通过将给定板状态的正确输出作为其后面的板状态的值(使用评估函数)来编译训练示例(其包括板状态和正确的输出).游戏序列.我认为这是Gerald Tesauro在编写TD-Gammon时所做的,但我可能误解了这篇文章.(注意:我在本文的底部放置了更新权重的具体机制).

我已经尝试了各种学习率的值,以及不同数量的隐藏神经元,但似乎没有任何效果.即使经过数小时的"学习",战略上也没有明显的改进,评估功能也不会接近准确.

我意识到有更简单的方法来编写tic tac toe,但是我想用多层感知器做这件事,这样我以后可以将它应用于连接4.这甚至可能吗？我开始认为对于具有合理数量的隐藏神经元的tic tac toe板没有可靠的评估功能.

我向你保证,我不是在寻找一些快速的代码来完成家庭作业.我已经有一段时间没有成功工作,只想知道我做错了什么.所有建议表示赞赏.

这是我用于NN的具体机制:

27个输入神经元中的每一个接收0或1,其通过可微分的S形函数1 /(1 + e ^( - x)).每个输入神经元i发送此输出(i.output),乘以一些权重(i.weights [h])到每个隐藏的神经元h.这些值的总和被隐藏神经元h(h.input)作为输入,并且该输入通过sigmoid以形成每个隐藏神经元(h.output)的输出.我将lastInput表示为所有隐藏神经元中(h.output*h.weight)的总和.然后,板的输出值是sigmoid(lastInput).

我将学习率表示为alpha,并将错误表示为正确的输出减去实际输出.另外,我让dSigmoid(x)等于x点处的sigmoid的导数.

每个隐藏神经元h的权重增加值:(alpha*err*dSigmoid(lastInput)*h.output)并且从给定输入神经元i到给定隐藏神经元h的信号的权重增加该值:(alpha*err*dSigmoid(lastInput)*h.weight*dSigmoid(h.input)*i.output).

我从这个关于反向传播的讲座中得到了这些公式:http://www.youtube.com/watch？v = UnWL2w7Fuo8 .

我正在为计算机对手构建一个具有不同AI实现的Tic Tac Toe游戏,以便学习不同的算法以及如何实现它们.我尝试的第一个应该是最简单的只是让计算机每次都选择一个随机空间.

这在一定程度上对我有用,问题就变成了运行时间.每次aiRandMove()调用该方法时,需要更长时间才能选择移动到已经在板上进行了5次移动(cpu +用户组合)之后的程序,程序似乎挂起(尽管从技术上来说并非如此).

在我进一步调试时,我意识到这应该是预期的,因为该aiRandMove()方法是随机选择X和Y坐标,然后测试移动以查看它是否合法.随着越来越少的空间被打开,合法移动越来越少,因此随机发生器尝试生成合法移动的失败次数更多.

我的问题是,有什么方法可以修改这个,至少可以减少函数所用的时间吗？据我所知,谷歌搜索和我自己解决问题,我想不出一种方法来优化这个,而不会影响功能的"随机性".我考虑过保留计算机尝试的一系列移动,但这不会解决问题,因为这不会影响rand()生成重复数字的次数.以下是此函数的代码,它与此问题非常相关:

//Function which handles the AI making a random move requires a board
//object to test moves legality and player object to make a move with
//both are passed by reference because changes to board state and the player's
//evaluation arrays must be saved
char aiRandMove(Player &ai, Board &game){
   int tryX;
   int tryY; //Variables to store computer's attempted moves
   bool moveMade = false;
   char winner;
   while(!moveMade){
      srand(time(NULL));//Randomizes the …

我使用 Minimax 和 Alpha Beta Pruning 制作了一个 Tic Tac Toe 游戏。我想为 Tic Tac Toe (10x10) 游戏制作计算机 AI，但它的游戏树大小大得离谱。

我的代码是这样的，我只需要更改两个变量即可更改连续所需的棋盘大小 + 单元格数。例子：

boardSize = 3 // This is for 3x3 tic tac toe

boardSize = 4 // This is for 4x4 tic tac toe

boardSize = 10 // This is for 10x10 tic tac toe

和

winStreak = 3 // Need to make 3 cells in a row to win

winStreak = 4 // Need to make 4 cells in a row …

我正在开发一个项目，我必须在java中使用openCV来识别井字游戏板的状态。请参阅下面的示例程序执行。

输入

输出

X,-,-

-,O,-

X,-,-

我试图通过查找图像中的轮廓来解决此问题，但问题是未标记的空框也被捕获，并且我无法使用多边形大小和轮廓面积等轮廓属性来区分形状。下面是我到目前为止的代码。

package finalproject;

import java.awt.Color;
import java.util.ArrayList;
import java.util.List;

import org.opencv.core.Core;
import org.opencv.core.Mat;
import org.opencv.core.MatOfInt;
import org.opencv.core.MatOfPoint;
import org.opencv.core.MatOfPoint2f;
import org.opencv.core.Rect;
import org.opencv.core.Scalar;
import org.opencv.core.Size;
import org.opencv.imgcodecs.Imgcodecs;
import org.opencv.imgproc.Imgproc;


public class FinalProject {
    public static void main(String[] args) {

    System.loadLibrary(Core.NATIVE_LIBRARY_NAME);
    Mat image = Imgcodecs.imread("C://Users//BadarJahan//Desktop//board- 
    perfect.jpg");

    Mat binaryImage = preprocess(image);

    List<MatOfPoint> contours = new ArrayList<>();
    Imgproc.findContours(binaryImage, contours,new Mat() ,Imgproc.RETR_CCOMP, Imgproc.CHAIN_APPROX_SIMPLE);
    List<MatOfPoint2f> contoursConvert = new ArrayList<>();

    for(MatOfPoint contour : contours) {
        contoursConvert.add(new MatOfPoint2f(contour.toArray()));
    }

    identifyTicTacToeConfiguration(binaryImage,contoursConvert);

} …

我正在尝试使用 python 中的极小极大算法编写井字棋机器人。我的代码似乎应该对我有用，但错误地评估了位置，搜索太多或太少的节点，并且每场比赛都输给了我。

mainboard = ["-", "-", "-", "-", "-", "-", "-", "-", "-"]
nodes = 0

def detectwin(b):
    signs = ["O", "X"]
    for s in signs:
        for i in range(3):
            j = 3 * i
            if ((b[0 + j]==s and b[1 + j]==s and b[2 + j]==s) or
                (b[0 + i]==s and b[1 + i]==s and b[2 + i]==s)):
                if s == "O": return 1
                if s == "X": return -1
        if ((b[0]==s and b[4]==s and b[8]==s) or
            (b[2]==s …