Sign in to follow this  
LAURENT*

AI is harder than I thought

Recommended Posts

LAURENT*    779

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!

 

 

Share this post


Link to post
Share on other sites
Getov    498

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 :D, 

but the algorithm for the AI should work just fine.
 

Share this post


Link to post
Share on other sites
Tutorial Doctor    2573
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.)

Share this post


Link to post
Share on other sites
Mouser9169    401

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.

Share this post


Link to post
Share on other sites
LAURENT*    779

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()
{ 
cmark= IMG_Load("cmark.jpg");    
xmark= IMG_Load("xmark.jpg");    
board= IMG_Load("board.jpg");    
horizontale=IMG_Load("horizontale.jpg");    
verticale=IMG_Load("verticale.jpg");    
diagonale1=IMG_Load("diagonale1.png");    
diagonale2=IMG_Load("diagonale2.png");
}

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*

Share this post


Link to post
Share on other sites
Tutorial Doctor    2573

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. 

Share this post


Link to post
Share on other sites
LAURENT*    779
#include <iostream>
#include <SDL.h>
#include <SDL_image.h>
#include <time.h>
#include "Game.h"

Game::Game()
{
    cmark= IMG_Load("cmark.jpg");
    xmark= IMG_Load("xmark.jpg");
    board= IMG_Load("board.jpg");
    horizontale=IMG_Load("horizontale.jpg");
    verticale=IMG_Load("verticale.jpg");
    diagonale1=IMG_Load("diagonale1.png");
    diagonale2=IMG_Load("diagonale2.png");
}
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);
}

Share this post


Link to post
Share on other sites
LAURENT*    779
#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

Share this post


Link to post
Share on other sites
Tutorial Doctor    2573

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

Share this post


Link to post
Share on other sites
Tutorial Doctor    2573
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

Share this post


Link to post
Share on other sites
alvaro    21246
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.

Share this post


Link to post
Share on other sites
Tutorial Doctor    2573

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. 

Share this post


Link to post
Share on other sites
Tutorial Doctor    2573

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

Share this post


Link to post
Share on other sites
SerialKicked    611

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.

 

No one told you that it wasn't used for a lof of things. But like every AI system it's a tool. And as with all tools they have specific uses.I wouldn't use Fuzzy logic to solve tic tac toe and i wouldn't use a screwdriver to fell a tree.

 

second post addressed to me[...]

 

No they do not assume that. With the rules we explained regarding tic tac toe, what the opponent play doesn't matter. If he play more or less correctly he'll get a draw, if not he'll loose period.

 

The chess analogy isn't relevant and it's off topic, and you may want to read a bit more about the logic systemS used in chess before jumping to conclusion.

 

 

Seriously...

Share this post


Link to post
Share on other sites
Tutorial Doctor    2573

. 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

 

That is the type of reasoning I am talking about. I come to this type of reasoning in pretty much all games. Because there is always a little uncertainty in real reasoning. And fuzzy logic considers this. It is not always a matter of true or false, because the condition is uncertain. When I am playing against a human opponent, I am not sure what move they will make, because they might not play the "best move." Bobby Fischer once played a move that was not the "best move" by the book, but because he understood the condition by another reasoning, he actually was playing the game against his opponent (using his pride) and not against the book.

 

That is all I will say on this subject though. The response was to how AI could be done, using chess as an example (more complex game). It is relevant.  

Edited by Tutorial Doctor

Share this post


Link to post
Share on other sites
Aardvajk    13207

Um.......................I had this idea to use the rand operator. Not working like I hoped. Anyone thinks this will work?


Depends how you plan to use it really :)

Normal use of rand is with modulus like

int i = rand() % 10;

That will give you a random number between 0 and 9 inclusive. If you are trying to pick a random square, that would be the way to use it. Replace 10 with 9 to get an index into the (zero based) array of squares.

Share this post


Link to post
Share on other sites
Waterlimon    4398

 

Um.......................I had this idea to use the rand operator. Not working like I hoped. Anyone thinks this will work?


Depends how you plan to use it really smile.png

Normal use of rand is with modulus like

int i = rand() % 10;

That will give you a random number between 0 and 9 inclusive. If you are trying to pick a random square, that would be the way to use it. Replace 10 with 9 to get an index into the (zero based) array of squares.

 

[insert rant about this method not actually producing uniformly distributed random integers]

 

You need to generate the random integer in a loop, such that if the random integer is at the very end of the range (specifically, larger than MAX_RANGE - MAX_RANGE%10) you throw it away and generate a new one, until you get one that is not a part of that "remainder" at the end of the range (thus the loop)

int range=10;
int rand=randInt();
//while (rand > MAX_INT - MAX_INT%range) <-dis wrong. dont do dis.
while (rand >= MAX_INT - MAX_INT%range) //if result part of remainder at end of possible random values, regen
{
    rand=randInt();
}
return rand % range;

Though, better read an article written by someone who loves PRNGs to be sure this is correct. ;)

Edited by Waterlimon

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this