7

我可以看到这个问题(或类似的问题)已被问过几次,并且我已经在谷歌上搜索了很多,以便我可以尝试理解它,但是我绝对被卡住了。

我的任务是使用递归函数,该函数使用“善良”变量来确定计算机可以做出的最佳移动,我什至有一个文档可以帮助解决这个问题,但对于我的生活,我只是不不明白。

如果有人可以花一些时间来帮助我或分解我实际需要做的事情,我将不胜感激,我将在下面链接我目前拥有的代码,但这是一项作业,因此指导比直接回答更可取。我已经查看了 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();
    }
}
4

1 回答 1

12

不要因为阅读该文档而无法理解递归而感到难过。它不能很好地解释递归。(这是一个艰难的概念——我可能也不会那么好)。归根结底,你要做的就是让你的程序做你想做的事。我将尝试从这个角度来解释它。

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

试着这样想:在游戏开始时,玩家 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。目前我想不出其他任何东西(重要的),但通常还有更多可能存在但不会真正影响程序的东西(比如眼睛颜色)。这也是您可以使用继承的地方。你有一个带有抽象 move 方法的玩家类。从玩家继承的人类类具有从 UI 接受输入的覆盖移动方法,计算机/AI 类从玩家继承并通过计算具有良好评级的移动来覆盖移动方法。

板子有数据:

  • 一个 3 x 3 的可能播放位置网格(顺便说一下,这也可以是位置对象的集合)
    • 可能需要玩家 1 和 2 的代表

董事会的行动可以是:

  • 接受玩家(人类或人工智能)的移动,如果有效则记录它,确定获胜并返回一个指示好移动、坏移动、游戏结束或获胜的​​指示符
  • 可以有一种方法来返回当前游戏的获胜者
  • 可能需要一个重置方法
  • 可能有移动历史

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

  • 接受棋盘,计算并返回善良数组,或者简单地返回最佳移动

AI 可以在移动之前调用 Goodness GetBestMove 方法。
递归将被隔离到该 GetBestMove 方法。

请注意,这些都不是一成不变的。类由您认为应该包含的内容定义。这一切都基于您认为解决问题的最佳方式。如果您仍然遇到问题,请使用您尝试使用的代码更新您的问题。当您开始布置代码时,绘制图表确实很有帮助。

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

于 2012-01-17T02:50:02.153 回答