2007 Computer Stratego World Championship
From StrategoUSA
The first Computer Stratego World Championship was held December 8-12, 2007. This was a free tournament open to any programmer whose application supported the Stratego AI API and abides by the game rules.
The tournament was hosted by Metaforge (http://www.metaforge.net), an online, multiplayer gaming site. Participants ran their code on their own computer and used a downloadable client to connect to the server. Viewers were able to logon to Metaforge and watch games as they were played, or replay completed games at a later time.
Contents |
[edit] News
- 2007-12-09: Tournament started! See the results!
- 2007-12-01: Final release of Metaforge Bot SDK
- 2007-09-17: "Reveal Your Rank!" registered
- 2007-09-16: "Master of the Flag" registered
- 2007-09-15: "Invincible" registered
- 2007-09-15: "Probe" registered
- 2007-09-15: Site launched
[edit] Objective
We are a small community that loves strategy games and strategy game programming, particularly Stratego. As players, we range from the intermediate level up to the current world champion (Vincent de Boer). As programmers, all of us have experience in artificial intelligence. We share in common a desire to see the emergence of Stratego programs that can play on a par with the best human opponents.
This tournament will be a demonstration of the current state-of-the-art in Stratego AI programming. It will show both how far we've come in recent years and how much further we still have to go. Stratego, a game of incomplete information, presents a substantial challenge to the artificial intelligence community. It requires the ability to draw intelligent inferences, see far ahead in games, adapt to a wide variety of playing styles and remain unpredictable. Unlike chess, Stratego programming remains a wide open field.
[edit] Committee members
These are the members of the tournament committee:
Vincent de Boer
World Champion "live" Stratego &
Author of Invincible
vdeboer_nl@yahoo.com
Imer Satz
Author of Probe
imer@imersatz.com
Chip McVey
Founder of Metaforge
chip@metaforge.net
[edit] Tournament rules
The tournament will consist of five sessions, one session per day. During a session, each program will play each other program once.
Scoring will be as follows:
| Win | 6 |
| Draw | 3 |
| Loss | 1 |
| Forfeit | 0 |
A forfeit will result from a program crash, illegal move, illegal setup or other condition that terminates the game abnormally.
This is the official Stratego tournament scoring, which is equivalent to (W-D-L) 5 - 2 - 0 with 1 point for playing, or 1 - 0.4 - 0 with 0.2 points for playing. This gives a small drawing penalty (draw is valued less than half a win) which should promote aggressive play.
If, at the end of the tournament, two programs have equal scores, their point totals from the final session will be used as a tie breaker, followed by the previous session and so forth. This will reward improvements programmers have made during the tournament by placing greater value on the later sessions.
[edit] Game rules
The games will be played according to the standard Stratego rules, with range attacks enabled (scouts can attack during a range move).
[edit] Time limit
There will be a time limit of 15 seconds per move.
[edit] Move limit
At 2,000 moves, a game will be declared a draw.
[edit] Two-Squares rule
Literally from the ISF rules http://www.isfstratego.com/images/isfgamerules.pdf
10.1 It is not allowed to move a piece more than 5 times non-stop
between the same two squares, regardless of what the opponent
is doing. It does not matter whether a piece is moving and
thereby attacking an opponent’s piece, or just moving to an
empty square.
In pseudocode this would be:
method breaksTwoSquareRule(move)
limit := 5
for(count := 1 ; count <= limit ; count++)
prevmove := getMove(current-2*count)
if( !equal(move,prevmove) && !reverse(move,prevmove) )
return false
return true
method equal(move1,move2)
if(move.toField==move2.toField && move.fromField==move2.fromField) return true
else return false
method reverse(move1,move2)
if(move.fromField==move2.toField && move.toField == move2.fromField) return true
else return false
This rule must be implemented to participate in the tournament. Also, it is important to specify the limit as exactly five moves: with a higher limit your program may attempt to make illegal moves, while with a lower limit your program may play at a disadvantage.
Note this is a simplification of the ISF rules as they apply to scouts. Article 10.2 states that for scout moves, each square that is passed by the scout counts as the begin or the end square of that move. We are not enforcing this rule for the tournament.
[edit] More-Squares rule
Literally from the ISF Rules http://www.isfstratego.com/images/isfgamerules.pdf
11.1
It is not allowed to continuously chase one or more pieces of the
opponent endlessly. The continuous chaser may not play a
chasing move again more which would lead to a position on the
board which has already taken place.
11.2
Exception: chasing moves back to the square where the chasing
piece came from in the directly preceding turn are always
allowed as long as this does not violate the Two-Squares Rule
(Five-Moves-on-Two-Squares).
11.3 Definitions:
- continuous chase: the same player is non-stop threatening one or more pieces of his opponent that is/are evading the threatening moves.
- chasing move: a move in a continuous chase that threatens an opponent’s piece that was evading during the continuous chase.
Hereby:
- a/to move: a/to move plus attacking or a/to move to an empty square.
- to threaten: to move a piece next (before, behind or besides) a piece of the opponent.
- to evade: to move a piece away promptly after it has been threatened.
Pseudocode for the official More-Squares Rule:
forbiddenPositions := new List //this list contains all board positions that you are not allowed to create again
method isAttackingMove(move)
if (move involves combat) return true
else return false
method breaksMoreSquareRule(move)
// if combat, then there is obviously not a chase
if(isAttackingMove(move)) return false
// if we're moving opposite of last move, that is the
// domain of the two square rule
if(reverse(move,myLastMove)) return breaksTwoSquareRule(move)
// perform the move - update board state based on move - to allow testing validity
board := performMove(board, move)
// if the board state is in the forbidden list, then it's not valid
if(forbiddenPositions contains board.hash()) valid := false
else valid := true
// unperform the test move we just made
board := unperformMove(board, move)
return !valid
method doMyMove(move)
// if it doesn't break the rule
if (!breaksMoreSquareRule(move)) {
...code for executing move...
// add all board positions after your own moves to the forbidden list
forbiddenPositions.add(board.hash())
// record my last move
myLastMove := move
}
method doOpponentMove(move)
// if opponent is not running away from us...
if(!nextTo(myLastMove.endField,move.startField)
// empty forbidden list when opponent doesn't move from a field
// next to where our last move ended
forbiddenPositions := new List
...code for executing move...
The More-Squares rule will not enforced for the 2007 tournament, but participants are encouraged to implement rules that discourage their bots from chasing.
[edit] Stratego AI API
The Stratego AI API enables Stratego programs to play on Metaforge, using the downloadable Metaforge client. The API supports both Java and native programs. The Stratego AI API is available for free download here:
Version 2.0.36: http://www.metaforge.net/olg/webstratego/ai/MetaforgeBotSDK.zip
Note the complete API supports features beyond the scope of this tournament. For the purposes of the tournament, a program need only be able to play classic Stratego with range attacks enabled, from either side of the board.
These are the methods a program must implement for tournament play:
setGameOption()
set the passed game option
createAISetup()
create or select a setup for the AI
getAISetupPiece()
return the AI setup, piece-by-piece
illegalSetup()
the AI setup is illegal
setOpponentSetupPiece()
mark squares that have an opponent piece
getAIMove()
generate a move and pass it back
submitAIMoveResult()
learn the result of the AI move (for attacks)
submitOpponentMove()
learn the opponent move
For more information about the Stratego AI API, please contact one of the committee members.
[edit] Tournament roster
Here are the programs currently signed up to play in the tournament (in alphabetical order):
[edit] Invincible
 Invincible | |
| Programmer | Vincent de Boer |
| Nationality | Dutch |
| Year Created | 2007 |
| Last Update | 2007 |
| Company/Affiliation | TU Delft |
| Link | - |
"Invincible" is my graduation project from Delft University. It's meant to radically improve the level of Stratego artificial intelligence, or at least to have the potential to do so ;). Considering the solving of Stratego by means of exhaustive search futile, Invincible never performs more than a single move in advance which makes it relatively fast. This tournament will be its first public appearance, it cannot be downloaded or played online.
[edit] Master of the Flag
 Master of the Flag | |
| Programmer | Sven Jug |
| Nationality | German/American |
| Year Created | 2004 |
| Last Update | 2007 |
| Company/Affiliation | Jayoogee |
| Link | http://www.jayoogee.com/masteroftheflag/ |
Master of the Flag started out as a prototyping project for new software technologies. It quickly turned into something bigger when I realized that writing a decent AI would be very challenging. At one point during the development I froze the initial design and moved on the the second generation of AI, which was a fundamentally different algorithm design than the first one.
Master of the Flag is participating in the tournament with it's latest AIs from the first and the second generations.
[edit] Probe
 Probe | |
| Programmer | Imer Satz |
| Nationality | American |
| Year Created | 1983 |
| Last Update | 2007 |
| Company/Affiliation | Imersatz GmbH |
| Link | http://www.probe.imersatz.com/ |
Probe is no doubt the oldest Stratego program entered in this tournament, and may well be the first Stratego program of all. I originally wrote it as an undergraduate in college, the first program I'd completed that was longer than about 50 lines. It played reasonably well (beat my prof!), but PCs were just coming onto the market at the time and were much too slow to play Probe. So I put it aside.
I picked up Probe two years ago and discovered I could do more with the current generation of fast PCs. So I wrote a standalone program that plays Classic Stratego, a new Enhanced mode of my invention for more dynamic play and a custom mode for variants such as Barrage. I released Probe as freeware last year.
Probe performs a fixed depth search with alpha-beta tree pruning. Tree searches are problemmatic for Stratego. On the one hand, they discover attack combinations, reveal Flag threats and produce other useful results. But on the other hand, they introduce error insofar as it is necessary to make guesses about the opponent's pieces. Games such as chess do not have this problem, since the AI can simply flip the board around during recursion and play with complete information from each side. With Stratego, the deeper you search the more likely you are to make incorrect assumptions about your opponent's best move, so it is not apparent that deep searches contribute to better move selection. At the Tournament skill level, Probe searches to seven plies.
Obviously, seven plies is an insufficient lookahead for Stratego. In Stratego, pieces may have targets that are 10-15 moves distant, which would amount to 20-30 plies in a search tree, far beyond the reasonable limits of search. Therefore, it is necessary to have another means for pieces to discover targets. Probe employs its own iterative pathfinding algorithm that discovers clear routes for pieces to any square on the board. Targets include weaker mobile pieces, Bombs (for Miners), likely Flag locations and squares that intercept pieces threatening Probe's Flag.
Probe manages uncertainty in a number of ways. For one, it maintains probability tables that relate to Flag placement and other variables. It keeps track of attack opportunities passed over as an indicator of unlikely ranks for unknown opponent pieces. Probe also makes specific guesses about the identities of certain opponent pieces. A guess might be the result of a piece moving aggressively, ignoring a piece that moves aggressively against it, approaching the Flag and so forth. Guessing simplifies the search tree, since each piece is assumed to have a unique rank, but it creates problems for circumstances where it might be best to protect against a piece being one of several possible ranks.
[edit] Reveal Your Rank!
 Reveal Your Rank! | |
| Programmer | Raimonds Rudmanis |
| Nationality | Latvian |
| Year Created | 2001 |
| Last Update | 2006 |
| Company/Affiliation | None |
| Link | http://www.yellowgames.com/ |
Reveal Your Rank! is old game. It appeared first for PocketPC platform around 2001. Because it is designed to run also on devices with limited resources like PocketPC and mobile phones, the AI is very compact and fast.
[edit] RandomBot
| RandomBot | |
| Programmer | Vincent de Boer |
| Nationality | Dutch |
| Year Created | 2007 |
| Last Update | Nov 2007 |
| Company/Affiliation | None |
| Link | None |
The RandomBot is precisely what it's name implies. During its turn, it enumerates all possible legal moves and then randomly selects one of them. While this obviously is not a sign of intelligence, it will serve a useful purpose in the tournament by encouraging the other entrants to be aggressive. An overly defensive entrant may not sufficiently try to capture the flag and may therefore draw against the RandomBot, whereas programs that are more adept at flag capture should benefit by getting win points against RandomBot.
[edit] Schedule
The tournament will be played on 5 days, on each day each participant will play each other participant once.
Times are given in GMT.
[edit] Day 1: Saturday 8th of december
Round 1: 19:00 gmt
- Reveal Your Rank! vs. Master of the Flag I 1-6
- Probe vs. Invincible 6-1
- Master of the Flag II vs. RandomBot 6-1
Round 2: 20:00 gmt
- Invincible vs. Reveal Your Rank! 6-1
- Master of the Flag II vs. Probe 1-6
- RandomBot vs. Master of the Flag I 1-6
Round 3: 21:00 gmt
- Reveal Your Rank! vs. RandomBot 6-1
- Probe vs. Master of the Flag I 6-1
- Invincible vs. Master of the Flag II 6-1
Round 4: 22:00 gmt
- Master of the Flag II vs. Reveal Your Rank! 6-1
- RandomBot vs. Probe 1-6
- Master of the Flag I vs. Invincible 1-6
Round 5: 23:00 gmt
- Reveal Your Rank! vs. Probe 1-6
- Master of the Flag I vs. Master of the Flag II 1-6
- Invincible vs. RandomBot 6-1
[edit] Day 2: Sunday 9th of december
Round 1: 19:00 gmt
- Reveal Your Rank! vs. Master of the Flag II
- Probe vs. RandomBot 6-1
- Invincible vs. Master of the Flag I 6-1
Round 2: 20:00 gmt
- Probe vs. Reveal Your Rank! 6-1
- Master of the Flag II vs. Master of the Flag I 6-1
- RandomBot vs. Invincible 1-6
Round 3: 21:00 gmt
- Master of the Flag I vs. Reveal Your Rank! 6-1
- Invincible vs. Probe 1-6
- RandomBot vs. Master of the Flag II 1-6
Round 4: 22:00 gmt
- Reveal Your Rank! vs. Invincible 1-6
- Probe vs. Master of the Flag II 6-1
- Master of the Flag I vs. RandomBot 6-1
Round 5: 23:00 gmt
- RandomBot vs. Reveal Your Rank! 1-6
- Master of the Flag I vs. Probe 1-6
- Master of the Flag II vs. Invincible 3-3
[edit] Day 3: monday 10th of december
Round 1: 19:00 gmt
- Reveal Your Rank vs. Probe
- Master of the Flag I vs. Master of the Flag II
- Invincible vs. RandomBot
Round 2: 20:00 gmt
- Reveal Your Rank! vs. Master of the Flag I
- Probe vs. Invincible
- Master of the Flag II vs. RandomBot
Round 3: 21:00 gmt
- Master of the Flag II vs. Reveal Your Rank!
- RandomBot vs. Probe
- Master of the Flag I vs. Invincible
Round 4: 22:00 gmt
- Reveal Your Rank! vs. RandomBot
- Probe vs. Master of the Flag I
- Invincible vs. Master of the Flag II
Round 5: 23:00 gmt
- Invincible vs. Reveal Your Rank!
- Master of the Flag II vs. Probe
- RandomBot vs. Master of the Flag I
[edit] Day 4: Tuesday 11th of december
Round 1: 19:00 gmt
- RandomBot vs. Reveal Your Rank!
- Master of the Flag I vs. Probe
- Master of the Flag II vs. Invincible
Round 2: 20:00 gmt
- Reveal Your Rank! vs. Master of the Flag
- Probe vs. RandomBot
- Invincible vs. Master of the Flag
Round 3: 21:00 gmt
- Reveal Your Rank! vs. Invincible
- Probe vs. Master of the Flag II
- Master of the Flag I vs. RandomBot
Round 4: 22:00 gmt
- Probe vs. Reveal Your Rank!
- Master of the Flag II vs. Master of the Flag I
- RandomBot vs. Invincible
Round 5: 23:00 gmt
- Master of the Flag I vs. Reveal Your Rank!
- Invincible vs. Probe
- RandomBot vs. Master of the Flag II
[edit] Day 5: Wednessday 12th of december
Round 1: 19:00 gmt
- Invincible vs. Reveal Your Rank!
- Master of the Flag II vs. Probe
- RandomBot vs. Master of the Flag I
Round 2: 20:00 gmt
- Reveal Your Rank! vs. RandomBot
- Probe vs. Master of the Flag I
- Invincible vs. Master of the Flag II
Round 3: 21:00 gmt
- Reveal Your Rank! vs. Probe
- Master of the Flag I vs. Master of the Flag II
- Invincible vs. RandomBot
Round 4: 22:00 gmt
- Reveal Your Rank! vs. Master of the Flag I
- Probe vs. Invincible
- Master of the Flag II vs. RandomBot
Round 5: 23:00 gmt
- Master of the Flag II vs. Reveal Your Rank!
- RandomBot vs. Probe
- Master of the Flag I vs. Invincible
To convert to your local time zone, look here: http://time.securesites.com/
[edit] Results
[edit] Standings
| Pos | Name | Nation | Score | W (6) | D (3) | L (1) |
| 1. | Probe  | |
141 | 22 | 3 | 0 |
| 2. | Invincible   | |
115 | 16 | 5 | 4 |
| 3. | Master of the Flag II | |
103 | 14 | 4 | 7 |
| 4. | Master of the Flag I | |
70 | 9 | 0 | 16 |
| 5. | Reveal Your Rank! | |
65 | 8 | 0 | 17 |
| 6. | RandomBot | |
25 | 0 | 0 | 25 |
[edit] Cross table Day 1
| Name | Nation | Score | Inv | MF1 | MF2 | Pro | Ran | RYR |
| Invincible | | 25 | x | 6 | 6 | 1 | 6 | 6 |
| Master of the Flag I | | 15 | 1 | x | 1 | 1 | 6 | 6 |
| Master of the Flag II | | 20 | 1 | 6 | x | 1 | 6 | 6 |
| Probe | | 30 | 6 | 6 | 6 | x | 6 | 6 |
| RandomBot | | 5 | 1 | 1 | 1 | 1 | x | 1 |
| Reveal Your Rank! | | 10 | 1 | 1 | 1 | 1 | 6 | x |
[edit] Cross table Day 2
| Name | Nation | Score | Pro | Inv | MF2 | MF1 | RYR | Ran |
| Probe | | 30 | x | 6 | 6 | 6 | 6 | 6 |
| Invincible | | 22 | 1 | x | 3 | 6 | 6 | 6 |
| Master of the Flag II | | 22 | 1 | 3 | x | 6 | 6 | 6 |
| Master of the Flag I | | 15 | 1 | 1 | 1 | x | 6 | 6 |
| Reveal Your Rank! | | 10 | 1 | 1 | 1 | 1 | x | 6 |
| RandomBot | | 5 | 1 | 1 | 1 | 1 | 1 | x |
[edit] Cross table Day 3
| Name | Nation | Score | Pro | Invi | MF2 | MF1 | RYR | Ran |
| Probe | | 27 | x | 3 | 6 | 6 | 6 | 6 |
| Invincible | | 19 | 3 | x | 3 | 1 | 6 | 6 |
| Master of the Flag II | | 17 | 1 | 3 | x | 6 | 1 | 6 |
| Master of the Flag I | | 15 | 1 | 6 | 1 | x | 1 | 6 |
| Reveal Your Rank! | | 20 | 1 | 1 | 6 | 6 | x | 6 |
| RandomBot | | 5 | 1 | 1 | 1 | 1 | 1 | x |
[edit] Cross table Day 4
| Name | Nation | Score | Pro | Inv | MF2 | MF1 | RYR | Ran |
| Probe | | 27 | x | 3 | 6 | 6 | 6 | 6 |
| Invincible | | 27 | 3 | x | 6 | 6 | 6 | 6 |
| Master of the Flag II | | 20 | 1 | 1 | x | 6 | 6 | 6 |
| Master of the Flag I | | 10 | 1 | 1 | 1 | x | 1 | 6 |
| Reveal Your Rank! | | 15 | 1 | 1 | 1 | 6 | x | 6 |
| RandomBot | | 5 | 1 | 1 | 1 | 1 | 1 | x |
[edit] Cross table Day 5
| Name | Nation | Score | Pro | Invi | MF2 | RYR | MF1 | Ran |
| Probe | | 27 | x | 6 | 3 | 6 | 6 | 6 |
| Invincible | | 22 | 1 | x | 3 | 6 | 6 | 6 |
| Master of the Flag II | | 24 | 3 | 3 | x | 6 | 6 | 6 |
| Reveal Your Rank! | | 10 | 1 | 1 | 1 | x | 1 | 6 |
| Master of the Flag I | | 15 | 1 | 1 | 1 | 6 | x | 6 |
| RandomBot | | 5 | 1 | 1 | 1 | 1 | 1 | x |
[edit] Programmer reports
This section will be used by the programmers to document their experiences during and after the tournament.
[edit] Vincent de Boer (Invincible)
Day 1
The first day has been completed without bugs or crashes from any of the programs! Invincible got of a bad start, losing its opening match against Probe. Probe attacked very aggressively and Invincible was at a loss for an answer. The flag was on the side where Probe attacked and Probe excellently captured it, ending the game in a little over 300 moves. Earlier, Invincible tried to bluff Probe, but since Probe called the bluff this cost Invincible a colonel, it was probably not a very good bluff to try ;)
Invincible won the next four games though and ended on the second place after the first day. Master of the Flag II was slow, but played impressive matches against Probe and Invincible, only narrowly losing them. A lot of the games were pretty even and with still 4 days to go this might become a very exciting tournament.
I've edited some numbers in the setup generator to let him create setups more suitable for bot vs bot games and changed something in the capturing logic, because Invincible sometimes refused to reveal the rank of one of its pieces even for a piece just one rank lower. There were also some cases where Invincible would run a very high piece on a bomb either shortly after he got an important lead or close before winning the game. I haven't yet found why he does that, but since it's always in situations that he can't lose I'll have to consider it celebration fireworks for now...
Day 2
The second day was a difficult one for Invincible. He got trashed by Probe, which seemed to become an interesting game when Invincible went into a counter-attack in the endgame. A draw would have been possible if the last miner was captured, but unfortunately Invincible let it slip away and then made a fool of himself by letting his last high piece be traded.
I made a small bug-fix after the game against RandomBot because it appeared a piece changed rank in that game, but the result of this "bugfix" was that none of Invincible's pieces ever became known (at least that's what he thought). He kept trying to hide the rank of pieces that were already known and bluffed with pieces that could not be a high rank any more. This explains the most stupid moves Invincible made against Probe. Unfortunately I didn't find this during the tournament. Reveal Your Rank! could easily have beaten me, but Invincible made a last attempt on one of two possible flags with his last miner and found the right one.
The last game against Master of the Flag II was one of a type I feared before the start of the tournament: neither player was willing to attack for a long time. In the end something did happen and the game was totally won for Master of the Flag, but he failed to move any of its four miners down to the flag. The game then became a draw on 2000 moves, a result I should consider myself happy with but which puts Probe at a very big lead in this tournament.
Day 3
I spent all day fixing bugs and testing, by the amount of bugs I found a rough estimate is that there are still several thousand left... but some are fixed ;) The reward was an opening round loss against Master of the Flag 1, no not 2, it's weaker ancestor 1... MF1 got a lucky start and was later virtually forced by Invincible to capture an unmoved colonel.
After a rather dull (result-wise) second day, today we saw how close the competitors really are in level, Reveal Your Rank took revenge for its beating in the first two round by beating two higher ranked programs and seems to be getting silver on day 3. As much as it hurts losing a game to an outsider I can only admit it adds to the excitement of this tournament to know that no win is certain. Maybe even Probe... nah ;)
On a positive note, Invincible finally managed to steal points from Probe. One of the last things I added (10 minutes before the first round started) was code to get a draw when down to a single scout when the opponent has more pieces but no miners. This happened when Probe (who had gotten shamelessly lucky of course) had 6 higher pieces but failed to capture Invincibles last scout so Invincible was able to steal a draw. This was not enough though, as Probe has now taken a huge lead and it doesn't seem likely anyone can catch up in two more days. MF2 and Invincible seem doomed to fight it out for the second place.
Funny thing to mention is that this round we got a record game when Master of the Flag II beat RandomBot in a single move. This is probably gonna stay a tournament record :)
Day 4
A great day for Invincible! Maybe my bug-fixes didn't make the program worse after all. 4 wins and a second draw to Probe give Invincible a shared first place on day 4! This time the draw against Probe was actually a pretty even endgame, where Invincible had most chances to win but that was a long shot and apparently too difficult for Invincible.
On this day we also played some games of the last round, including the last Invi-Probe game. It really looked like Invi might pull this one off, but being up 2 colonels he stupidly let Probe's last miner get to the flag, right past a sergeant. Invincible should have known better so there's probably one of the remaining bugs to blame :( It was a great game though, where Probe's initial agression for a change did not give him a huge lead before Invincible gathered himself together for the counter-attack. This resulted in a great game, where Invincible seemed to have the upper hand till he slipped in defense. Probe was a great opponent though and a deserving winner of this tournament. Maybe next time ;)
Epilogue
Looking back, this was a great tournament in which most of the best Stratego programs fought each other for the first time that should definitely be repeated next year. We had some trouble with bots chasing the other player infinitely and thus preventing the opponent from making constructive moves, but we all agree that this should be a point of attention for improvements. Probe and Invincible show that it's possible to solve this problem as neither did excessive pointless chasing.
All bots had their own personality, weak and strong sides and each could, if not beat, give each other participant a hard time.
Reveal Your Rank! was very aggressive and focusing on the flag, but too careless about protecting known pieces. He nearly always lost some high pieces quickly, but still managed to beat the MotF bots which sometimes tended to ignore flag defense. I think it could have performed a lot better if it sometimes feared unknown pieces ;)
Master of the Flag I was the second extremely aggressive program, it must have had a bug though as it frequently gave away pieces for free which somewhat limited its winning chances. Still, it was very dangerous, especially for Invincible which kinda expects the opponent to be scared of bluffs and unmoved pieces.
Master of the Flag II was the newer version of Master of the Flag but almost completely opposite in playing style. It was extremely carefull and made few obvious mistakes, though it tended either to ignore flag defense or exaggerate it by moving all his highest pieces very close to the flag. Unfortunately it was very slow (15 seconds per move) and sometimes engaged in endless chasing. It played lots of very close games against Invincible and Probe though and could easily have had more points.
Invincible, my own creation, performed rather unstable... part of this was because of bugs, fixed bugs and newly introduced bugs as I believe I'm the only one who made significant changes during the tournament. I chose to do this because as the "newest" participant I probably had the least testing and the most easily fixable bugs. Invincible was a rather passive program, being easily pushed in defense by the stronger programs, but once it got enough information it could make great comebacks even against Probe. It was the only program who regulary bluffed, though the opponents not always bought that, which then cost Invi a piece. Without building a search tree, Invincible was a lot faster than Probe and Master of the Flag II but did not seem to be more clumsy in tactical maneuvers.
Probe seemed to have found the right balance between attack and defense and between taking risks and playing safe. He did take risks, but not stupid ones and they usually turned out painful for the opponent. Probe also paid much attention to defending the flag, which is probably an important reason why he stayed undefeated the whole tournament. It also actively searched for the flag, which was hard to defend against if Probe attacked on the right side. Probe had its weaknesses too, but none so big that the other participants could consistently exploit them, which makes Probe a deserving winner of this championship!
[edit] Sven Jug (Master of the Flag)
Day 1
The last 18 hours before the tournament were rough. My main computer kept crashing due to a hardware failure, so I only got 2 hours of sleep and had to borrow and prepare another computer 3 hours before the tournament started. Nevertheless, I made it on time and both AIs participated in the tournament.
Master of the Flag II stayed more in a defense position for some of the games, which was unexpected, but it's too early to tell if it is really a problem.
Master of the Flag I tended to get into semi-chase situations, but fortunately the multi-square rule prevented the games to stall.
Day 1
I was able to get my hardware replaced in time for the second tournament day. Master of the Flag II played stronger today, which can be explained with the faster hardware. Unfortunately it gave away a few strong positions in game end situations.
[edit] Imer Satz (Probe)
Day 1
I am really impressed with how well all the bots have been playing! Stratego represents a very difficult programming challenge, and yet every game has been competitive. The results are basically irrelevant: it doesn't matter whether this or that AI has a particular flaw that can be corrected at a later date. What's important is that each AI understands how to play Stratego, and makes it difficult for an opponent to beat it. That is quite an accomplishment. After only one day, I consider the tournament to be a success.
The first day also shows that Chip's SDK works beautifully. From now on, it will be easy for any aspiring game author to write a Stratego AI, present it on Metaforge and test it out. This is news we need to get out to the academic community, in particular, so students will be encouraged to investigate new algorithms for Stratego AI.
Day 2
Vincent mentioned that Probe managed to beat InvinciBot on Day 1 by refusing a bluff. Funny thing is, every time I replayed that position later, Probe took the bluff! Dunno why it didn't during the game, but I ain't complaining.
We're running into a lot of chase sequences we'll need to handle for future tournaments. When a bot plays a human, the human will always get the game out of any stuck positions. But two bots will cycle back and forth forever. We've already got some ideas how to correct this, and after the tournament is over we're going to come up with something to try out next time.
Probe has played a number of extremely close games, yet so far has managed to win them all. The difference seems to be mostly in endgame tactics, where Probe has an edge in its ability to protect its own Flag and attack its opponent's at the same time. We're all going to learn from watching these games, and I expect this will be an area where authors will want to make changes.
Some of the AIs select from databases of setups created by humans; Probe, for instance, does this. At least one AI generates its setups algorithmically. It would be an interesting topic for future tournaments to ask whether an AI should be required to generate setups, so that all of its gameplay would be the product of the AI. Probe actually knows how to generate setups, it's just not using that feature for the tournament.
Day 3
Probe's winning streak finally came to an end with a draw against InvinciBot. To his credit, Vincent had code that taught InvinciBot's last remaining piece, a Scout, how to avoid capture, whereas Probe has no logic to trap a Scout under these conditions. Until now, I haven't paid much attention to endgame special cases because they are rare against humans, who are more likely to terminate the game and start another one. But I see now that close endgames in bot tournaments deserve the same attention as close endgames in tournaments between humans.
Day 4
Probe managed to finish the tournament undefeated, but it had a number of close scrapes, mainly against InvinciBot and MF2. There doesn't seem to be a great deal of difference among the top AIs until you get to the endgame, and there the gap between Probe and the others seems rather large. I think Probe has two advantages at the end: (1) it does a good job of creating a perimeter defense to keep out Miners and suspected Miners; and (2) it aggressively hunts the opponent's Flag. This aggression might backfire against an opponent that played strong defense, but at present MF2 and InvinciBot are too cautious about attacking unknown pieces, and so tend to let Miners in for attacks on the Bombs and Flag. But this is an easy change to make, and next time will create very close games indeed.
With Stratego AI, the first question one asks is, How good can they get? Since Stratego is a game of incomplete information, style and learning come into play. Probe is optimized to play as well as it can against the style of human opponents it has a chance to beat, and has crude learning capability that could be expanded somewhat. But I remain of the opinion that an AI able to play on a par with the best human opponents would require a different solution than exists today among the AIs represented in the tournament. I have no idea what that algorithm might look like, but I hope there are artificial intelligence students out there ready to make their try at next year's tournament!
[edit] Raimonds Rudmanis (Reveal Your Rank!)
Day 1
Many games were pretty even, but I still lost. Disappointed.
Day 2
The same story... RYR generates its setups algorithmically. For Day 2 I chosen a little bit different setup, but unfortunately it didn't help.
Day 3
Finally Reveal Your Rank somehow managed to win both MF1 and MF2 despite the fact that in both games opponent gained an advantage pretty early. It means that RYR knows how to take the flag. AI still has many bugs.
Day 4
Today I noticed too many stupid moves, especially by Miners. Today I again won against MF1 in a very similar way like yesterday - MF1 was ahead, but didn't manage to protect its Flag. Probe is no doubts the best.
