AI contest: Connect four

[Sang-drax]

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:

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:

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.

[Jeremy G]

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

[PJYelton]

Count me in!

[PJYelton]

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:

    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.

[Prelude]

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

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

const int A::a = 10;

This is the older syntax that all compilers accept.

[PJYelton]

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

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

[Prelude]

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

[MrWizard]

I'd be down for this.

[Sang-drax]

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.

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!

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

[Perspective]

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.

[Jeremy G]

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.

[LuckY]

Sounds like fun. Count me in.

[jlou]

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

[Sang-drax]

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