18 replies to this topic

[paso87]

Hi guys,

First of all I am new here and i'd like to say hello to all!

Now is the hard part for me...
I have a assignement for next week that i just can't really do it. I have to use minimax to make TTT game.Because i am not studying programming is a bit hard for me. I like programming but this seems to hard for me.I cannot understand how to write the algoritm in c++.So i have the mini max algoritm and TTT game.I have searched all over the Internet and i found some links to TTT games and source code but it does not help me.It pased a while since i had no programming course and know i must get it done. I know to program in c++ but only basics.If it was TTT for 2 players it was ok: no problem to get it done.But i have to play against computer and...big problem. So guyz can u help me understand the algorithm? As i said i can find it on the internet but it has no value for me...
How should i build a game tree?
What i return at a leaf?
How do i search entire tree?

On paper i can do this assignement and i know to play around with but when i should implement it ...

I am a bit dissapointed because i don't really get it ... So if you are willing to take some of your time to explain me in C++ it will be great.I am using VC++2008.
Thank you!

[WingedPanther]

Most TTT programs you will find do NOT implement mini-max, they will used static logic that corresponds to what the mini-max algorithm would do. What you have to do, each time it is the computer's turn, is consider each possible move, playing out all possible game results. When doing a virtual "self" move, it should always choose the move that gives it the best guaranteed result, and when doing a virtual "other" move, it should always choose the move that gives the worst guaranteed result. Usually, what you will do is use recursion with the recursive function receiving a game "state", proposed move, and player "turn", and returning a result that indicates "win", "lose", or "tie".

Without having some of your existing code (say, just to get it playable by two players), there's not a whole lot more to say without risk of giving you the solution.

[paso87]

huh is quite hard for me...
so the algorithm is like this:

int mm( int depth, int a, int b) // a, coresponding to min and max ?
{ if (depth==1)
return value of that leaf
else if node is a Max
return max value of childnodes
else if node is a Min
return mim value of childnodes
}

I get it on the paper but i don't get in C. So how do i climb up or down in a tree?
how could i build up that tree ?
WingedPanther how can i implement what you said ?

[WingedPanther]

Okay, your tree is a based on the following:
Given current state, child nodes represent possible "next" moves. So a blank board has 9 children, a board with an X has 8 children, a board with an X and an O has 7 children, etc.
The value of a leaf can be 0 = lose, 1 = tie, 2 = win.
I would use recursion to climb up and down a "virtual" tree so that only one path exists at any given time, along with the current "best" move found. Storing the entire tree in memory, while viable for TTT, is not a good idea in general.

As I said before, you really need to post your existing TTT code before I can offer much additional direction.

[paso87]

WingedPanther said:

As I said before, you really need to post your existing TTT code before I can offer much additional direction.

should i post 2 player TTT ?

[WingedPanther]

If that's what you have.

[paso87]

#include<iostream>

using namespace std;

char a[]={' ',' ',' ',' ',' ',' ',' ',' ',' '}; 

int size=9;

void matrice()
{cout<<"+-----+"<<endl;
 cout<<"|"<<a[1]<<"|"<<a[2]<<"|"<<a[3]<<"|"<<endl;
 cout<<"+-+-+-+"<<endl;
 cout<<"|"<<a[4]<<"|"<<a[5]<<"|"<<a[6]<<"|"<<endl;
 cout<<"+-+-+-+"<<endl;
 cout<<"|"<<a[7]<<"|"<<a[8]<<"|"<<a[9]<<"|"<<endl;
 cout<<"+-----+"<<endl;
}

int castiga()
{
    if ((a[1]=='X' && a[2]=='X' && a[3]=='X') || (a[1]=='O' && a[2]=='O' && a[3]=='O'))
        return 1;
    if ((a[1]=='X' && a[4]=='X' && a[7]=='X') || (a[1]=='O' && a[4]=='O' && a[7]=='O'))
        return 1;
    if ((a[1]=='X' && a[5]=='X' && a[9]=='X') || (a[1]=='O' && a[5]=='O' && a[9]=='O'))
        return 1;
    if ((a[2]=='X' && a[5]=='X' && a[8]=='X') || (a[2]=='O' && a[5]=='O' && a[8]=='O'))
        return 1;
    if ((a[3]=='X' && a[5]=='X' && a[7]=='X') || (a[3]=='O' && a[5]=='O' && a[7]=='O'))
        return 1;
    if ((a[3]=='X' && a[6]=='X' && a[9]=='X') || (a[3]=='O' && a[6]=='O' && a[9]=='O'))
        return 1;
    if ((a[4]=='X' && a[5]=='X' && a[6]=='X') || (a[4]=='O' && a[5]=='O' && a[6]=='O'))
        return 1;
    
    return 0;
}


 void player1()
 { int x,i;

reread:
    cout<<"Enter pozition player1:";cin>>x;
            if ((a[x]=='X') || (a[x]=='O'))
        {cout<<"Used!";cout<<endl; goto reread;}
            else {a[x]='X'; i=castiga();}
            if (i==1)
            {cout<<"Player 1 wins!"<<endl;size=0;}
            
 }
  void player2()
  {int x,i;
reread:
    cout<<"Enter pozition player2:";cin>>x;
            if ((a[x]=='X') || (a[x]=='O'))
        {cout<<"Used!";cout<<endl; goto reread;}
            else {a[x]='O';i=castiga();}
            if (i==1)
                {cout<<"Player 2 wins!"<<endl;size=0;}
            
 }

void main ()
{ 
    cout<<" Tic Tac Toe"<<endl;
    matrice();
    while ( size>0)
    {    player1();matrice();
        size--;
        player2();matrice();
        size--;
     }
    system("pause");
}

This is the code for 2 player game.I've made it in 30 mins i think... I wasn't too hard.
Now how do i implement AI player?

Edited by WingedPanther, 14 October 2011 - 04:05 PM.
add code tags (the # button)

[WingedPanther]

Start by changing player2() to make a call to a recursive function that uses your castiga() to check for a win.

[paso87]

Something like this ?

	else {a[x]='O';

			    if(castiga())

				{cout<<"Player 2 wins!"<<endl;size=0;}

			

			}

[WingedPanther]

Except you run through options in a loop, checking to see which are valid/optimal.

[paso87]

i am thinking about this but i have no idea...

[bbqroast]

See lazy foo's tutorial on AI:
What is AI - lazyfoo.net