AI vs AI (VB6)

[Milk]

Would anyone be interested in a little AI vs AI competition?

The idea being a suitable game would be chosen, and a simple dumb interface would written. Then anyone interested in taking part would create an AI for this interface to be pitted against all the other AI's submitted in a mini league.

These AI's must be a little different to a basic AI as each move should be subject to a time limit, in other words the time limit and the code speed will dictate the depth of recursion. It would not be fair if one AI took 3 seconds to move whilst another took 3 minutes. This implies to me that the AI module could contain a function purely to assess it's speed on the competition computer prior to a match. I'm also a little dubious about any use of game tables but if the right game is chosen these tables would be impractically large anyway. For this reason there should also be a size limit to any submitted AI's

I'll start by suggesting Quixo, which is a Tic-Tac-Toe hybrid. Tic-Tac-Toe would be too easy for this as the whole game can be solved (as in every possible move calculated) in under a second. Quixo on the other hand has a much much larger tree, ignoring symmetry it has 44 opening moves.

I would be writing the agreed game interface in VB6 so all submitted AI's must have the ability to be called from VB6 relatively easily.

Anyone interested? Any Ideas?

Nice description of various AI algorithms with code examples (C)

[Milk]

<reserved>

[Ellis Dee]

Possibly.

I don't understand why the 3 secs vs 3 minutes is unfair. I know when I play chess IRL, it always seems like one guy takes way longer to move than the other guy. (I'm often the faster one, but by no means always.)

[Milk]

Well nothing's pinned down yet but, typically most game AI's are recursive and work to a depth. The greater the depth, the more moves assessed, the longer the function takes. Typically a AI function can be set to any depth, so the same function could return in seconds or hours (maybe not quite hours) depending on the depth set. If there was no time limit then the temptation would be to always work to the maximum depth that the stack space will allow.

I would envisage several matches with different time limits, i.e. something like 1, 10, 30, 60, 120, 300 second moves. Maybe some with no time limit, but I would like to avoid games that take too long, as I've only so much time to put into this.

[Ellis Dee]

The real-life solution in chess is to use a chess clock. That may or may not add too much complexity to this problem, though.

[Milk]

I agree that average move time would be fairer. Either way, I don't think It would necessarily add too much complexity. Forgetting about any speed assessment function, If the AI takes too long the match could be simply replayed with the offending AI's depth reduced.

[Ellis Dee]

Just for clarity, a chess clock doesn't measure average time, but rather total time you get for the match. A "peppy" game usually gives each player 5 minutes to use as they see fit. You could do a flurry of moves in a standard opening book using only like 1 second per move. In the midgame you might take 10 seconds to a half minute to make a move, but as you start running out of time you have to speed it up. If you run out of your 5 minutes, you lose.

[Milk]

Wow, thats a fast game!
After some further thought on Quixo, it might not be so suitable for AI vs AI as the games could well never end.
I've some more games to suggest...
Mancala
Quarto
Pyraos

[Ellis Dee]

I vote Mancala, though it may be brute-forceable. (I play it all the time with my niece.)

[Milk]

I like the idea of Mancala too though I confess to having written a rudimentary AI for this already. I like the Kalah variant the best. There are quite a few open source Kalah AI's dotted around to look at. Game tables and some interesting research can be found here, it's worth noting that generally the starting player has an advantage. If we choose this I would suggest creating an AI capable of handling different pit and seed numbers and an optional 'Empty Capture' rule.