Hi,
Altough I know it has been done many times before, I'm trying to write a bot for tic-tac-toe that always does the best move. So far, I am only succeeding half.
Take this situation:
X | 1 | 2
---|---|---
3 | O | 5
---|---|---
X | 7 | 8
Circle may do a move now, and the computer is the circle. Now I wrote a method for the BoardState class that returns the percentage of wins as a float between 0 and 1.
The most obvious move ofcourse should be 3. However, the computer takes 5. I stepped trough the code and let it checked the return values of 3 and 5:
3: 0.9 = 90%
5: 1.0 = 100%
Is it a flaw in the algorithm, or a misimplementation in my code?
Here is the bot code:
public void RequestMove(Game game, int id)
{
Move bestMove = new Move();
float bestVal = -1.0f;
Move[] moves = game.State.GetPossibleMoves();
foreach(Move move in moves)
{
float chance = game.State.Evaluate(move, game.GetPlayerName(this));
if(chance<=bestVal)
continue;
bestVal = chance;
bestMove = move;
}
Console.WriteLine("Bot makes move {0}", bestMove.X+bestMove.Y*3);
game.DoMove(this, id, bestMove);
}
As you can see, the code loops trough all possibilities and takes the one with the highest win percentage. This part should be ok, but the following method returned those weird results from above:
public float Evaluate(Move move, PlayerName player)
{
PlayerName winner = CheckWinner();
if(winner!=PlayerName.Empty)
return winner==player ? 1.0f : 0.0f;
if(IsBoardFull())
return 0.5f;
BoardState board = new BoardState(this, move, player);
winner = board.CheckWinner();
if(winner!=PlayerName.Empty)
return winner==player ? 1.0f : 0.0f;
if(board.IsBoardFull())
return 0.5f;
Move[] moves = board.GetPossibleMoves();
float wins = 0.0f;
foreach(Move movetry in moves)
wins += board.Evaluate(movetry, player);
return wins/moves.Length;
}
The first part checks for a win in the current state, and returns the win/loss/draw, the second part checks for the same in the board after the move, and if the next board declares no winner, all possible moves are evaluated.
What's wrong with this?
