Tic Tac Toe recursive algorithm
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.
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();
}
}
Answer
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.
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).
- Player 2 can choose from 8 possible moves.
- Player 1 can choose from 7
- Player 2 can choose from 6
- Player 1 can choose from 5
- Player 2 can choose from 4
- Player 1 can choose from 3
- Player 2 can choose from 2
- Player 1 takes the last square.
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
You can reword this into: given current player, switch player and CheckGoodness() Repeat until no more choices are possible
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;
}
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.
EDIT: Explanation of board class added.
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.
Think about what objects the game has. 2 players and a board. Not much else.
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.
The board has data:
- a 3 by 3 grid of possible play locations (This COULD be a collection of location objects too, by the way)
- might need representation for players 1 & 2
The actions of the board COULD be:
- accept a player's (Human or AI) move, records it if valid, determines win & returns an indicator of good move, bad move, game over or win
- Could have a method to return winner of current game
- Probably need a reset method
- Could have a move history
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:
- accept a board, calculate & return goodness array, or simply return best move
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.
Good luck, hope this helps, and I'll try to do a better job of monitoring StackOverflow notifications.