• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
LAURENT*

AI is harder than I thought

39 posts in this topic

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!

 

 

0

Share this post


Link to post
Share on other sites

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.
 

2

Share this post


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

Share this post


Link to post
Share on other sites

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.

0

Share this post


Link to post
Share on other sites

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*
0

Share this post


Link to post
Share on other sites

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. 

0

Share this post


Link to post
Share on other sites
#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);
}
0

Share this post


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

0

Share this post


Link to post
Share on other sites

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
0

Share this post


Link to post
Share on other sites
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
-1

Share this post


Link to post
Share on other sites

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. 

-2

Share this post


Link to post
Share on other sites

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
-2

Share this post


Link to post
Share on other sites

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...

2

Share this post


Link to post
Share on other sites

. 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
-3

Share this post


Link to post
Share on other sites

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.
0

Share this post


Link to post
Share on other sites

 

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
0

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  
Followers 0