• Advertisement
Sign in to follow this  

A tic-tac-toe superbot

This topic is 4772 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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?

Share this post


Link to post
Share on other sites
Advertisement
Fixed it already, I think. The method only calculates for the current player, not taking in account the moves by the opponent. Now it does, but the it is beatable. Here is the winning tactic:


0 | 1 | 2
---|---|---
3 | 4 | 5
---|---|---
6 | 7 | 8
Cross, please make your move: 6
0 | 1 | 2
---|---|---
3 | 4 | 5
---|---|---
X | 7 | 8
Bot makes move 4
0 | 1 | 2
---|---|---
3 | O | 5
---|---|---
X | 7 | 8
Cross, please make your move: 2
0 | 1 | X
---|---|---
3 | O | 5
---|---|---
X | 7 | 8
Bot makes move 8
0 | 1 | X
---|---|---
3 | O | 5
---|---|---
X | 7 | O
Cross, please make your move: 0
X | 1 | X
---|---|---
3 | O | 5
---|---|---
X | 7 | O
Bot makes move 3
X | 1 | X
---|---|---
O | O | 5
---|---|---
X | 7 | O
Cross, please make your move: 1
X | X | X
---|---|---
O | O | 5
---|---|---
X | 7 | O
Cross has won


It is indeed so, that when you calculate all possible moves, the middle one has a higher win percentage in the first move for the computer. However, it is a bad thing to do that, because as soon as the player X-es the opposite corner, the game is already finished.

What should I try to do now? Obviously, this way is not the way to go.

Share this post


Link to post
Share on other sites
Implement alpha-beta, or make a table big enough to hold all the positions in the game and compute the game value of each node, as it is done with endgame tablebases in chess or checkers.

Share this post


Link to post
Share on other sites
It was an idea worth exploring... :)

I tried the same thing for Connect-Four once, just for kicks.. One of the (many) problems with this method is that the computer had no knowledge of gauranteed wins, and would typically avoid them.

Take for instance a 2 move win-- if you screw up any of the two moves, the opponent wins, but as long as you play correctly the win is 100% certain. Looking at a win / loss ratio would actually have the computer avoid that situation, which is pure crazy! Coversly, the computer would persue it if the tables were turned.

Kudos for trying something different. As has been mentioned earlier, MinMax would give you the true 'super bot'.

Will

Share this post


Link to post
Share on other sites
Quote:
Original post by Sijmen

... as soon as the player X-es the opposite corner, the game is already finished.


No, it is not. Play at any side, not a corner.

And, obviously, Alvaro is right.

Share this post


Link to post
Share on other sites
Try adapting your percentage calculation so that when you consider future moves consider best moves.

Basically, don't try all possible moves for the next possible move (of both the player and the AI) take the one with the highest win percentage (a bit of recursion there).

Basically the AI should be taking the best move given that its opponent will make the best possible move for himself.

So far your AI has been calculating its percentages with the assumption it is playing against a moron (i.e. under the assumption that it will pick a move at random) while that's not the case. (Mathematicly speaking you haven't modeled your probability space properly).

So, your AI is working OK now it is picking a move that is most likely to lead to a win (given that it is playing against a moron). The move it makes gives it the highest possibilty of win (unfortunately it also leaves a small chance of a loss, but hey, the opponent is a moron anyway). :)

Did you get that?



Share this post


Link to post
Share on other sites
Quote:
Original post by A Guy from CRO
Did you get that?


Not entirely. Currently I'm trying every possible bot move, then every possible player move, and so forth - but what I understand of your explanation, is that I should /always/ anticipate on the best opponent move?

/edit:

Quote:
Basically the AI should be taking the best move given that its opponent will make the best possible move for himself.


So I assume that is right. I'll try to implement it as soon as I boot into Windows again, thanks!

Share this post


Link to post
Share on other sites
Quote:
Original post by Sijmen
Not entirely. Currently I'm trying every possible bot move, then every possible player move, and so forth - but what I understand of your explanation, is that I should /always/ anticipate on the best opponent move?



That's exactly what I meant. I haven't tried it, just thought of it but mathematics tells me it should work.

Share this post


Link to post
Share on other sites
I've put the calculating bot in the fridge to rethink it a litle bit, and started work on a remembering bot (which is easy using hte Tic-Tac-Toe bot API I know have).

This bot checks for every move if he has done it before, and if so, what the win-loss rate is. When there is a move he didn't try before, he tries it, and if all moves are tried, he uses the one with the highest win ratio.

When the game ends, the bot checks if he has won. If so, he adds 1 to the win/loss ratio of all moves from the past game, otherwise he substracts 1. With 'move' I mean the state of the board after the move has been done.

But now I have this problem. When I first play agianst the bot, he uses a predictable pattern (he simply tries all the moves 1 after 1). However, since the bot is always beaten, he never builds up any winning states.

What should I do - should I be changing something in the 'remember' thing, or should I let him learn some tactics, by deliberately losing (as player) when the bot makes a good move?

Share this post


Link to post
Share on other sites
You're making this way too hard for yourself. Your code shouldn't have to know anything about particular cases of where to go. For TTT use a simple minimax algorithm and pretty much all you have to do is tell it what a win and a loss look like. Then it will always pick the best move, guaranteed.
No more "Oops I missed the case where..."

Share this post


Link to post
Share on other sites
Quote:
Original post by iMalc
You're making this way too hard for yourself. Your code shouldn't have to know anything about particular cases of where to go. For TTT use a simple minimax algorithm and pretty much all you have to do is tell it what a win and a loss look like. Then it will always pick the best move, guaranteed.
No more "Oops I missed the case where..."


Thank you far the link, I will certainly try to implement it. However, I'd like to try other styles, too. Any suggestions on the 'teching'?

Share this post


Link to post
Share on other sites
Quote:
Original post by Sijmen
or should I let him learn some tactics, by deliberately losing (as player) when the bot makes a good move?


Yes, its called training the bot.

Share this post


Link to post
Share on other sites
Quote:
Original post by A Guy from CRO
Quote:
Original post by Sijmen
or should I let him learn some tactics, by deliberately losing (as player) when the bot makes a good move?


Yes, its called training the bot.


I came that far, but I was just wondering if I just just keep playing, or train the bot with a goal - that his, learn it a certain tactic. Probably I'll go for training it then.

Share this post


Link to post
Share on other sites
There isn't much training to do with Tic Tac Toe, cause u've only got 5983 possible gamestates(Thats including endstates and the blank board).

Share this post


Link to post
Share on other sites
You should use minimax (w/ alphabeta, to make this very, very fast). You should also use a hash table, with a hash that recognises congruent positions (ie. Flips, ect.).

You then record which is the best move to take, using the hash table (as your updating it). You could use two different hashes, Computed two completely different ways, before stringing them together, to make it harder to get a collission.

You then just look up via the hash-table, the best possible move for it.

Thats assuming 3*3 ttt, 4*4 would need a different approach.

From,
Nice coder


Share this post


Link to post
Share on other sites
Quote:
Original post by A Guy from CRO
There isn't much training to do with Tic Tac Toe, cause u've only got 5983 possible gamestates(Thats including endstates and the blank board).


That number I wrote was under the assumption that the bord is fixed. If you can rotate the board then the number of gamestates goes down drasticly.

Share this post


Link to post
Share on other sites
@Sijmen: If you are real keen on the training concept, have a look at Artifical Neural Networks, although it may be overkill for TTT, the results may be quite interesting and could be applied to other applications.

Unfortunately, I haven't done any work with ANN since Uni, and that didn't include too much programming, so I couldn't help you with that.

Share this post


Link to post
Share on other sites
When you showed how you played against the computer player, I didn't see much of a problem. The way the Xs moved is impossible to beat in actual tic-tac-toe, only to draw. So basically, it was a slight error if any.

I've beaten human players in tic-tac-toe with that tactic(:

Share this post


Link to post
Share on other sites
This is probobly not the solution you wanted, as it looks like you are doing some serious experimenting with AI, and related techniques.

However, Tic-Tac-Toe, being a simple game has a simple solution.
I am certain there is a brute force strategy that the computer could use to every game win or stalement the player.

(Also, a basic strategy is go for middle first, and in your sample game I didnt see this happening, which is odd since it is a crucial spot)

Look into it some more!

I would write more, but the longer the post I write the more likely it is to be blatently ignored :P
- Jacob

Share this post


Link to post
Share on other sites
Kevlar-X, its called minimax. And it solves the entire game in a few seconds.
Implement AlphaBeta and it will be solved in <1 sec.

Get some good move ordering, (like even using the evaluation function, to sort moves), and it'll be very very fast.

Its not too hard, you know....

From,
Nice coder

Share this post


Link to post
Share on other sites
I dont have experience with minimax but Nice coder has nicely given the solution already it seems.

(Though I still am convinced a switch case or a small pile of if/elses could easily solve Tic-Tac-Toe due to its simplicity)

In anycase, go with Nice Coders suggestion!

Cheers,
- Jacob

Share this post


Link to post
Share on other sites
I know you have your agenda: to make a bot that always makes the best move. And Nice Coder has given you all you need to know to do that, but wouldn't you rather have a bot that sometimes makes bad moves? I mean, honestly what would be the point of playing against a bot that you couldn't beat (although you would have a good chance at tying)?

Just food for thought.

Share this post


Link to post
Share on other sites
Perhaps, if you were to throw some random weights into the evaluation function? Maybe get it to go +- 10% of its value?

That would give you some chance of beating it.

Or else, you could go choose another (harder) game, and try and get it to play that, with a limited search depth.

From,
Nice coder

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Maybe u can use a lousier heurestic when calculating minimax/alphabeta values, and then the human might get some chance to win... or u can limit the search space, to maybe 2 ply, and play 100X100 TTT with the computer

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement