Tic Tac Toe递归算法

Question

我可以看到这个问题(或类似的问题)已被问过几次,我已经搜索了很多谷歌,所以我可以试着理解它,但我绝对被卡住了.

我的任务是使用递归函数,使用"goodness"变量来确定哪个是计算机可以做出的最佳移动,我甚至有一个文档可以帮助解决这个问题,但对于我的生活,我只是不喜欢理解它.

如果有人可能需要一些时间来帮助我或分解我真正需要做的事情,我会非常感激,我将链接到目前为止我的代码,但这是一项任务,所以指导比直接答案更可取.我已经看过MinMax解决方案了,这肯定在我的掌握之上,我对编程非常陌生(特别是在C#只有几个月的经验)所以就这么简单!

以下是我想要遵循的建议解决方案:

http://erwnerve.tripod.com/prog/recursion/tictctoe.htm

public partial class Form1 : Form
{
    public static string[,] Board = new string[3, 3] { { "1", "2", "3" }, { "4", "5", "6" }, { "7", "8", "9" } };
    public bool Winner = false;
    public string WinState;

    private void Reset()
    {
        WinState = "";
        Winner = false;
        Board[0, 0] = "1";
        Board[0, 1] = "2";
        Board[0, 2] = "3";
        Board[1, 0] = "4";
        Board[1, 1] = "5";
        Board[1, 2] = "6";
        Board[2, 0] = "7";
        Board[2, 1] = "8";
        Board[2, 2] = "9";
        btn1.Text = "";
        btn2.Text = "";
        btn3.Text = "";
        btn4.Text = "";
        btn5.Text = "";
        btn6.Text = "";
        btn7.Text = "";
        btn8.Text = "";
        btn9.Text = "";
    }

    private void checkWinner()
    {
        // Top Row
        if (Board[0, 0].Equals(Board[0, 1]) && Board[0, 1].Equals(Board[0, 2]))
        {
            Winner = true;
            WinState = Board[0, 0];
        }
        // Middle Row
        if (Board[1, 0].Equals(Board[1, 1]) && Board[1, 1].Equals(Board[1, 2]))
        {
            Winner = true;
            WinState = Board[1, 0];
        }
        // Bottom Row
        if (Board[2, 0].Equals(Board[2, 1]) && Board[2, 1].Equals(Board[2, 2]))
        {
            Winner = true;
            WinState = Board[2, 0];
        }
        // Left column
        if (Board[0, 0].Equals(Board[1, 0]) && Board[1, 0].Equals(Board[2, 0]))
        {
            Winner = true;
            WinState = Board[0, 0];
        }
        // Middle column
        if (Board[0, 1].Equals(Board[1, 1]) && Board[1, 1].Equals(Board[2, 1]))
        {
            Winner = true;
            WinState = Board[0, 1];
        }
        // Right column
        if (Board[0, 2].Equals(Board[1, 2]) && Board[1, 2].Equals(Board[2, 2]))
        {
            Winner = true;
            WinState = Board[0, 2];
        }
        // Diagonal 1
        if (Board[0, 0].Equals(Board[1, 1]) && Board[1, 1].Equals(Board[2, 2]))
        {
            Winner = true;
            WinState = Board[0, 0];
        }
        // Diagonal 2
        if (Board[2, 0].Equals(Board[1, 1]) && Board[1, 1].Equals(Board[0, 2]))
        {
            Winner = true;
            WinState = Board[2, 0];
        }

        if (Winner == true)
        {
            if (WinState == "X")
            {
                MessageBox.Show("Congratulations you win!");
                Reset();
            }
            else if (WinState == "O")
            {
                MessageBox.Show("Sorry you lose!");
                Reset();
            }
        }
    }

    private void btn1_Click(object sender, EventArgs e)
    {
        btn1.Text = "X";
        Board[0, 0] = "X";
        checkWinner();
    }

    private void btn2_Click(object sender, EventArgs e)
    {
        btn2.Text = "X";
        Board[0, 1] = "X";
        checkWinner();
    }

    private void btn3_Click(object sender, EventArgs e)
    {
        btn3.Text = "X";
        Board[0, 2] = "X";
        checkWinner();
    }

    private void btn4_Click(object sender, EventArgs e)
    {
        btn4.Text = "X";
        Board[1, 0] = "X";
        checkWinner();
    }

    private void btn5_Click(object sender, EventArgs e)
    {
        btn5.Text = "X";
        Board[1, 1] = "X";
        checkWinner();
    }

    private void btn6_Click(object sender, EventArgs e)
    {
        btn6.Text = "X";
        Board[1, 2] = "X";
        checkWinner();
    }

    private void btn7_Click(object sender, EventArgs e)
    {
        btn7.Text = "X";
        Board[2, 0] = "X";
        checkWinner();
    }

    private void btn8_Click(object sender, EventArgs e)
    {
        btn8.Text = "X";
        Board[2, 1] = "X";
        checkWinner();
    }

    private void btn9_Click(object sender, EventArgs e)
    {
        btn9.Text = "X";
        Board[2, 2] = "X";
        checkWinner();
    }
}

Answer 1

不要因为阅读该文档而不理解递归感到太糟糕.它在解释递归方面做得不是很好.(这是一个艰难的概念 - 我可能也不会这么做).最终,你要做的就是尽量让你的程序做你想做的事.我将尝试从这个角度来解释它.

递归很有用,因为它允许我们在解决方案中编码(一次)一个步骤,然后使用刚刚计算的结果作为输入重复该步骤.尝试从你的角度看你的问题,而不是一些任意的善意算法.你可能很难理解论文中的算法.

尝试这样思考:在游戏开始时玩家1进行游戏.你的程序必须为玩家2选择一个移动.但玩家2必须考虑游戏的其余部分(每个可能的移动).

1. 玩家2可以选择8种可能的动作.
2. 玩家1可以从7中选择
3. 玩家2可以从6中选择
4. 玩家1可以从5中选择
5. 玩家2可以从4中选择
6. 玩家1可以从3中选择
7. 玩家2可以选择2
8. 玩家1占据最后一个方格.

您可以将其改为:
当前玩家为2,为当前玩家的所有剩余选择赋予权重.
当前玩家为1,为当前玩家的所有剩余选择赋予权重.
当前玩家为2,为当前玩家的所有剩余选择赋予权重.
当前玩家为1,为当前玩家的所有剩余选择赋予权重.
当前玩家为2,为当前玩家的所有剩余选择赋予权重.
当前玩家为1,为当前玩家的所有剩余选择赋予权重.
当前玩家为2,为当前玩家的所有剩余选择赋予权重.
当前玩家为1,为当前玩家的所有剩余选择赋予权重.

您可以将其改为:给予当前玩家,切换玩家并为当前玩家的所有可能选择赋予权重.
重复直到不再有可能的选择

您可以将其改为:给定当前播放器,切换播放器和CheckGoodness()重复直到无法再进行选择

所以,回到你的写作.作者使用1和-1的玩家.为什么？因为当你越来越深地传递动作时,你必须交换玩家,并且当你下降这样的等级时切换玩家很容易(我在这里只讨论玩家:

public int CheckGoodness(bool playerID)
{
    playerID = -playerID;
    if (!endConditionMet)
    {
        goodness = CheckGoodness(playerID);
    }
    return goodness;
}

与玩家一起,你必须传递代表剩余所有可能移动状态的东西.问题是,如果您传递的内容作为参考传递,您所做的任何更改都将反映在原始数据中.确保没有发生.这可能就是@CodeInChaos建议你克隆的原因.

请注意,在递归中,您必须确保始终有办法结束调用序列.您必须修改您所依赖的最终条件.在这种情况下,您的可能移动数量正在下降.否则你永远打电话,内存不足.

编辑:添加的板类说明.

从大局出发考虑一下.类是现实世界事物(例如对象)的表示.一件事具有描述它的属性.这些是班级的数据.事也行动.这些是方法.我听过的一个类的另一个定义是类是对该数据的数据和操作.

想想游戏中的对象.2名球员和一名董事会.没什么别的.

玩家可以移动,并且具有唯一标识符(在这种情况下为"X"或"O"),并且可以是人或AI.我现在想不出任何其他事情(重要的),但通常会有更多的东西可以存在,但不会真正影响程序(如眼睛颜色).这也是您可以使用继承的地方.你有一个带有抽象移动方法的玩家类.从播放器继承的人类,使用覆盖移动方法接受来自UI的输入,从播放器继承的计算机/ AI类,并通过计算具有良好评级的移动来覆盖移动方法.

董事会有数据:

• 一个3乘3网格的可能游戏位置(顺便说一句,这也可能是一个位置对象的集合)
  • 可能需要代表球员1和2

董事会的行动可能是:

• 接受一个玩家的(人类或AI)移动,记录它是否有效,确定胜利并返回一个好动,坏动,游戏结束或胜利的指标
• 可以有一种方法来返回当前游戏的赢家
• 可能需要重置方法
• 可以有一个移动历史

你可以有一个静态的GoodNess类(可能需要一个更好的名字),没有数据,只有一个方法(或者这可能是板类上的另一种方法:

• 接受一块板,计算并返回良性阵列,或者只是返回最佳移动

AI可以在移动之前调用Goodness GetBestMove方法.
递归将与GetBestMove方法隔离.

请注意,这些都不是一成不变的.类是由您认为应该在其中定义的.这完全取决于你如何成为解决问题的最佳方法.如果您仍然遇到问题,请使用您尝试过的代码更新您的问题.在开始布置代码时,绘制图表确实很有帮助.

祝你好运,希望这会有所帮助,我会尝试更好地监控StackOverflow通知.