2008 Computer Stratego World Championship

From StrategoUSA

Jump to: navigation, search

The 2008 Computer Stratego World Championship will be held December 5-8. 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. Participants will run their code on their own computer and use a downloadable client to connect to the server. Viewers will be able to logon to Metaforge and watch games as they are played, or replay completed games at a later time.

Contents

[edit] News

  • 2008-11-02: "Reveal Your Rank!" registered
  • 2008-08-12: "Hobbes" registered
  • 2008-04-07: "Master of the Flag" registered
  • 2008-04-03: "Invincible" registered
  • 2008-04-01: "Probe" registered
  • 2008-04-01: Tournament announced

[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

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

[edit] Objective

The inaugural 2007 tournament demonstrated that existing Stratego AI programs are capable of playing at a high level, although none is able to compete equally against a moderately skilled human opponent. This tournament intends to advance Stratego AI by:

Improving existing AIs. Most of the programs entered last year faltered during the endgame, and would be considerably more competitive with improved endgame logic. All of the programs demonstrated weak positional play, for example, lacking the ability to establish a perimeter defense to defend the flag.

Attracting new entries. The community of Stratego AI programmers is small at this time. However, the Stratego AI SDK considerably lowers the barriers to entry by removing the need to write a UI, and provides an opportunity for programs to be tested against both human and computer opponents. Also, there is growing recognition that Stratego is not, in fact, an intractable problem, as once supposed, but rather a challenging and rewarding opportunity for AI programmers. (Academics, take note.)

Encouraging discussion. Most of the existing Stratego AI programs, some of which are commercial products, are closely guarded secrets. But for Stratego AI to advance dialog is necessary, so a shared body of knowledge can begin to amass. This wiki can serve as an ideal forum for Stratego AI programmers to discuss, at least in general terms, how their applications address specific topics. It is worth noting here that Stratego programming is so wide open at present that even as fundamental a question as the efficacy of recursion remains a matter of debate. So there is both a lot of room for experimentation and a corresponding opportunity to compare and evaluate competing algorithms.

[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

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] Additional Rules

Last year's tournament demonstrated that the Two-Squares Rule and More-Squares Rule are insufficient to prevent two computer programs from lapsing into repetitive cycles and other pointless moves. For the 2008 tournament Probe will implement three additional constraints on its own moves, in the hope that games it plays will be more interesting for human observers:

Position Repetition Rule. This rule restricts Probe from making a move that would repeat a position found earlier in the game. Its purpose is to prevent repetitive patterns, such as alternating chase pairs, that do not violate the More-Squares Rule. The rule does not apply to an immediate back-and-forth repetition, which is covered by the Two-Squares Rule, nor to moves by a piece that is being chased.

Resumed Chase Rule. This rule prevents Probe from resuming a chase after the end of a previous chase by the same pair of pieces. Without this rule, Probe will often chase a piece until stopped by the Two-Squares Rule, move another piece and then resume the chase. The rule does not apply if movement of other pieces in the immediate area suggests that resuming the chase might produce a productive outcome.

Continuous Chase Rule. This rule prevents Probe from chasing a piece with another piece for more than ten consecutive moves. Its purpose is to prevent long, pointless chase sequences, especially during the endgame.

[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] Programming Tips

The easiest way to develop a Stratego AI implementation is to use Java as the programming language. An open source compiler can be downloaded from www.eclipse.org. Support for C++ code is also available via the native Stratego AI adapter.
A java prototype for a "random player" is available for interested programmers and can be a big time saver for getting started on a Stratego AI implementation. For more details, 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

Image:Hol.png Invincible
ProgrammerVincent de Boer
NationalityDutch
Year Created2007
Last Update2007
Company/AffiliationTU Delft
Link-


[edit] Master of the Flag 1

Image:Ger.png Master of the Flag
ProgrammerSven Jug
NationalityGerman/American
Year Created2004
Last Update2008
Company/AffiliationJayoogee.com
Linkhttp://www.jayoogee.com/masteroftheflag/


[edit] Master of the Flag 2

Image:Ger.png Master of the Flag
ProgrammerSven Jug
NationalityGerman/American
Year Created2004
Last Update2008
Company/AffiliationJayoogee.com
Linkhttp://www.jayoogee.com/masteroftheflag/


[edit] Probe

Image:Usa.png Probe
ProgrammerImer Satz
NationalityAmerican
Year Created1983
Last Update2008
Company/AffiliationImersatz GmbH
Linkhttp://www.probe.imersatz.com/


[edit] Hobbes

Image:Hol.png Hobbes
ProgrammerMaarten Schadd
NationalityDutch
Year Created2008
Last Update2008
Company/AffiliationMaastricht University
Linkhttp://www.cs.unimaas.nl/maarten.schadd/Stratego/


[edit] Reveal Your Rank!

Image:Lat.png Reveal Your Rank!
ProgrammerRaimonds Rudmanis
NationalityLatvian
Year Created2001
Last Update2006
Company/AffiliationNone
Linkhttp://www.yellowgames.com/


[edit] Game Results

[edit] Game Log

Times are specified as reported by the Metaforge server.

Time Creator Joiner Winner Winner Score Loser Score Moves Result
Friday
Fri 10:54ProbeRevealYourRankProbe61379Flag capture
Fri 11:12ProbeRevealYourRankProbe61693Flag capture
Fri 11:43ProbeRevealYourRankProbe61879Flag capture
Fri 12:07MasterFlag1RevealYourRankRevealYourRank61778No moves
Fri 12:13MasterFlag1RevealYourRankMasterFlag161851Flag capture
Fri 12:17MasterFlag1RevealYourRankRevealYourRank61654No moves
Fri 12:20MasterFlag1RevealYourRankRevealYourRank61344Flag capture
Fri 12:23MasterFlag1RevealYourRankRevealYourRank61564Flag capture
Fri 12:27ProbeRevealYourRankProbe61353Flag capture
Fri 12:41MasterFlag2RevealYourRankMasterFlag261431Flag capture
Fri 12:42ProbeRevealYourRankProbe61333No moves
Fri 12:56MasterFlag2RevealYourRankMasterFlag261581No moves
Fri 13:09MasterFlag2RevealYourRankMasterFlag261379Flag capture
Fri 13:19MasterFlag2RevealYourRankMasterFlag261401Flag capture
Fri 13:30MasterFlag2RevealYourRankMasterFlag261481No moves
Fri 17:43MasterFlag1ProbeProbe61682Flag capture
Fri 17:57MasterFlag1ProbeProbe61430Flag capture
Fri 18:19MasterFlag1ProbeProbe61606Flag capture
Fri 18:37MasterFlag1ProbeProbe61544Flag capture
Fri 19:21MasterFlag1ProbeProbe611336Flag capture
Saturday
Sat 8:53InvincibleHobbesDraw332034Draw
Sat 9:44InvincibleHobbesInvincible61949Forfeit
Sat 10:48InvincibleHobbesDraw331180Draw
Sat 12:00InvincibleHobbesInvincible611278No moves
Sat 13:15InvincibleHobbesInvincible611312Flag capture
Sat 11:25ProbeMasterFlag2MasterFlag2611120Flag capture
Sat 11:40ProbeInvincibleInvincible61878Forfeit
Sat 11:57ProbeInvincibleProbe61511Forfeit
Sat 11:58ProbeMasterFlag2Probe61549No moves
Sat 12:16ProbeMasterFlag2Probe61349Flag capture
Sat 12:29ProbeMasterFlag2Probe61351Flag capture
Sat 12:37ProbeInvincibleProbe611237Flag capture
Sat 12:51ProbeMasterFlag2Probe61459Flag capture
Sat 13:36MasterFlag1InvincibleMasterFlag161775Flag capture
Sat 13:43MasterFlag1InvincibleInvincible61832No moves
Sat 13:52MasterFlag1InvincibleInvincible611150No moves
Sat 14:01ProbeHobbesProbe61437Flag capture
Sat 14:02MasterFlag1InvincibleInvincible611490Flag capture
Sat 14:17MasterFlag1InvincibleDraw332288Draw
Sat 14:24ProbeHobbesProbe61199Flag capture
Sat 15:47ProbeHobbesProbe61653Flag capture
Sat 16:08ProbeInvincibleInvincible61936No moves
Sat 17:45ProbeInvincibleProbe61485Flag capture
Sunday
Sun 3:00ProbeHobbesProbe61631Flag capture
Sun 3:27ProbeHobbesProbe61335Flag capture
Sun 4:17MasterFlag1HobbesMasterFlag161325Flag capture
Sun 4:37MasterFlag1HobbesMasterFlag161429Flag capture
Sun 4:50MasterFlag1HobbesMasterFlag161273No moves
Sun 6:09MasterFlag1HobbesMasterFlag1611523Flag capture
Sun 6:28MasterFlag1HobbesMasterFlag161335Flag capture
Sun 8:41MasterFlag2HobbesMasterFlag261565No moves
Sat 10:38MasterFlag2HobbesMasterFlag2611419No moves
Sun 11:54MasterFlag2HobbesMasterFlag261767Flag capture
Sun 12:08MasterFlag2HobbesMasterFlag261239Flag capture
Sun 14:27MasterFlag2HobbesMasterFlag2611911Flag capture
Sun 16:13MasterFlag2InvincibleDraw333536Draw
Sun 16:52MasterFlag2InvincibleDraw332030Draw
Sun 16:12MasterFlag2InvincibleMasterFlag261971Flag capture
Sun 16:28MasterFlag2InvincibleMasterFlag261627Flag capture
Sun 18:45MasterFlag2InvincibleDraw333315Draw
Sun 16:58MasterFlag1MasterFlag2MasterFlag261430Flag capture
Sun 17:17MasterFlag1MasterFlag2MasterFlag261678Flag capture
Sun 17:28MasterFlag1MasterFlag2MasterFlag261600Flag capture
Sun 17:43MasterFlag1MasterFlag2MasterFlag261694Forfeit
Sun 17:58MasterFlag1MasterFlag2MasterFlag261714No moves
Monday
Mon 9:58RevealYourRankInvincibleInvincible61326No moves
Mon 10:10RevealYourRankInvincibleRevealYourRank611257Flag capture
Tuesday
Tue 10:49RevealYourRankInvincibleInvincible611111No moves
Tue 10:53RevealYourRankInvincibleInvincible61327Forfeit
Tue 10:49RevealYourRankInvincibleRevealYourRank61640Flag capture
Tue 10:21RevealYourRankHobbesRevealYourRank61340Flag capture
Tue 10:36RevealYourRankHobbesRevealYourRank61350Flag capture
Tue 11:00RevealYourRankHobbesRevealYourRank61504Flag capture
Tue 11:20RevealYourRankHobbesRevealYourRank61426Flag capture
Tue 11:29RevealYourRankHobbesRevealYourRank61206Flag capture


[edit] Match Cross Table

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

AI Program W D L Hobbes Invincible MasterFlag1 MasterFlag2 Probe RevealYourRank
Image:Hol.png Hobbes 0 2 23 x 0-2-3 0-0-5 0-0-5 0-0-5 0-0-5
Image:Hol.png Invincible 11 6 8 3-2-0 x 3-1-1 0-3-2 2-0-3 3-0-2
Image:Ger.png MasterFlag1 7 1 17 5-0-0 1-1-3 x 0-0-5 0-0-5 1-0-4
Image:Ger.png MasterFlag2 18 3 4 5-0-0 2-3-0 5-0-0 x 1-0-4 5-0-0
Image:Usa.png Probe 22 0 3 5-0-0 3-0-2 5-0-0 4-0-1x 5-0-0
Image:Lat.png RevealYourRank 11 0 14 5-0-0 2-0-3 4-0-1 0-0-5 0-0-5 x


[edit] Score Summary

AI Program Games Played Total Score Ranking
Image:Usa.png Probe 25 135 1
Image:Ger.png MasterFlag2 25 121 2
Image:Hol.png Invincible 25 92 3
Image:Lat.png RevealYourRank 25 80 4
Image:Ger.png MasterFlag1 25 62 5
Image:Hol.png Hobbes 25 29 6


Retrieved from "http://www.strategousa.org/wiki/index.php/2008_Computer_Stratego_World_Championship"
Personal tools