Making Board Games...

Hello all!

I have been programming in C++ for about a year now and am still working in the console programming department :( Oh well, i like it, i have been working mostly on simple programs dealing with mathematics and encryption as some of you may know. I would like to expand that knowledge into game programming a bit because i feel some of the things i will need to learn will help me out in the long run :) What i really want to do is make a simple, console based chess game. I was fascinated tonight after getting an Electronic Chess board for Christmas from one of my relatives. It amazed me how smart it was, i am good at chess but the first game i played against it it caught me up in a stale mate, i was shocked! How could a chess set plan, manuever and 'think' so well, i am now very interested in doing some game AI programming like this. Now maybe this belongs in the AI forum, if you moderators/administrators out there feel it does please move it to the appropriate forum (i am a Mod on one forum and an Admin on another so i know what its like :) )

Ok so what i want to know is: how can i make a chess game? More specifically what steps do i have to take to get to that skill level of programming? I am sure i will need to know trees (minimax i believe) and other things that come into play in the realm of AI/Game programming. I also understand that i will not be able to jump right into Chess programming, i will probably need to make a few stops along the way. So if anyone can point me in the right direction of good tutorials, books, etc. It would be greatly apprecaited. Although i still love Encryption and security at heart i really want to try my hand at this type of programming. Thanks again for any help you may be able to provide! :D

A great book i recommend is "Beginning C++ Game Programming" by Michael Dawson(Gamedev). I've been using this book for a couple of months and it really helped. Although, it is for n00bs to C++ like myself. Check it out at and retail book store(ex: Borders). :D

p.s. here is a link from this website for AI programming-->http://www.aihorizon.com/

Thanks for the recommendation, ill check it out. I know about AIHorizon and ive checked it out but its not really helping alot, advanced ideas and priniciples and such. No real beginner stuff. But once again thanks for the recommendation ill go on amazon and take a look.

AFAIK the AI used in Chess games is far from a being a begginer subject.

The client I use uses a minimax algorithm - that's probably about as simple as you're going to get, and IIRC it's included in the "advanced" ideas at AIHorizon.com.

Ok guys, here's how i understand it:

games like chess and tic-tac-toe use a Minimax tree as Sean said.

I decided that because chess is merely a ridiculously more complex form of tic-tac-toe (if you can say merely). My point is that they seem to be very similar yet one is much more complex than the other. So i decided to make a tic-tac-toe game.

I have just finished programming all of the program except for the AI. I have win parameters coded in and everything else. In fact here is my code. The only 2 things i need are the AI and i have to get the computer to randomly pick who goes first (i have a program or a tut around here somewhere where it shows you how to do that). So heres the code for the tic-tac-toe game:

Code:

---

#include <iostream>
#include <windows.h>

using namespace std;

void dispboard(char board[3][3]);

int main()
{
    //tic-tac-toe game
    //infinite loop
    while(1)
    {
        //clear screen;
        system("cls");
        //title
        cout<<"##########################\n";
        cout<<"##########################\n";
        cout<<"##    TIC - TAC - TOE  ##\n";
        cout<<"##      VERSION 1.0    ##\n";
        cout<<"##########################\n";
        cout<<"##########################\n\n";
        //menu
        cout<<"(1) Play\n";
        cout<<"(2) Exit\n";
        //get choice
        int mchoice;
        cout<<"Choice: ";
        cin>>mchoice;
        cin.ignore();
        //evaluate
        if(mchoice==2)
        {
            //exit
            cout<<"Exitting...";
            Sleep(1000);
            break;
        }
        if(mchoice!=1)
        {
            cout<<"Incorrect Choice";
            cin.ignore();
            continue;
        }
        //play game
        //initialize vairiables***************
        //init board
        char board[3][3];
        //fill board
        int bfi;
        int bf;
        for(bfi=1; bfi<4; bfi++)
        {
            for(bf=1; bf<4; bf++)
            {
                board[bfi][bf]='\0';
            }
        }
               
        //init piece vars
        char player;
        char computer;
        //************************************
        //get which the player wants
        cout<<"\n\nWhich Piece would you like to be?\n";
        cout<<"(1) X 's\n";
        cout<<"(2) O 's\n\n";
        //get
        int piecechoice;
        cout<<"Choice: ";
        cin>>piecechoice;
        cin.ignore();
        //evaluate
        if(piecechoice==1)
        {
            player='X';
            computer='O';
        }
        else if(piecechoice==2)
        {
            player='O';
            computer='X';
        }else{
            cout<<"Incorrect Choice!";
            cin.ignore();
            continue;
        }
        //begin game
        //vars
        int column;
        int row;
        int win;
        win=0;
        while(win==0)
        {
            system("cls");
            column=0;
            row=0;
            dispboard(board);
            //check for winner
            char checkletter;
            for(bf=1; bf<4; bf++)
            {
                for(bfi=1; bfi<3; bfi++)
                {
                    if(bfi==1)
                    {
                        checkletter=player;
                    }else if(bfi==2)
                    {
                        checkletter=computer;
                    }       
                    if((board[bf][1]==checkletter && board[bf][2]==checkletter && board[bf][3]==checkletter) ||
                      (board[1][bf]==checkletter && board[2][bf]==checkletter && board[3][bf]==checkletter) ||
                      (board[1][1]==checkletter && board[2][2]==checkletter && board[3][3]==checkletter) ||
                      (board[3][1]==checkletter && board[2][2]==checkletter && board[1][3]==checkletter))
                    {
                        //winner
                        if(checkletter==player)
                        {
                            //human won
                            win=1;
                        }
                        else if(checkletter==computer)
                        {
                            //computer won
                            win==2;
                        }   
                    }
                }   
            }
            if(win!=0)
            {
                break;
            }   
            cout<<"\n\n\n";
            cout<<"Where would You Like To Move?\n";
            cout<<"Column: ";
            cin>>column;
            cin.ignore();
            cout<<"Row: ";
            cin>>row;
            cin.ignore();
            board[column][row]=player;
        }
        //write winner
        if(win==1)
        {
            //human won
            cout<<"\n\nCongratulations You Won!\n\n";
            cin.ignore();
            continue;
        }
        if(win==2)
        {
            cout<<"Sorry You Lost!\n\n";
            cin.ignore();
            continue;
        }           
    }
    return 0;
}               

void dispboard(char board[3][3])
{
    cout<<"  1    2    3  \n";
    cout<<"    |    |    \n";
    cout<<"1 "<<board[1][1]<<"  | "<<board[2][1]<<"  | "<<board[3][1]<<"  \n";
    cout<<" ____|____|____\n";
    cout<<"    |    |    \n";
    cout<<"2 "<<board[1][2]<<"  | "<<board[2][2]<<"  | "<<board[3][2]<<"  \n";
    cout<<" ____|____|____\n";
    cout<<"    |    |    \n";
    cout<<"3 "<<board[1][3]<<"  | "<<board[2][3]<<"  | "<<board[3][3]<<"  \n";
    cout<<"    |    |    \n";
}

---

So anyone who can help me out/ point me in the right direction it would be greatly appreciated. Thanks!

The first thing you need for a minimax tree is the data structure - you need objects to represent the board after every possible move as far as your program is intended to think (for Tic-Tac-Toe it's feasible to go all the way). So you need to write the class definition, and then you need to put these objects into a searchable tree (some of the tutorials Prelude has written should help you considerably with this part).

Then you need to write code that will analyze your odds of a winning outcome for each possible next move - and then make that move.

Ok, after reading your post a few times i think i need to do something like this:

[x _ _]
[_ _ _]
[_ _ _]
| \
[X O _] [X _ _]
[_ _ _] [O _ _]
[_ _ _] [_ _ _]

etc. etc. etc. Thats a minimax tree right?

So what would the best way to approach the problem be? I mean as far as storing that information as you said? If() statements? Switch statements? Or something entirely different like a bunch of board[3][3] arrays and say

Code:

---

if(board1[3][3]=board[3][3]) {}...

---

Seems like tedious work, if you could perhaps tell me how you think the best way to approach it is? Or if you already did above perhaps you could clarify it for me. Thanks alot Sean!

I can't really tell what that diagram is. But basically this tree should be like a linked-list where each node can have multiple children. Your class therefore, should consist of a null-terminated array of pointers to nodes (the children nodes), possibly a pointer to the parent node (optional - it's possible to do without), and a 2d array representing the board.

If you don't understand all of that, you need to do some serious reading up on data structures before proceeding with this project.

The best approach is to take it step by step. Learn about data structures. Design the data structure. Learn about searching algorithms. Write the searching algorithm. It will be tedious work. If it isn't, you're probably not doing it right.

sorry the diagram was better but forums like these dont let you put too many spaces between words. My diagram was supposed to show the X where the user goes. Than the possible places where the computer can place an O, of course there are 8 possible places i only showed 2. Hopefully you understand the diagram now. I saw one like it when i read up on Minimax trees last night.

Ok so ill start trying to do some research on data structures (like arrays and such?) and linked lists (theres a chapter in my Learn C++ in 21 Days Book, but it wasn't represented good. Ok ill do that. If you or anyone else can point me in the right direction of some tutorials online or articles or websites etc. that can help me out please post them up. Thanks again Sean.

Quote:

---

sorry the diagram was better but forums like these dont let you put too many spaces between words

---

Code tags are useful for that kind of thing - they preserve spacing and all the characters are the same width.

You'll want to be familiar with the syntax for working with 2d arrays and pointers. Linked-lists will help you understand the concept a bit, but you'll really want to read some of the articles on other types of data trees (seriously - Prelude's articles are good. Check out her website @ eternallyconfuzzled.com). Binary search trees aren't terribly relevant, but you'll learn concepts you need to know.

ok thanks

http://aihorizon.com/essays/basiccs/trees/minimax.htm <-- That'll help a lot

Wow thanks, it has the tree right there! Thanks alot ill read it all. Thanks Sean for finding me that, i really appreciate it. Hopefully i will find a way to implement it into my code.

EDIT: Ok after reading that great article i think now im going to draw out the full minimax tree, and get that out of the way. Then ill evaluate the outcomes. After that ill figure out a way to integrate that into my code. Thanks again Sean. I cant imagine how big the tree is for chess!

> for(bfi=1; bfi<4; bfi++)
Perhaps learning C++ before going onto more advanced stuff would be a better idea.
Like for example the fact that arrays start at 0, not 1.

It's all very well looking at all these advanced things, but if you're always going to be shooting yourself in the foot over the basics, you're not going to make progress.

ok thanks but that function is working fine for some reason. I know c++ that was just easier for me to keep track of. Ill go back and change it and see if it makes a difference. No need to be rude :)

Ok, now i have found the general area that the problem is coming from. What i think is happening is that the variables are not being defined (compc and compr) If anyone has the time to sift through the deeply nested if statements please do so :) Id appreciate it. You can also see the AI behind my game. Whether it will work or not well as of now its not but i feel as if it will once i find what statements still need to be fixed/ added in to make it work. So if someone could take a look at it and see if they can find the problem without reprimanding me for using too many if statements or other things like that :D I dont know why im so psyched about this, maybe its just cause i have spent literally all day doing this, lol. So here she is the heart of my program that must be in cardiac arrest as of now :P

Oh and alot of this isnt finished yet. There will be even more if statements (though not many) and some of the if statements are empty cause i havent gotten around to filling them yet :)

Code:

---

void evaluateboard(char testboard[3][3], int compc, int compr, char player, char computer)
{
    //evaluates a board in order to find the best move
    //  init vars
    int rowi=0;
    int rowii=0;
    int rowiii=0;
    int coli=0;
    int colii=0;
    int coliii=0;
    int diagi=0;
    int diagii=0;
    int randrow=0;
    int randcol=0;
    //begin evaluation
    // if empty board
    if(testboard[0][0] == testboard[0][1] == testboard[0][2] == testboard[1][0] == testboard[1][1]
    == testboard[1][2] == testboard[2][0] == testboard[2][1] == testboard[2][2] == '\0')
    {
        //randomly pick
        srand((unsigned)time(NULL));
        randrow=(rand()%3);
        randcol=(rand()%3);
        compr=randrow;
        compc=randcol;
    }   
    // columns and rows
    for(int i=0; i<3; i++)
    {
        //columns
        //  2 in a row
        if((testboard[i][0] || testboard[i][1] || testboard[i][2])=='\0')
        {
            if(((testboard[i][0]==testboard[i][1]) ||
                (testboard[i][1]==testboard[i][2]) ||
                (testboard[i][0]==testboard[i][2])) &&
                ((testboard[i][0] && testboard[i][2]) != '\0'))
            {
                if(testboard[i][0]==computer || testboard[i][2]==computer)
                {
                    if(i==0)
                    {
                        coli+=50;
                    }
                    else if(i==1)
                    {
                        colii+=50;
                    }
                    else if(i==2)
                    {
                        coliii+=50;
                    }
                }
                else if(testboard[i][0]==player || testboard[i][2]==player)
                {
                    if(i==0)
                    {
                        coli+=20;
                    }
                    else if(i==1)
                    {
                        colii+=20;
                    }
                    else if(i==2)
                    {
                        coliii+=20;
                    }
                }
            }
            //rows       
            //  2 in a row
            if(((testboard[0][i]==testboard[0][i]) ||
                (testboard[1][i]==testboard[2][i]) ||
                (testboard[0][i]==testboard[2][i])) &&
                ((testboard[0][i] && testboard[2][i]) != '\0'))
            {
                if(testboard[0][i]==computer || testboard[2][i]==computer)
                {
                    if(i==0)
                    {
                        rowi+=50;
                    }
                    else if(i==1)
                    {
                        rowii+=50;
                    }
                    else if(i==2)
                    {
                        rowiii+=50;
                    }
                }
                else if(testboard[0][i]==player || testboard[2][i]==player)
                {
                    if(i==0)
                    {
                        rowi+=20;
                    }
                    else if(i==1)
                    {
                        rowii+=20;
                    }
                    else if(i==2)
                    {
                        rowiii+=20;
                    }
                }
            }
        }
    }   
    //test for single places
    //  rows and columns
   
    //diagonals LR=1 RL=2
    //  testing for 2 in a row
    if((testboard[0][0] || testboard[1][1] || testboard[2][2])=='\0')
    {
        if((testboard[0][0]==testboard[1][1] ||
            testboard[1][1]==testboard[2][2] ||
            testboard[0][0]==testboard[2][2]) &&
            (testboard[0][0] && testboard[2][2]) != '\0')
        {
            if(testboard[0][0]==computer || testboard[2][2]==computer)
            {
                diagi+=50;
            }
            else if(testboard[0][0]==player || testboard[2][2]==player)
            {
                diagi+=20;
            }
        }
        if((testboard[2][0]==testboard[1][1] ||
            testboard[1][1]==testboard[0][2] ||
            testboard[2][0]==testboard[0][2]) &&
            (testboard[2][0] && testboard[0][2]) != '\0')
        {
            if(testboard[2][0]==computer || testboard[0][2]==computer)
            {
                diagi+=50;
            }
            else if(testboard[2][0]==player || testboard[0][2]==player)
            {
                diagi+=20;
            }
        }
    }                   
    //find best location
    int drow=0;
    int pospositions;
    int poscolone;
    int poscoltwo;
    int posrowone;
    int posrowtwo;
    int dcol=0;
    if((rowi || rowii || rowiii) > ((coli && colii && coliii) && (diagi && diagii)))
    {
        //rows are the priority
        if(rowi > (rowii && rowiii))
        {
            //row one is the priority
            compr=0;
            drow=0;
        }
        else if(rowii > (rowi && rowiii))
        {
            //row two is the priority
            compr=1;
            drow=1;
        }
        else if(rowiii > (rowi && rowii))
        {
            //row three is the priority
            compr=2;
            drow=2;
        }
        pospositions=0;
        poscolone=0;
        poscoltwo=0;
        for(int c=0; c<3; c++)
        {
            if(testboard[c][drow]=='\0')
            {
                pospositions++;
                if(pospositions==1)
                {
                    poscolone=c;
                }
                else if(pospositions==2)
                {
                    poscoltwo=c;
                }       
            }
        }       
        if(pospositions==1)
        {
            compc=poscolone;
        }
        else if(pospositions==2)
        {
            if(poscolone==1 && poscoltwo==2)
            {
                if(coli > colii)
                {
                    compc=0;
                }
                else if(coli < colii)
                {
                    compc=1;
                }   
            }
            else if(poscolone==2 && poscoltwo==3)
            {
                if(colii > coliii)
                {
                    compc=1;
                }
                else if(colii < coliii)
                {
                    compc=2;
                }
            }             
            else if(poscolone==1 && poscoltwo==3)
            {
                if(coli > coliii)
                {
                    compc=0;
                }
                else if(coli < coliii)
                {
                    compc==2;
                }
            }
        }                   
    }
    else if((coli || colii || coliii) > ((rowi && rowii && rowiii) && (diagi && diagii)))
    {
        //columns are the priority
        if(coli > (colii && coliii))
        {
            //col 1 is priority
            compc=0;
            dcol=0;
        }
        else if(colii > (coli && coliii))
        {
            //col 2 is priority
            compc=1;
            dcol=1;
        }
        else if(coliii > (coli && colii))
        {
            //col 3 is priority
            compc=2;
            dcol=2;
        }
        posrowone=0;
        posrowtwo=0;
        pospositions=0;
        for(int r=0; r<3; r++)
        {
            if(testboard[dcol][r]=='\0')
            {
                pospositions++;
            }
            if(pospositions==1)
            {
                posrowone=r;
            }
            else if(pospositions==2)
            {
                posrowtwo=r;
            }       
        }
        if(pospositions==1)
        {
            compr=posrowone;
        }
        else if(pospositions==2)
        {
            if(posrowone==1 && posrowtwo==2)
            {
                if(rowi > rowii)
                {
                    compr=0;
                }
                else if(rowi < rowii)
                {
                    compr=1;
                }
            }                     
            else if(posrowone==2 && posrowtwo==3)
            {
                if(rowii > rowiii)
                {
                    compr=1;
                }
                else if(rowii < rowiii)
                {
                    compr=2;
                }
            }
            else if(posrowone=1 && posrowtwo==3)
            {
                if(rowi > rowiii)
                {
                    compr=0;
                }
                else if(rowi < rowiii)
                {
                    compr=2;
                }
            }
        }                           
    }
    else if((diagi || diagii) > ((rowi && rowii && rowiii) && (coli && colii && coliii)))
    {
        //diagonals are the priority
        if(diagi > diagii)
        {
            //diag one is priority
           
        }
        else if(diagii > diagi)
        {
            //diag two is priority
           
        }       
    }             
}

---

Thanks for anyone who has gotten this far (and read the code) or anyone else who can help me, its greatly appreciated. I started off thinking that i would be able to work my way to chess, now i dont think so lol

Thanks again everyone!

I programmed Tic Tac Toe a long time ago. The method I used was to hardcode moves required for a human or AI move. You can programatically generate these. Then based on the selected difficulty you can decide whether or not to use the correct data for the move or choose a random one. It worked quite well and it was very easy to code.

To do this, number each cell.

0 1 2
3 4 5
6 7 8

Now let's code the moves for the top row.

0 - 1,3,4
1 - 0,2,4
2 - 1,4,5

Now you might not want to use the actual data unless the player has moved more than once. Provide some randomness to the moves and then use the known data to respond once the board gets too complex to use random moves. This way the computer won't always move next to you or near the number selected all the time. Of course you would want to check to make sure the slot on the board was empty before placing the piece.

EDIT: You might want to group these into single moves and double moves. For instance a double move would look like this:

if (0 and 4) move is 8 or we lose

or
0,4,8

These all can be encoded into one byte move codes.

Ok thanks, ill take a look at implementing that design tomorrow, i gotta go to bed now though :)

But thanks ill definitely take a look, if its simpler than my algorithm im willing to try it :D

Quote:

---

These all can be encoded into one byte move codes.

---

Another reason to have a thorough look through the articles on AI Horizon.com - it teaches you good strategies for storing this kind of information - like how to store the location of every piece on a chess board.

on AIHorizon in that minimax tree bit? It explained everything about the minimax tree but not really how to implement it. Ill check out the site again. Im still working on my mathematical approach, i saw some code for another TTT program that used a mathematical approach so well see how i do on this. Maybe after i get this working ill try my hand at linked lists and such. Although i still have no idea how to go about implementing it. Ill keep looking, thanks!

If you are good at reading code, there is a complete tic-tac-toe game, including minmax algorithm, in the AI threads. Feel free to ask questions about it, I'll answer whatever I can. For tic-tac-toe, you can search the tree all the way to the bottom. A game that you can do after tic-tac-toe, that is closer to chess (but still fairly easy) is connect four. Next would be checkers. Then chess. Also, you might find the following link helpful, I know I did:

http://www.seanet.com/~brucemo/topics/topics.htm

Thanks! Ill take a look, i was thinking if i ever got this Tic Tac Toe to work that i would maybe move on to connect four. However i have to get this TTT to work first :) Thanks again, ill take a look!

EDIT: I dont see it on these ai threads... Perhaps on another site? Thanks

Ok, i just did some more searching for actual programs and came up with an interesting one. However this individual did use a Minimax tree they coded the entire thing into switch statements. The source file code is over 8000 lines long! This surely cannot be the best way to implement a minimax tree, however it is effective. She claims the computer cannot be beat. However i think if it were to go first it could be. Heres the link:

http://moonflare.com/code/tttwithoutloops.php

Good night all!

Here it is:

http://cboard.cprogramming.com/showthread.php?t=63324

Thanks ill look it over, luckily there isnt a big difference between C and C++ :)

Why do people still use C instead of C++?

Thanks again, ill take a look!

Quote:

---

Why do people still use C instead of C++?

---

Some people prefer it. It's simpler. Maybe people learnt it and it's just what they're comfortable with. And then of course there's always the need to maintain old programs, etc...

Oh ok, thanks. Looks more complicated to me i guess cause im used to C++ and i havent gotten too complicated with C++ lol

Anyway thanks, im still looking at a bunch of code and articles and stuff. Hopefully ill figure it out. Thanks everyone for all the help!

If you like, I can post my tic tac toe engine. Its just under 100 lines of code and uses the alphabeta optimisation of minimax. I actually tried to code it in as few lines as possible, without obfuscating anything. It's very simple to understand, would you like to see?