2009 Computer Stratego World Championship

From StrategoUSA

Revision as of 18:19, 25 June 2010 by Imer Satz (Talk | contribs)

(diff) ←Older revision | Current revision (diff) | Newer revision→ (diff)

The 2009 Computer Stratego World Championship will be held during the week of November 23. This will be a free tournament open to any programmer whose application supports the Stratego AI API and abides by the game rules.

The tournament will be hosted by Metaforge (http://www.metaforge.net), an online, multiplayer gaming site. Bots will play each other by means of the Metaforge client, exactly as do humans. This year, all the bots will run on a single computer in a continuous sequence of matches until the tournament is complete. Viewers will be able to logon to Metaforge and watch games as they are played, or replay completed games at a later time.

[edit] Objective

The goal of the tournament is to encourage development of increasingly superior Stratego artificial intelligence implementations. The game is rich for research into game play and decision making with limited information, and we hope that gathering the best implementations available will foster collaboration and increase quality. The tournament also seeks to promote the popularity of the game in general.

[edit] Committee Members

These are the members of the tournament committee:

Vincent de Boer
2007 World Champion "human" Stratego & Author of Invincible
vdeboer_nl@yahoo.com

Imer Satz
Author of Probe
imer@imersatz.com

Chip McVey
Founder of Metaforge
chip@metaforge.net

Sven Jug
Author of Master of the Flag
sven_jug@yahoo.com

[edit] Tournament Rules

The tournament will consist of five games between each pair of participating programs. 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.

Each game will be played according to the Game Rules.

[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

The maximum time limit per move is 15 seconds. The average time per move should not exceed 5 seconds.

[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. However, Article 10.2 of the ISF rules, which pertains to scout moves, will not be enforced.

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

This rule must be implemented to participate in the tournament.

[edit] Tournament Roster

[edit] Probe

Defending 2007 & 2008 Computer Stratego World Champion

Probe
Programmer	Imer Satz
Nationality	American
Year Created	1983
Last Update	2009
Company/Affiliation	Imersatz GmbH
Link	http://www.probe.imersatz.com/

[edit] Master of the Flag 1

Master of the Flag
Programmer	Sven Jug
Nationality	German/American
Year Created	2004
Last Update	2008
Company/Affiliation	Jayoogee.com
Link	http://www.jayoogee.com/

[edit] Master of the Flag 2

Master of the Flag
Programmer	Sven Jug
Nationality	German/American
Year Created	2004
Last Update	2009
Company/Affiliation	Jayoogee.com
Link	http://www.jayoogee.com/

[edit] Invincible

Invincible
Programmer	Vincent de Boer
Nationality	Dutch
Year Created	2007
Last Update	2007
Company/Affiliation	TU Delft
Link	http://www.kbs.twi.tudelft.nl/Publications/MSc/2008-deBoer-Msc.html

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

[edit] Hobbes

Hobbes
Programmer	Maarten Schadd
Nationality	Dutch
Year Created	2008
Last Update	2009
Company/Affiliation	Maastricht University
Link	http://www.personeel.unimaas.nl/maarten-schadd/Homepage/index.html

[edit] Hayati

Hayati
Programmer	Omer Weissbrod & Ziv Cohen
Nationality	Israeli
Year Created	2009
Last Update	2009
Company/Affiliation	None
Link	None

[edit] Zixerqath

Zixerqath
Programmer	Matt Stowe
Nationality	American
Year Created	2008
Last Update	2009
Company/Affiliation	None
Link	http://mattstowe.webs.com/

[edit] Schedule

Round	Match	Creator	Wins	Joiner	Wins	Draws
1	1	Hayati	1	Zixerqath	4	0
1	2	Hobbes	1	Reveal Your Rank!	4	0
1	3	Invincible	2	Probe	3	0
1	4	Master of the Flag 1	0	Master of the Flag 2	5	0
2	1	Reveal Your Rank!	5	Hayati	0	0
2	2	Zixerqath	0	Probe	5	0
2	3	Hobbes	0	Master of the Flag 2	5	0
2	4	Invincible	5	Master of the Flag 1	0	0
3	1	Hayati	1	Probe	4	0
3	2	Reveal Your Rank!	0	Master of the Flag 2	5	0
3	3	Zixerqath	1	Master of the Flag 1	4	0
3	4	Hobbes	0	Invincible	5	0
4	1	Master of the Flag 2	5	Hayati	0	0
4	2	Probe	5	Master of the Flag 1	0	0
4	3	Reveal Your Rank!	1	Invincible	4	0
4	4	Zixerqath	2	Hobbes	3	0
5	1	Hayati	0	Master of the Flag 1	2	3
5	2	Master of the Flag 2	3	Invincible	2	0
5	3	Probe	5	Hobbes	0	0
5	4	Reveal Your Rank!	2	Zixerqath	3	0
6	1	Invincible	5	Hayati	0	0
6	2	Master of the Flag 1	3	Hobbes	1	1
6	3	Master of the Flag 2	5	Zixerqath	0	0
6	4	Probe	4	Reveal Your Rank!	1	0
7	1	Hayati	1	Hobbes	4	0
7	2	Invincible	5	Zixerqath	0	0
7	3	Master of the Flag 1	3	Reveal Your Rank!	2	0
7	4	Master of the Flag 2	2	Probe	0	3

[edit] Game Results

[edit] Match Cross Table

Match results are shown as W-D-L in alphabetical order.

AI Program	W	D	L	Hayati	Hobbes	Invincible	MasterFlag1	MasterFlag2	Probe	RevealYourRank	Zixerqath
Hayati	3	3	29	x	1-0-4	0-0-5	0-3-2	0-0-5	1-0-4	0-0-5	1-0-4
Hobbes	9	1	25	4-0-1	x	0-0-5	1-1-3	0-0-5	0-0-5	1-0-4	3-0-2
Invincible	28	0	7	5-0-0	5-0-0	x	5-0-0	2-0-3	2-0-3	4-0-1	5-0-0
MasterFlag1	12	4	19	2-3-0	3-1-1	0-0-5	x	0-0-5	0-0-5	3-0-2	4-0-1
MasterFlag2	30	3	2	5-0-0	5-0-0	3-0-2	5-0-0	x	2-3-0	5-0-0	5-0-0
Probe	26	3	6	4-0-1	5-0-0	3-0-2	5-0-0	0-3-2	x	4-0-1	5-0-0
RevealYourRank	15	0	20	5-0-0	4-0-1	1-0-4	2-0-3	0-0-5	1-0-4	x	2-0-3
Zixerqath	10	0	25	4-0-1	2-0-3	0-0-5	1-0-4	0-0-5	0-0-5	3-0-2	x

[edit] Score Summary

AI Program	Games Played	Total Score	Ranking
MasterFlag2	35	191	1
Invincible	35	175	2
Probe	35	171	3
RevealYourRank	35	110	4
MasterFlag1	35	103	5
Zixerqath	35	85	6
Hobbes	35	82	7
Hayati	35	56	8

Retrieved from "http://www.strategousa.org/wiki/index.php/2009_Computer_Stratego_World_Championship"