• Create Account

## AI is harder than I thought

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

39 replies to this topic

### #1LAURENT*  Members

Posted 12 April 2014 - 09:18 AM

So I wanted to make an AI for my tic-tac-toe game that was really random. I tried a LOT of ideas that failed and still have more but, now I think I need some assitances. Sorry but I don't have code now. I'm making this thread to force myself to commit to ask for help later. See ya in 7 hours!

### #2Lactose  GDNet+

Posted 12 April 2014 - 09:36 AM

POPULAR

You probably don't want a truly random AI, as it would have a fair chance at playing something incredibly stupid (e.g. the opponent has 2 in row, and doesn't place to win, but just picks a random open tile).

Tic-Tac-Toe is a solved game -- there exists a strategy which will allow you to never lose (and if the opponent doesn't play perfectly, you will always win).1

Most people generally don't know this, so you can still make an AI which is challenging enough for this type of player.

What I'd suggest is something like, from highest to lowest priority:

Place a winning move if you can.

If you can't, block other player if he has winning move next turn.

Pick a random open tile.

This could be further tweaked, e.g. by adding a chance to not do the correct thing, but it should hopefully get you a good start.

1If you're interested in more about this, wikipedia has it explained fairly nicely, as far as I can recall. Also of note as a reference is "minimax".

Hello to all my stalkers.

### #3Getov  Members

Posted 12 April 2014 - 01:13 PM

If you want you can have a look at this code: click

Specifically line 146 - computerMove() function.

I have written this version in my early years when I was learning C++ and some parts of the code look horrible

but the algorithm for the AI should work just fine.

### #4Tutorial Doctor  Members

Posted 12 April 2014 - 03:26 PM

Yeah, you should look for a tic-tac-toe algorithm and use that, because if it is a soloved game, there is not really any way that you can make the computer 100% intelligent yet fair (If the computer was programmed to know the solution to the game it would win every time. Then it comes down to who goes first, or second (it depends on the solution of tic tac toe, which I don't know myself.)

They call me the Tutorial Doctor.

### #5Mouser9169  Members

Posted 12 April 2014 - 03:58 PM

You can used the 'solved' solution, and yes that will make it a better (perfect) tic tac toe machine, but I don't know if that really helps you with AI.

If anything, it would give you practice with matrix rotations and comparisons.

The problem you are going to run into is most 'trivial' games have been solved. A few you might try that would give you more room to play with the AI:

1) Don't know the name of it - 'game board' is lines of dots. You take away dots on your turn. You win if you opponent picks up the last dot.

2) Fox and the Hounds and its many variants - the simplest of which simply start with a 'character marker' on a hex grid. That players goal is to reach the edge of the board and 'escape'. Player 2 places blocking markers - 1 per turn. His goal is to 'trap' the fox.

3) You could go into games without perfect information: blackjack is a nice simple game to get started with there.

"The multitudes see death as tragic. If this were true, so then would be birth"

- Pisha, Vampire the Maquerade: Bloodlines

### #6Álvaro  Members

Posted 12 April 2014 - 04:34 PM

POPULAR

1) Don't know the name of it - 'game board' is lines of dots. You take away dots on your turn. You win if you opponent picks up the last dot.

It's called Nim, and it has been solved for over a hundred years.

### #7LAURENT*  Members

Posted 12 April 2014 - 06:59 PM

Sorry for the delay, my network was acting up and it look like my a driver got corrupted while I was updating my tablet. Anyways I've fix the problem and now i'm ready to code.

Here are 2 of my files. What I thought would be easy isn't so easy. In the first file in the while statement there is a switch case statement. Within one of the options it check for X and O turn and blit the surface after a button event. I just need the computer to blit the surface without a button event or make it own turn.

Thanks guys for the resources. I've try them out right now.

I screwed up the formatting in these 2. Ignore and look at the reply below

#include <iostream>
#include <SDL.h>
#include <SDL_image.h>
#include <time.h>
#include "Game.h"
Game::Game()
{
}

void Game::play(SDL_Surface *screen)
{    int continuer=1, turn=0, end=0;
position.x=0;
position.y=0;
SDL_FillRect(screen, NULL, SDL_MapRGB(screen->format, 255, 255, 255));
SDL_BlitSurface(board, NULL, screen, &position);
SDL_Flip(screen);
for(i=0; i<3; i++)
{
for(j=0; j<3; j++)
{
grid[i][j]=EMPTY;
}    }
while(continuer)
{
SDL_WaitEvent(&event);
switch(event.type)
{
case SDL_QUIT:
continuer=0;
break;
//Click management
case SDL_MOUSEBUTTONDOWN:
if(!end && grid[event.button.y/70][event.button.x/70]==EMPTY)
{
positionforme.x=((event.button.x/70)*70)+15;
positionforme.y=((event.button.y/70)*70)+15;

if(turn)
{   //Check for circles

grid[event.button.y/70][event.button.x/70]=CIRCLE;
SDL_BlitSurface(cmark, NULL, screen,
&positionforme);
SDL_Flip(screen);
turn=0;
}
//The type of AI I want is a random AI. I was going to use rand operator but I didn't have any idea for it at the time.

else
if(!turn)
{   //Check for X

grid[event.button.y/70][event.button.x/70]=CROSS;
SDL_BlitSurface(xmark, NULL, screen, &positionforme);
SDL_Flip(screen);
turn=1;
}
}
break;
}
continuer=check_victory(screen);    }}

int Game::check_victory(SDL_Surface* screen)
{
int
nowinner=0;     //It verifies if there is a winner
for(i=0; i<3; i++)
{
//horizontal Win Line
if((grid[i][0]==CROSS && grid[i][1]==CROSS && grid[i][2]==CROSS) || (grid[i][0]==CIRCLE && grid[i][1]==CIRCLE && grid[i][2]==CIRCLE))
{
positionwon.x=20;
positionwon.y=i*70+34;
SDL_BlitSurface(horizontale, NULL, screen,
&positionwon);
SDL_Flip(screen);
end=1;
return 0;
}
//Vertical Win
Line
if((grid[0][i]==CROSS && grid[1][i]==CROSS && grid[2][i]==CROSS) || (grid[0][i]==CIRCLE && grid[1][i]==CIRCLE && grid[2][i]==CIRCLE))
{
positionwon.x=i*70+34;
positionwon.y=20;
SDL_BlitSurface(verticale, NULL, screen,
&positionwon);
SDL_Flip(screen);
end=1;
return 0;
}
}        //Diagonal Win
Line        if((grid[0][0]==CROSS
&& grid[1][1]==CROSS && grid[2][2]==CROSS) ||
(grid[0][0]==CIRCLE && grid[1][1]==CIRCLE &&
grid[2][2]==CIRCLE))
{
positionwon.x=20;
positionwon.y=20;
SDL_BlitSurface(diagonale1, NULL, screen,
&positionwon);
SDL_Flip(screen);
end=1;
return 0;
}        if((grid[0][2]==CROSS &&
grid[1][1]==CROSS && grid[2][0]==CROSS) || (grid[0][2]==CIRCLE
&& grid[1][1]==CIRCLE &&
grid[2][0]==CIRCLE))
{
positionwon.x=22;
positionwon.y=20;
SDL_BlitSurface(diagonale2, NULL, screen,
&positionwon);
SDL_Flip(screen);
end=1;
return 0;
}        for(i=0; i<3;
i++)
{            for(j=0;
j<3;
j++)
{
if(grid[i][j]!=EMPTY)
{
nowinner++;
}
}
}
if(nowinner==9)
{
end=1;
return 0;
}        return 1;}
Game::~Game(){
SDL_FreeSurface(horizontale);
SDL_FreeSurface(verticale);
SDL_FreeSurface(diagonale1);
SDL_FreeSurface(diagonale2);
SDL_FreeSurface(xmark);    SDL_FreeSurface(cmark);}
#ifndef GAME_H_INCLUDED#define GAME_H_INCLUDED
enum {EMPTY, CIRCLE, CROSS};class Game{
public:
Game();        void play(SDL_Surface*
screen);        int
check_victory(SDL_Surface*
screen);        ~Game();
private:
SDL_Surface *board, *cmark, *xmark, *horizontale, *verticale, *diagonale1,
*diagonale2;        SDL_Event
event;        int grid[3][3], continuer,
i, j, turn, end, nowinner;
SDL_Rect position, positionforme, positionwon;};
#endif // GAME_H_INCLUDED

Edited by LAURENT*, 12 April 2014 - 08:53 PM.

### #8Tutorial Doctor  Members

Posted 12 April 2014 - 07:05 PM

Well, this is my first opportunity to experiment with this new subject I am looking into called Fuzzy Logic. And actually, I have been making an AI system that does stuff based on senses like sight and hearing, and touch. But this type of intellectual intelligence I haven't considered.

Yet, it seems that this is the perfect scenario to use Fuzzy Logic in. I am actually just now getting ready to write a program that implements fuzzy logic, perhaps I can use tic-tac-toe as a test case.

They call me the Tutorial Doctor.

### #9LAURENT*  Members

Posted 12 April 2014 - 07:13 PM

#include <iostream>
#include <SDL.h>
#include <SDL_image.h>
#include <time.h>
#include "Game.h"

Game::Game()
{
}
void Game::play(SDL_Surface *screen)
{
int continuer=1, turn=0, end=0;
position.x=0;
position.y=0;
SDL_FillRect(screen, NULL, SDL_MapRGB(screen->format, 255, 255, 255));
SDL_BlitSurface(board, NULL, screen, &position);
SDL_Flip(screen);
for(i=0; i<3; i++)
{
for(j=0; j<3; j++)
{
grid[i][j]=EMPTY;
}
}
while(continuer)
{
SDL_WaitEvent(&event);
switch(event.type)
{
case SDL_QUIT:
continuer=0;
break;
//Click management
case SDL_MOUSEBUTTONDOWN:
if(!end && grid[event.button.y/70][event.button.x/70]==EMPTY)
{
positionforme.x=((event.button.x/70)*70)+15;
positionforme.y=((event.button.y/70)*70)+15;//

if(turn)
{   //Check for circles turn
grid[event.button.y/70][event.button.x/70]=CIRCLE;
SDL_BlitSurface(cmark, NULL, screen, &positionforme);
SDL_Flip(screen);
turn=0;
}

//The type of AI I want is a random AI. I was going to use rand operator but I didn't have any idea for it at the time.
//Goodluck and thank you very much for this support

else if(!turn)
{   //Check for X turn
grid[event.button.y/70][event.button.x/70]=CROSS;
SDL_BlitSurface(xmark, NULL, screen, &positionforme);
SDL_Flip(screen);
turn=1;
}
}
break;
}
continuer=check_victory(screen);
}
}

int Game::check_victory(SDL_Surface* screen)
{
int nowinner=0;
//It verifies if there is a winner
for(i=0; i<3; i++)
{    //horizontal Win Line
if((grid[i][0]==CROSS && grid[i][1]==CROSS && grid[i][2]==CROSS) || (grid[i][0]==CIRCLE && grid[i][1]==CIRCLE && grid[i][2]==CIRCLE))
{
positionwon.x=20;
positionwon.y=i*70+34;
SDL_BlitSurface(horizontale, NULL, screen, &positionwon);
SDL_Flip(screen);
end=1;
return 0;
}
//Vertical Win Line
if((grid[0][i]==CROSS && grid[1][i]==CROSS && grid[2][i]==CROSS) || (grid[0][i]==CIRCLE && grid[1][i]==CIRCLE && grid[2][i]==CIRCLE))
{
positionwon.x=i*70+34;
positionwon.y=20;
SDL_BlitSurface(verticale, NULL, screen, &positionwon);
SDL_Flip(screen);
end=1;
return 0;
}
}
//Diagonal Win Line
if((grid[0][0]==CROSS && grid[1][1]==CROSS && grid[2][2]==CROSS) || (grid[0][0]==CIRCLE && grid[1][1]==CIRCLE && grid[2][2]==CIRCLE))
{
positionwon.x=20;
positionwon.y=20;
SDL_BlitSurface(diagonale1, NULL, screen, &positionwon);
SDL_Flip(screen);
end=1;
return 0;
}
if((grid[0][2]==CROSS && grid[1][1]==CROSS && grid[2][0]==CROSS) || (grid[0][2]==CIRCLE && grid[1][1]==CIRCLE && grid[2][0]==CIRCLE))
{
positionwon.x=22;
positionwon.y=20;
SDL_BlitSurface(diagonale2, NULL, screen, &positionwon);
SDL_Flip(screen);
end=1;
return 0;
}
for(i=0; i<3; i++)
{
for(j=0; j<3; j++)
{
if(grid[i][j]!=EMPTY)
{
nowinner++;
}
}
}
if(nowinner==9)
{
end=1;
return 0;
}
return 1;
}

Game::~Game()
{
SDL_FreeSurface(horizontale);
SDL_FreeSurface(verticale);
SDL_FreeSurface(diagonale1);
SDL_FreeSurface(diagonale2);
SDL_FreeSurface(xmark);
SDL_FreeSurface(cmark);
}


### #10LAURENT*  Members

Posted 12 April 2014 - 07:16 PM

#ifndef GAME_H_INCLUDED
#define GAME_H_INCLUDED

enum {EMPTY, CIRCLE, CROSS};
class Game
{
public:
Game();
void play(SDL_Surface* screen);
int check_victory(SDL_Surface* screen);
~Game();

private:
SDL_Surface *board, *cmark, *xmark, *horizontale, *verticale, *diagonale1, *diagonale2;
SDL_Event event;
int grid[3][3], continuer, i, j, turn, end, nowinner;
SDL_Rect position, positionforme, positionwon;
};

#endif // GAME_H_INCLUDED



MUCH MUCH Better! Sorry I had formatting problems. Man it just one problem after another today

### #11Tutorial Doctor  Members

Posted 12 April 2014 - 08:38 PM

Haha. I was trying to read it to see the flow of it, but i figured that is just how you wrote your code.

In my study of AI, I don't think it is best to make a random AI. Normal human intelligence isn't random.

The whole story goes that there is a computer that can beat any human at a game of chess. It learns your natural patterns and then adapts to beat you. So the more it plays you, the better it comes at beating you. Eventually it will beat you every time. This takes advantage of the fact that humans, no matter how random they try to be, are really not so random.

I actually think the scenario was a game of rock, paper, scissors, but the idea applies everywhere.

That is why I think fuzzy logic is the best way to do AI for such games as tic-tac-toe, because it becomes naturally fair, since the computer isn't using a mathematical algorithm for solving the game, but an imprecise observation and guessing at the solution to any current problem. So it is bound to make human-like errors, that keep the game fun.

And fuzzy logic is actually not as hard. I am doing research in this area, and I should be finished with it (an implementation as well) by next Saturday.

Edited by Tutorial Doctor, 12 April 2014 - 08:45 PM.

They call me the Tutorial Doctor.

### #12Álvaro  Members

Posted 13 April 2014 - 06:55 AM

POPULAR

The whole story goes that there is a computer that can beat any human at a game of chess. It learns your natural patterns and then adapts to beat you. So the more it plays you, the better it comes at beating you. Eventually it will beat you every time. This takes advantage of the fact that humans, no matter how random they try to be, are really not so random.

I actually think the scenario was a game of rock, paper, scissors, but the idea applies everywhere.

Oh, I see: Rock-paper-scissors, tic-tac-toe, chess, brain surgery... It's all the same in your mind, unencumbered by detailed knowledge of anything in this subject.

That is why I think fuzzy logic is the best way to do AI for such games as tic-tac-toe, because it becomes naturally fair, since the computer isn't using a mathematical algorithm for solving the game, but an imprecise observation and guessing at the solution to any current problem. So it is bound to make human-like errors, that keep the game fun.

And fuzzy logic is actually not as hard. I am doing research in this area, and I should be finished with it (an implementation as well) by next Saturday.

What time on Saturday do you think you'll be finished with it?

### #13Aardvajk  Members

Posted 13 April 2014 - 07:15 AM

POPULAR

Fuzzy logic is not applicable to tic-tac-toe. Tutorial Doctor has learned a new word, but seems to lack understanding of what it means.

For any given turn in tic-tac-toe, each square can be classified as:

• I will win if I go here
• Opponent will win next turn if he goes here
• If I go here, I can win the following turn
• None of the above

If 1 or 2 exist, the choice is clearly "go there". Otherwise choose 3 if one exists. If multiples of any category exist, choose one at random. If none apply, randomly choose a square. It may be possible to prove that the centre square is best here and that diagonals are better than the others.

There is absolutely nothing fuzzy about any of this.

http://en.wikipedia.org/wiki/Fuzzy_logic

Edited by Aardvajk, 13 April 2014 - 07:16 AM.

### #14Tutorial Doctor  Members

Posted 13 April 2014 - 08:20 AM

I wouldn't use fuzzy logic everywhere, because humans have exact knowledge too. And I use fuzzy logic in all of the above games.

The term is new, but the idea is as old as the first human.

Aardvajk, there are other classifications for squares, unless one presumes the computer knows the perfect game or the best move on every turn. In the event the square is classified as "none of the above," what does the computer do?

Most normal humans don't know the best move for every turn, unless they have studied the game (gotten more exact knowledge about it.)

So the way I would do it is keep the base fuzzier, and the increase in difficulty more exact.
Fuzzy logic isn't the end all be all.

I'm not sure what time l will have it done Saturday. I have to work during the week. I've just started to collect the info I have learned so far last night. I still do have a lot to learn about it, but I can get a simple implementation done by then.

A better link to info on fuzzy logic is:

http://www.seattlerobotics.org/encoder/mar98/fuz/fl_part1.html#INTRODUCTION

They call me the Tutorial Doctor.

### #15Álvaro  Members

Posted 13 April 2014 - 08:57 AM

We understand you are excited about fuzzy logic, TD. It is one of those approaches that have a sexy name and a good story to go with it. The same is true of neural networks and genetic algorithms.

But until you get some actual experience solving problems with fuzzy logic, please stop telling everyone that it is the solution to their problems. You simply don't know if that's the case.

When [smart] humans play tic-tac-toe, they generally can look a few moves ahead. Minimax search might be a better analog of how humans behave in this context.

### #16SerialKicked  Members

Posted 13 April 2014 - 09:11 AM

POPULAR

Aardvajk is right. Fuzzy state machines are not applicable to tic tac toe in any shape or form. The game AI has only one state "play to win", you can't really have a "play to win a bit" or "play to win a lot" states depending on external factors in something so basic as tic-tac-toe. It doesn't even really make sense in this context.

As an example: Where Fuzzy logic shines is for a guard AI in a stealth game . Well designed enough, it allows to have something between the patrol state and the alert state, giving more human-like reactions than what you'd get from a simple finite state machine. A guard would have heard you, but due to distance and other factors he isn't sure sure if it's an error or your location so it continues his patrol but with a wider cone of vision / improved hearing / etc depending on how sure he is to have heard an intruder.

Aardvajk, there are other classifications for squares, unless one presumes the computer knows the perfect game or the best move on every turn. In the event the square is classified as "none of the above," what does the computer do?

In that case any choices that would lead to have a 2 X (if you're X) in a row/column/diag  is to be picked, otherwise, none offer an advantage over the others.

If i recall correctly you need to pick center as a first move in all cases (no matter if you play first or second).

Most normal humans don't know the best move for every turn, unless they have studied the game (gotten more exact knowledge about it.)

Are we talking about the same game here ? Because yes they do. Play tic tac toe with a child for 10 games or so and none of you two will ever loose a game after that.

Edited by SerialKicked, 13 April 2014 - 09:12 AM.

### #17Tutorial Doctor  Members

Posted 13 April 2014 - 09:12 AM

If fuzzy logic wasn't already an established term, and used in many fields of engineering and programming systems, then I might sound more like a fangirl, but it is established, and used in more applications than I can yet expound upon. Again, the term is new, but the idea is old.

In short, it allows computers to mimic human decision making. And why wouldn't it be a good suggestion in the case of tic-tac-toe, chess, or any other game? Tic-tac-toe is all about decision making.

And yes, people can look a few moves ahead, but not a novice, in which case such an ability would represent an more skilled player.

The OP doesn't have to take it from me, perhaps they would be better taking it from you, since you are more experienced. Or perhaps they might look into it?

And I intend to solve a problem with fuzzy logic by Saturday.

They call me the Tutorial Doctor.

### #18Tutorial Doctor  Members

Posted 13 April 2014 - 09:20 AM

Aardvajk is right. Fuzzy state machines are not applicable to tic tac toe in any shape or form. The game AI has only one state "play to win", you can't really have a "play to win a bit" or "play to win a lot" states depending on external factors in something so basic as tic-tac-toe. It doesn't even really make sense in this context.

As an example: Where Fuzzy logic shines is for a guard AI in a stealth game . Well designed enough, it allows to have something between the patrol state and the alert state, giving more human-like reactions than what you'd get from a simple finite state machine. A guard would have heard you, but due to distance and other factors he isn't sure sure if it's an error or your location so it continues his patrol but with a wider cone of vision / improved hearing / etc depending on how sure he is to have heard an intruder.

Aardvajk, there are other classifications for squares, unless one presumes the computer knows the perfect game or the best move on every turn. In the event the square is classified as "none of the above," what does the computer do?

In that case any choices that would lead to have a 2 X (if you're X) in a row/column/diag  is to be picked, otherwise, none offer an advantage over the others.

If i recall correctly you need to pick center as a first move in all cases (no matter if you play first or second).

Most normal humans don't know the best move for every turn, unless they have studied the game (gotten more exact knowledge about it.)

Are we talking about the same game here ? Because yes they do. Play tic tac toe with a child for 10 games or so and none of you two will ever loose a game after that.

These things assume that the opponent/computer always plays the optimal move on every turn. Not all 2 year olds know how to do this.

Here is a case and point. I once played the highest difficulty on the chessmaster PC game. I knew the computer would play optimally, and that it was taught the best move in every case. But in some cases, it would play the best move provided I play the best move. So I played an off-the-wall move. The next move, the computer made a blunder.

Then I captured the computer's queen, and then the game froze indefinitely, because it could not compute a win. Not fair.

So, not only does such logic make a game more fair (I don't want to have fun, and not loose every time) but it actually can be fine tuned where you can increase difficulty based on a skill level. Also, the computer won't be so predictable (it would be predicable if a human counterpart also knew how to exploit the fact that at the end of the day, a computer is a computer, and it might have a few bugs somewhere).

I'd love to play a game of chess against a computer that uses human reasoning. It makes the game more unpredictable, yet not random, because usually, every move is with some measure of intent, for better or worse.

Edited by Tutorial Doctor, 13 April 2014 - 09:22 AM.

They call me the Tutorial Doctor.

### #19Aardvajk  Members

Posted 13 April 2014 - 09:25 AM

POPULAR

This is the point in a thread that Nathan222 mentions JARVIS normally.

Derailed = true. Sorry if I was any part of that. Just like newcomers to be given decent advice on here.

### #20Lactose  GDNet+

Posted 13 April 2014 - 09:28 AM

POPULAR

Here is a case and point. I once played the highest difficulty on the chessmaster PC game. I knew the computer would play optimally, and that it was taught the best move in every case. But in some cases, it would play the best move provided I play the best move. So I played an off-the-wall move. The next move, the computer made a blunder.

Then the computer did not play optimally. You might have discovered a bug in the AI code for the chess program, or it might have been completely unrelated to what you were doing, and just triggered a different bug.

This is actually a concept you hear quite often if you follow chess a bit -- "well, just play something completely random/unexpected and you'll circumvent the logic behind the other person's moves, and you'll beat a grand champion even if you're a noob".

A good chess player will crush you instantly if you make any "silly" moves like that -- they are silly for a reason. If using them was a good tactic, then the good chess players would use that sort of thinking.

That said, I don't necessarily agree with every Tic-Tac-Toe player being able to play it flawlessly, but I don't see Tic-Tac-Toe AI as being a fuzzy logic shaped problem.

Edited by Lactose!, 13 April 2014 - 04:25 PM.

Hello to all my stalkers.

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.