Tic Tac Toe递归算法 [英] Tic Tac Toe recursive algorithm
问题描述
我看到这个问题(或类似的问题)已经问了几次了，我在Google上搜索了很多，以便我可以尝试理解它，但是我绝对会卡住.
I can see this question (or a similar one) has been asked a few times and I've searched google a lot so that I can try to understand it however I am most definitely stuck.
我的任务是使用一个递归函数，该递归函数使用善良"变量来确定哪台计算机可以做出最好的移动，我什至有一个文档可以帮助您做到这一点，但对我而言，这是我的生命只是不明白.
My task is to use a recursive function that uses a "goodness" variable to determine which is the best move a computer can make, I even have a document that is meant to help with this but for the life of me, I just don't understand it.
如果有人可以花一些时间来帮助我或破坏我真正需要做的事情，我将不胜感激，我将在下面链接我到目前为止的代码，但这是一项作业，因此指导更可取答案.我已经看过MinMax解决方案，而且这绝对超出了我的理解范围，我对编程非常陌生(尤其是在只有几个月经验的C#中)，所以轻松一点吧！
If anyone could take some time to help me or break down what I actually need to do i'd be much appreciating, I'll link the code I have so far below but this is an assignment so guidance is preferable to direct answers. I've looked at the MinMax solution and that definitely seems above my grasp, I am very new to programming (especially in C# with only a few months experience) so go easy!
这是我要遵循的拟议解决方案:
Here is the proposed solution I'm meant to be following:
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();
}
}
推荐答案
不要因为阅读该文档而对不理解递归感到难过.它不能很好地解释递归.(这是一个很难的概念-我也可能做得不好).最终，您需要做的就是尝试使您的程序执行您想做的事情.我将尝试从这种角度解释它.
Don't feel too bad about not understanding recursion as a result of reading that document. It doesn't do a very good job of explaining recursion. (It's a tough concept - I probably won't do that well either). Ultimately, what you have to do is try to make your program do what you would do. I'm going to try to explain it from that point of view.
递归非常有用，因为它使我们可以对解决方案中的步骤进行编码(一次)，然后使用刚刚计算出的结果作为输入来重复该步骤.尝试从自己的角度看问题，而不是一些任意的善良算法.您可能会太过努力，难以理解本文中的算法.
Recursion is useful, because it lets us code (once) a step in a solution, and then repeat that step using as input the results that were just calculated. Try to look at your problem from your point of view, not some arbitrary goodness algorithm. You're probably trying too hard to understand the algorithm from the paper.
尝试这样思考:在游戏开始时，玩家1进行游戏.您的程序必须为播放器2选择一个动作.但是播放器2必须考虑游戏的其余部分(每次可能的移动).
Try thinking like this: At the start of the game player 1 makes a play. Your program has to choose a move for Player 2. But player 2 has to think about the rest of the game (FOR EACH POSSIBLE MOVE).
- 玩家2可以从8种可能的动作中进行选择.
- 玩家1可以选择7
- 玩家2可以选择6
- 玩家1可以选择5
- 玩家2可以从4中选择
- 玩家1可以从3中选择
- 玩家2可以从2中选择
- 玩家1占据最后一个方块.
您可以将其改写为:
当前玩家为2，权衡当前玩家的所有可能剩余选择.
当前玩家为1，权衡当前玩家的所有可能剩余选择.
当前玩家为2，权衡当前玩家的所有可能剩余选择.
当前玩家为1，权衡当前玩家的所有可能剩余选择.
当前玩家为2，权衡当前玩家的所有可能剩余选择.
当前玩家为1，权衡当前玩家的所有可能剩余选择.
当前玩家为2，权衡当前玩家的所有可能剩余选择.
当前玩家为1，权衡当前玩家的所有可能剩余选择.
You can re-word this into:
current player is 2, give a weight to all possible remaining choices for the current player.
current player is 1, give a weight to all possible remaining choices for the current player.
current player is 2, give a weight to all possible remaining choices for the current player.
current player is 1, give a weight to all possible remaining choices for the current player.
current player is 2, give a weight to all possible remaining choices for the current player.
current player is 1, give a weight to all possible remaining choices for the current player.
current player is 2, give a weight to all possible remaining choices for the current player.
current player is 1, give a weight to all possible remaining choices for the current player.
您可以将其改写为:给定当前玩家，切换播放器，并权衡当前播放器的所有可能选择.
重复直到没有更多选择为止
You can reword this into:
given current player,
switch player and give a weight to all possible choices for the current player.
Repeat until no more choices are possible
您可以将其改写为:给定当前玩家，切换播放器和CheckGoodness()重复直到没有更多选择为止
You can reword this into: given current player, switch player and CheckGoodness() Repeat until no more choices are possible
因此，回到您的文章中.作者使用1&的玩家.-1.为什么?因为随着您越走越远的动作，您就必须调换玩家，并且在您降低等级时很容易切换玩家(我在这里只是在谈论玩家:
So, back to your write-up. The author uses players of 1 & -1. Why? Because as you pass the moves deeper and deeper, you must swap players, and it's very easy to switch players as you go down levels like this (I'm only talking about player here:
public int CheckGoodness(bool playerID)
{
playerID = -playerID;
if (!endConditionMet)
{
goodness = CheckGoodness(playerID);
}
return goodness;
}
与玩家一起，您必须传递一些东西，以表示剩余的所有可能动作的状态.问题是，如果您传递通过的东西作为参考，则所做的任何更改都会反映在原始数据中.确保没有发生这种情况.这可能就是@CodeInChaos建议您克隆的原因.
Along with the player, you have to pass something that represents the state of all possible moves remaining. The problem is that if you pass something that passes as a reference, any change you make will be reflected in your original data. Make sure that isn't happening. That is probably why @CodeInChaos suggested you clone.
请注意，在递归中，您必须确保始终有一种方法来结束调用序列.您必须修改最终条件所依赖的内容.在这种情况下，您可能采取的行动数量正在减少.否则，您将永远通话并耗尽内存.
Note that in recursion you have to make sure you ALWAYS have a way to end the call sequence. You must modify whatever your end condition is relying on. In this case, your number of possible moves is dropping. Otherwise you call forever and run out of memory.
添加了板级说明.
从大局思考.类是现实事物(例如对象)的表示.事物具有描述它的属性.这些是课程的数据.事物也可以做动作.这些是方法.我听说过的一个类的另一个定义是一个类，即数据和对该数据的操作.
Think about it from the big picture. A class is a representation of a real world thing (e.g. an object). A thing has attributes that describe it. These are the class's data. A thing also does actions. These are the methods. Another definition of a class that I've heard is a class is data and operations on that data.
考虑游戏中包含哪些对象.2个玩家和一个棋盘.没什么.
Think about what objects the game has. 2 players and a board. Not much else.
玩家可以移动，并具有唯一的标识符(在这种情况下为"X"或"O")，并且可以是人类或AI.我目前无法想到其他任何事情(重要的事情)，但是通常还有更多的事情可能发生，但是并没有真正影响程序(例如眼睛的颜色).这也是您可以使用继承的地方.您有一个带有抽象move方法的播放器类.从播放器继承的人类类具有从UI接受输入的覆盖move方法，而计算机/AI类则从播放器继承并通过计算具有良好等级的移动来覆盖move方法.
A player can move, and has a unique identifier (in this case either 'X' or 'O'), and can be either human or AI. I can't think of anything else (that matters) at the moment, but there are usually more things that could be there but don't really affect the program (like eye color). This is also where you could use inheritance. You have a player class with an abstract move method. A human class that inherits from player with an override move method that accepts input from the UI, a computer/AI class that inherits from player and overrides the move method by calculating the move with the goodness rating.
委员会有数据:
- 3 x 3的可能游戏位置网格(顺便说一下，这也可能是位置对象的集合)
- 可能需要代表1和2的玩家2
董事会的行动可能是:
- 接受玩家(人类或AI)的移动，并记录该移动是否有效，确定获胜&返回好动，坏动，游戏结束或获胜的指示符
- 可以有一种方法来返回当前比赛的获胜者
- 可能需要重置方法
- 可能有移动记录
您可以拥有一个静态的GoodNess类(可能需要一个更好的名称)没有数据，只有一个方法(或者这可能是board类中的另一个方法:
You could have a static GoodNess class (might need a better name) with no data but a single method (or this could be another method on the board class:
- 接受董事会，计算并计算返回善意数组，或者简单地返回最佳动作
AI可以在移动之前调用Goodness GetBestMove方法.
递归将与该GetBestMove方法隔离.The AI could call the Goodness GetBestMove method before making a move.
The recursion would be isolated to that GetBestMove method.请注意，这些都不是一成不变的.类是根据您认为应该包含的内容来定义的.这完全取决于您如何看待将是解决问题的最佳方法.如果您仍然遇到问题，请使用尝试执行的代码更新您的问题.在开始布局代码时，确实有助于绘制图表.
Note that none of these are set in stone. Classes are defined by what you think should be in it. It's all based on how you percieve would be the best way to solve the problem. If you still have trouble, update your question with the code you've attempted to make work. It really helps to draw out diagrams as you start to lay out your code.
祝您好运，希望对您有所帮助，我将尽力更好地监视StackOverflow通知.
Good luck, hope this helps, and I'll try to do a better job of monitoring StackOverflow notifications.
这篇关于Tic Tac Toe递归算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
