我可以看到这个问题(或类似的问题)已被问过几次,我在谷歌上搜索了很多,以便我可以尝试理解它,但是我绝对被卡住了。
我的任务是使用递归函数,该函数使用“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();
}
}
最佳答案
不要因为阅读该文档而无法理解递归而感到太难过。它不能很好地解释递归。 (这是一个艰难的概念 - 我可能也不会做得很好)。最终,您必须做的是尝试让您的程序做您想做的事情。我将尝试从这个角度来解释它。
递归很有用,因为它让我们对解决方案中的一个步骤进行编码(一次),然后使用刚刚计算的结果作为输入重复该步骤。试着从你的角度来看你的问题,而不是一些任意的善良算法。您可能过于努力地理解论文中的算法。
试着这样想:在游戏开始时,玩家 1 开始玩。您的程序必须为玩家 2 选择一个移动。但是玩家 2 必须考虑游戏的其余部分(对于每个可能的移动)。
你可以把它改写成:
当前玩家为 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;
}
与玩家一起,您必须传递一些代表剩余所有可能移动状态的东西。问题是,如果您传递一些作为引用传递的内容,您所做的任何更改都将反射(reflect)在您的原始数据中。确保不会发生这种情况。这可能就是@CodeInChaos 建议您克隆的原因。
请注意,在递归中,您必须确保始终有办法结束调用序列。您必须修改最终条件所依赖的任何内容。在这种情况下,您可能的移动数量正在下降。否则,您将永远调用并耗尽内存。
编辑:添加了对板类的解释。
从大局考虑。类是现实世界事物(例如对象)的表示。事物具有描述它的属性。这些是类(class)的数据。一件事也做 Action 。这些是方法。我听说过的另一个类的定义是类是数据和对该数据的操作。
想想游戏有哪些对象。 2 名球员和一个棋盘。别的不多。
玩家可以移动,并拥有唯一标识符(在本例中为“X”或“O”),并且可以是人类或 AI。目前我想不出其他任何事情(重要的),但通常还有更多事情可能存在但不会真正影响程序(例如眼睛颜色)。这也是您可以使用继承的地方。您有一个带有抽象 move 方法的播放器类。从玩家继承的人类类,其覆盖移动方法接受来自 UI 的输入,计算机/AI 类从玩家继承并通过计算具有良好评级的移动来覆盖移动方法。
董事会有数据:
董事会的行动可能是:
你可以有一个静态的 GoodNess 类(可能需要一个更好的名字)
没有数据,只有一个方法(或者这可能是板类上的另一种方法:
AI 可以在移动之前调用 Goodness GetBestMove 方法。
递归将与该 GetBestMove 方法隔离。
请注意,这些都不是一成不变的。类由您认为应该包含在其中的内容定义。这一切都基于您如何认为是解决问题的最佳方法。如果您仍然遇到问题,请使用您尝试使用的代码更新您的问题。当您开始布置代码时,绘制图表确实很有帮助。
祝你好运,希望这会有所帮助,我会尝试更好地监控 StackOverflow 通知。
关于c# - 井字游戏递归算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/8880064/