AI contest: Connect four

OK, time for a new competion!
The last one was perhaps finished and judged a little abruptly, but I blame force majeure. :)

This time the task will be to write an AI for a well-known and simple board game -- connect four.
You will each write your own AI and your programs will face each other in a virtual tournament until one program is the winner!

I thought it'd be fun with a virtual tournament, and connect four is a relatively simple game to write AI for.

The function prototype will be the following:

Code:

---

namespace Nickname{
    int getMove( const Board& board, char player );
}

---

The board argument will contain the playing field. The source code for this class will be provided below.
The player argument will be either 'X' or 'O' depending on what character belongs to you.
The function will return the column where you wish to move your next piece.

Rules:

• Don't take long time to determine your move, it's impossible to set any fixed time constraints, but the moves should be made "instantly". :)
• The program who defeats the other programs in a tournament will be the winner.

Participation
As this contest requires a little more work than the others, please announce in this thread if you are willing to participate. Then, when you know the number of participants you can decide if it's worth the time and effort to write the program.

Here's a list of interested persons The persons in bold have submitted:

• Jeremy G
• PJYelton
• LuckY
• jlou
• goodvelo
• vasanth
• Perspective

If you are on this list but won't submit anything, please let me know.

You don't have to write a super-advanced algorithm. You could just do:

Code:

---

namespace ImLazy{
    int getMove( const Board& board, char player ){
        return std::rand()%Board::width;
    }
}

---

Deadline
The deadline is November 10th.
Post your submissions to p 0 4 p s t (a) efd.lth.se or by PM
I'll confirm each submission I recieve.

Definatly want to play in this one.


edit: PS: If this contest does happen, I expect a lot of solutions will be of the 'look ahead' nature. IE: considering all possible moves etc. I think a timing routine should time the call to this function. LIke just find out how much time the function call took, and if it takes longer then > x ammount of time print a warning + elapsed time over acceptable. At the end of the game, total time penalties might be used to evaluate winner of the contest.

Perhaps judement should be based points.
All contestants start with 200 points
Winning = 1000 points.
Lose = 300 points (such that code works and can be used to play the game, thats worth points)
Per character of solution = -1 points
Per second over time constraint = -1 points
Per second under time constraint = 1 point
Winning under 15 moves = 15-move count
Winning over 15 moves = 15-move count (so if it takes 20 moves to win, you lose 5 points)


Just my suggestions to make contest better (IMHO).

Count me in!

Couple of questions, first off are we allowed to create other functions within the namespace other than getMove?

Second, I tried compiling your code and got a couple of errors, first off there is an undeclared variable named moveScore[] in the board constructor, I assume this is probably from your AI and can be deleted but thought I'd ask first. Also, for the line in the board class declaration:

Code:

---

    static const int width=7,
                    height=6,
                    toWin=4;

---

I get multiple errors, all saying "Illegal pure syntax, must be '= 0' " and "pure specifier can only be specified for functions"

I admit I'm not extremely familiar with static variables and was having the same problems with the square root contest. I'm using MSVC++ and I assume this is compiler specific, but not sure what the best way around this is.

>I get multiple errors, all saying "Illegal pure syntax, must be '= 0' " and "pure specifier can only be specified for functions"
Your compiler is too old. Is this VC++ 6.0? The way to fix it is to initialize static const members outside of the class declaration:

Code:

---

class A {
  static const int a;
  //...
};

const int A::a = 10;

---

This is the older syntax that all compilers accept.

Ok, thanks Prelude, got it to work by doing your suggestion.

I'm using VC++ 6.0, you'd think it would work ;)

>I'm using VC++ 6.0, you'd think it would work
I'm surprised anything works in VC++ 6.0. :p

I'd be down for this.

Quote:

---

Originally Posted by PJYelton

Couple of questions, first off are we allowed to create other functions within the namespace other than getMove?

---

Yes, you may fill your namespace with anything you wish.

Quote:

---

Originally Posted by PJYelton

Second, I tried compiling your code and got a couple of errors, first off there is an undeclared variable named moveScore[] in the board constructor, I assume this is probably from your AI and can be deleted but thought I'd ask first. .

---

Yes, remove moveScore from the constructor.
Just as you guessed, I was reusing old code.

Jeremy, it's hard to set a certain time limit, because everyones compiler and hardware is different (my primary computer is currently 450 Mhz).
I was thinking of a tournament where everyone plays against everyone and is awarded 3 points for a win and 1 point for a draw, but I'll consider your suggestions.
One thing though, I will not remove points for every character in the source code. :) Please comment your code as much as possible! :)

The judging of this competition could be made quite exciting by posting the the results of one game per day (or one move :) ), instead of just posting who won the competition.

Quote:

---

Originally Posted by Sang-drax

The judging of this competition could be made quite exciting by posting the the results of one game per day (or one move :) ), instead of just posting who won the competition.

---

i havent looked at your code yet, but it would be cool to log the games to a file that could be played back. That way you could post the game files and people could watch the replays! If i have time i can assist in adding this functionality.

Quote:

---

Originally Posted by Sang-drax

Jeremy, it's hard to set a certain time limit, because everyones compiler and hardware is different (my primary computer is currently 450 Mhz).

---

Very true. But since it is being run by you, on your computer it's the same system specs for every one? Thus if you set a time limmit, the score will be relative to the machine for every one. That is to say, how slow or fast any of our routines are the results are based on your one machine. So no matter what the score is every one is graded on the same curve. Do you see what I mean?

A max time limmit could be set for 1 second. I can code my solution to run on my machine in .25 seconds while a competitor could code theirs to run in .25 seconds on their slower machine. When we compare our strict time results we tie, when we factor in the machine performance the competitor is the winner. By running both our code on one machine (the judges) that machine performance is calculated in and the results become a good measure of efficiency.

The time limmit could be tweaked, if you say set the time limmit to .5 seconds and every one is taking WAY longer than that, to avoid having super negative scores simply raise time restraint and do it again. But no matter what, the score for time penalties will reflect the efficiency of every ones code.


I'm not demanding their be a time limmit or trying to tell you how to run the competition, I'm just trying to make helpful (hopefully) suggestions. Take them or leave them, no harm no foul.

Sounds like fun. Count me in.

I'll try this... can't guarantee that I'll have time to finish, but I'll try.

Quote:

---

Originally Posted by Perspective

i havent looked at your code yet, but it would be cool to log the games to a file that could be played back. That way you could post the game files and people could watch the replays! If i have time i can assist in adding this functionality.

---

Yeah, that'd be a nice feature.
The log format can be made really simple, just a list of integers which represents the moves by the players.

I will get the time to implement this before the deadline, and hopefully you or someone else can help me test and debug the code before the actual tournament.

Looks like we already have enough contestants to make an interesting contest! Start coding everyone! :)

I was thinking of letting each match be settled by playing a thousand games and count the number of wins, which would allow some self-adaptation and learning. But this is probably too advanced.

If you have any ideas for time constraints, feel free to share them. Jeremy has provided some interesting ideas. But as for now, just aim for a 'fast' algorithm (well below one second/move).

Yeah, I think the biggest problem with having each AI play each other a thousand times is unless you specifically code it to learn you'd just end up with hundreds of identical games :D

I dunno, but the gamefiles seem to be missing the actual main function that handles the running of the game... Can we get the working game in full? It would help me out a bit.

I just made a stupid little driver to test out the boards functionality, you're welcome to use it.

Code:

---

int main()
{
        Board myBoard;
        printBoard(myBoard);
        int z;

        while (1)
        {       
                do
                {
                        cin>>z;
                }while (!myBoard.canMove(z));

                myBoard.move(z, 'X');
                printBoard(myBoard);
                if (myBoard.checkWin()!=' ')
                        break;
                do
                {
                        cin>>z;
                }while (!myBoard.canMove(z));

                myBoard.move(z, 'O');
                printBoard(myBoard);
                if (myBoard.checkWin()!=' ')
                        break;
        }
        cout<<"Winner!"<<endl;

        cout<<"Testing at function.  The character at spot 4,1 is a \'"<<myBoard.at(4, 1)<<"\'"<<endl;

        return 0;
}

---

Here's mine. No manual entry except an enter between moves so I can see how good the AI is at defeating itself.

Code:

---

static const char PLAYER1 = 'X';
static const char PLAYER2 = 'O';

int main() {
  srand(time(0));
 
  Board board;

  char turn = PLAYER1;

  while (true) {
    int move = <<your namespace here>>::getMove(board, turn);
   
    if (!board.canMove(move)) {
      std::cout << "* OUT OF COLUMNS *\n";
      break;
    }
   
    board.move(move, turn);
       
    printBoard(board);
    std::cout << turn << " went in column " << move << std::endl;
   
    if (board.checkWin() != ' ') {
      std::cout << turn << " WON THE GAME!\n";
      break;
    }
   
    std::cin.get();
       
    turn = turn == PLAYER1 ? PLAYER2 : PLAYER1;
  }
 
  return 0;
}

---

The only problem is that Connect 4 has been solved. So basically, the second player can always induce at least a draw in every game.

Actually thats not true. It HAS been solved but it has been proven to be a win for player 1, not a draw. But coding your AI to implement all of the ideas necessary to win every time as player 1 is a completely different thing and my hats off to anyone here who can do it :D

I was just thinking about it and a nice Win32 app would be a lot nicer to look at than that ugly console program, so I threw together a quick, dirty Connect4 game. The source is attached. Just go into the file YOURDATA.h and replace the defines (they specify your getMove() function and your header file). Then stick your header in the project directory and compile. You can make each move yourself by clicking on the column or click the "Let AI Move" button to let your AI do its job.

Tell me what you think and do what you want with the code. If you make any changes I'd love to see them.

[edit]
I just change the code a tad to allow you to define two different getMove() functions for player 1 and player 2.
[/edit]

Victor Allis solved connect four for white. But I suspect that for me to understand his thesis and search techniques will take more than a month.

Hi All,
My C++ is very rusty, but I hope to submit an entry. FYI, I'm a C.S. grad., LabVIEW programmer, and also using [pirated] MSVC 6.0.
Regarding previous post:
> Victor Allis solved connect four for white
does "player 1" = "white"?

and can our code determine whether we're playing as "player 1" or "player 2"?

Cheers!

Quote:

---

and can our code determine whether we're playing as "player 1" or "player 2"?

---

You only know what the board look like and what player you are. By counting the number of pieces on the board it's possible to determine whether you started the game or not, whatever you need that information for.

BTW, how are you all doing? :)

ok count me in....... sounds intresting..
And wahst the maximum time my function can take to make a move... So that I can limit the depth of search trees.... thanx in advance

and the driver code has to check for invalid moves... since a rouge function can place its coin anywhere in the array and cheat..

Ok, so no guarantee that 'X' moves first? Also, can we assume that the players are always 'X' and 'O'?

My AI is more or less done, just in the process of tweaking the eval function a little bit to get the best results.

Quote:

---

Originally Posted by vasanth

ok count me in....... sounds intresting..
And wahst the maximum time my function can take to make a move... So that I can limit the depth of search trees.... thanx in advance

---

After the function has executed 500 milliseconds, a time penalty will be issued, depending on the amount of overtime.
My current computer is 450 MHz, but I will hopefully have a new laptop when the judging begins.

You could make the depth easily changable, so I can decrease it if the function takes too long.

Quote:

---

Originally Posted by vasanth

and the driver code has to check for invalid moves... since a rouge function can place its coin anywhere in the array and cheat..

---

Yes, an invalid move will result in a lost game.

Quote:

---

Originally Posted by PJYelton

Ok, so no guarantee that 'X' moves first?

---

No.

Quote:

---

Originally Posted by PJYelton

Also, can we assume that the players are always 'X' and 'O'?

---

Yes.

Quote:

---

Originally Posted by PJYelton

My AI is more or less done, just in the process of tweaking the eval function a little bit to get the best results.

---

Yes, the eval function is the crucial part. :)

I will begin working on the judging program next week, when I have some more time. It won't be anything that advanced.

Just out of curiosity, is there a particular reason we can't just assume 'X' is going first? Seems like a pointless addition of time to our algorithm to have to figure out who moved first especially when you consider we are being graded on time.

No biggee though, just wondering if there was a reason ;)

It is easy enough to figure out if you are going first by checking if the board is empty before you move (at least that's what I've done).

Quote:

---

Originally Posted by PJYelton

Just out of curiosity, is there a particular reason we can't just assume 'X' is going first?

---

Why do you need to know?
To me, the knowledge of who started the game isn't needed.

Quote:

---

Why do you need to know?
To me, the knowledge of who started the game isn't needed.

---

Don't want to give my AI away, but lets just say its important. I think Lucky has the same idea ;)

Like I said, no biggee. I'll just do what Lucky's doing, check the first time around and store instead of checking every move.

Here' s an early version of the program I'll use to judge the contest.

It saves each game in a replay file, which can be used to replay old games move by move.

The final version will look something like this. If you have time, please provide feedback about functionality, bugs and suggestions.

EDIT:

Quote:

---

I dunno, but the gamefiles seem to be missing the actual main function that handles the running of the game... Can we get the working game in full? It would help me out a bit.

---

This is probably what you're looking for.

Just looked at your Win32 version, LuckY. It works fine. I recommend it to you if you need to bugcheck/fine-tune your submissions.
Perhaps I could modify it so it can read the log files created by my program. After each game, I'll post the logfile in the competition thread.

EDIT: When the size of the board is changed within the Board class, the program expands the grid, but doesn't change the size of the playing window. It's easy to fix, though.

Hey, I haven't looked at the code but I'm just wondering how you plan to test everyones AI. Are they meant to compile it into DLL's for your windows app to open, send it over loopback sockets or are you just going to cut and paste?

They will provide code for me to compile in the program I posted above.
DLLs and other libraries requires knowledge of a particular platform, which makes them less attractive for these uses.

Since the deadline is in a week can everyone who will be turning in working AI please post, I'd hate to be the only one who enters :D

I got an extremely simple one working (slightly better than random), but I don't know if I'll be able to get anything worthy of submitting done by the end of the week. There's still hope, though!

I still think you should submit. The contest will be more fun if there are more participants.

Submit your entries to the email adress I've added in the OP.

Perspective will be participating in this contest. He will try not to speak in the 3rd person for much longer though, as it is quite annoying.

so yeah, ive clocked 7 hours (4 sober) creating a mush of "AI" for this contest in a last minute surge of bordem combined with the rare and radiant free time i came across.

Im gonna mess with my submission a little more before i submit though.

The email address in the OP is a little messed up, at least for me anyways. Is that supposed to read p04pst (at) efd.lth.se ?

Yes, but I messed it up on purpose to avoid spam. :) :)
Please don't post it. :)

> The deadline is November 1st.

well, due to an unaccessible C-Board i didnt submit in time. Is there any extension to compensate for the site's downtime? Im at work right now so the earliest i would be able to submit would be later tonight.

I haven't recieved any submission yet, so the new deadline is Wednesday November 10th.

Quote:

---

Yes, but I messed it up on purpose to avoid spam.
Please don't post it.

---

I know, a couple of hours later it hit me like a brick why you did that, but by then the server went down so I couldn't edit it. Sorry! :o

I just sent you my entry.

submitted last night.

I noticed the current game files dont check for a tie. They just force the player to move if the board is full, which is obviously an illegal move. This should be accounted for.

Also, how are you going to decide who goes first in the tournament?

My guess is you play twice against you opponant each having an opportunity to go first.

Just wanted to point out (I don't know if anyone else has) there should be some bounds checking. Running my code could possibly crash if there isn't.

For example in at():

Code:

---

if (x < 0 || x >= width || y < 0 || y >= height)
  return ' ';

---

and in canMove():

Code:

---

if (x < 0 || x >= width)
  return false;

---

I assume that the files we were supplied with are not the complete versions that will be used for the competition, but you can't be too sure.

Quote:

---

Originally Posted by Perspective

submitted last night.

I noticed the current game files dont check for a tie. They just force the player to move if the board is full, which is obviously an illegal move. This should be accounted for.

Also, how are you going to decide who goes first in the tournament?

---

I've fixed the 'game engine' so it correctly checks for a tie.

I'll make each player play against each other two times, so each one can start once. The board dimensions will be slightly random, but not the number of pieces needed to win.

I've recived submissions from you three, I'll PM the others to check whether they'll submit or not. Either way, the tournament will begin soon.

>>I'll make each player play against each other two times, so each one can start once. The board dimensions will be slightly random, but not the number of pieces needed to win.<<

Ack, I didn't know the dimensions of the board would change, I thought it was going to stay the standard 7x6. A big chunk of my code is hard coded for this size board because getMove() was the only function to be called and I didn't want to recalculate every move. Looks like my entry will have to sit out anything that isn't 7x6.

mine as well is "optimized" to run at 7x6, though syntactially it should handle any size. Havent actually tried yet though :p

>>I'll make each player play against each other two times
so what happens in a 1:1 tie?

>>mine as well is "optimized" to run at 7x6, though syntactially it should handle any size.<<

Heh, not mine. Anything other than 7x6 and its crash and burn baby.

I'm very curious how ya'll approached this here program because I never even had even the slightest thought about taking into account the dimensions of the playing area... Hmm...

OK, the board will be 7x6. But the idea was to use Board::width and Board::height to make the program able to handle different boards. But since neither of you have taken this into account (although Perpective sent me a slightly updated version) I guess the contest will be better if the board stays 7x6.

Quote:

---

so what happens in a 1:1 tie?

---

A win = 2 points
A tie = 1 point each

well, mine is totaly independant of board size. It more or less was in the first place i just changed some stored values to be calculated on the fly based on board dimensions. But a fixed size is cool by me.

>>A win = 2 points
>>A tie = 1 point each
yeah, what i meant was what happens if one game is one by each player ( a score of 2 to 2). If you simply try to play the AI's against each other again your likely to just see the same games repeat themselves (unless one of them use a stochastic algorithm)

If only 3 of us submit i can submit my "FooBot" as well just for the sake of having competitors in the tournament. Its a slightly better than random player that should get destroyed by most of our AI's. Maybe the other players have some test bots as well? Also, im sure Sang-drax has an AI for his game, maybe he can enter that in the tournament if we dont get a better turn out.

Quote:

---

Originally Posted by Perspective

If you simply try to play the AI's against each other again your likely to just see the same games repeat themselves (unless one of them use a stochastic algorithm)

---

That was why I wanted to alter the board size a little between the games.

It will be a tournament and the program with most points at the end will be the winner.

The others aren't finished and it isn't that likely they will submit anything. I will start the first game soon, but I see no problem in adding another contestant later.

These are the preliminary rules:
Each player plays each other one twice and they begin the game once each.
Win = 2 points
Loss = 0 points
Tie = 1 point.

If a player earns any points with an average moving time of more than 1 second, ½ point will be removed for each ½ second above 1 second.

The player with the most points at the end of the tournament wins.

EDIT: http://cboard.cprogramming.com/showt...286#post411286

The following changes had to be made to make your submissions compile:
LuckY
Had to change your for loops so that x is declared in each loop, not just the first, like the standard says.

PJYelton
The getMove function (and all other functions) take Board& instead of const Board&, which is unacceptable.
I had to do this:

Code:

---

int getMove(const Board& cboard, char player)
{
    Board board = cboard;
    //Unchanged from here

---

Oops, I was going to change to const board once I relooked up the original post, but some reason I forgot.

If I have time this weekend I'll try to update my algorithm to account for different size boards. That way we can extend the tourney if we want to.

Quote:

---

Had to change your for loops so that x is declared in each loop, not just the first, like the standard says.

---

I appreciate your smugness and must note that, standard or not standard, what you've described is not compiler independent. I prefer using for loops the way you describe as standard, but Microsoft is intent on stopping me from practicing using my preferred technique. (in any case pardon my lack of standardized code).

Quote:

---

Maybe the other players have some test bots as well?

---

I just had my AI play against itself and sometimes I played against it and other times both.

Quote:

---

I prefer using for loops the way you describe as standard, but Microsoft is intent on stopping me from practicing using my preferred technique.

---

I feel your pain, that drives me nuts with MSVC++ as well meaning I have to declare the variable outside the loop everytime if theres even a chance that it might be compiled with anything else. Grrrrr... :)

Dang, if I had known so few people would have entered, I would have kept my initial AI which had a completely different eval function and way of picking moves. It played all right but it was slow so I unfortunately trashed it when I redid the AI.

Jeremy might still submit; he seemed quite interested, but he hasn't been online since before the dark period.

Quote:

---

I feel your pain, that drives me nuts with MSVC++ as well meaning I have to declare the variable outside the loop everytime if theres even a chance that it might be compiled with anything else. Grrrrr...

---

Code:

---

#define for if( 0 ); else for

---

Code:

---

#define for if( 0 ); else for

---

That's nice. Even simpler:

Code:

---

#define for if (1) for

---

or even simpler than that, Microsoft could actually follow the standard.

Don't make it too simple (yours has unexpected results here):

Code:

---

if (isFalse)
    for (int i = 0; i < 10; ++i)
        cout << i << endl;
else
    for (int i = 0; i < 10; ++i)
        cout << 10 - i << endl;

---

good point.