perholmberg.net

Seger i Kalaha-AI-turnering

2004-09-23. Vinnaren i årets Kalaha-AI-turnering på BTH är KalahMigKalaha programmerad av mig och Mikael Gustavsson.

KalahMigKalaha (kalla-mig-Kalaha) är ett program som söker efter det bästa draget i ett visst spelläge i det gamla brädspelet Kalaha. Algoritmen är minimax som är den klassiska algoritmen för att hitta draget som maximerar värdet för den ena spelaren samtidigt som värdet för den andra spelaren minimeras. Alpha-beta-pruning används för att sökningen ska hoppa över testa ointressanta spelsituationer.

23 AI-program var anmälda till turnering som avgjordes med japansk turneringsmodell. KalahMigKalaha började med att vinna sina tre första matcher. Sedan var det dags att möta Butcher, en jämn match där Butcher till slut blev vinnare. Tack vare turneringsmodellen lyckades dock KalahMigKalaha arbeta sig tillbaka och nå finalen, som skulle gå mot - Butcher. Eftersom KalahMigKalaha förlorade mot Butcher en stund tidigare så trodde många att saken redan var avgjord. Men det fanns en reservplan. Vi aktiverade en alternativ variant av alpha-beta-pruningen som hade visat sig vara lite effektivare vid programtestningen. Och tack vare vår ändring vann KalahMigKalaha!

Värt att notera är att KalahMigKalaha är skriven i Java. KalahMigKalaha vann under turneringen mot flera program skrivna i C, trots att program skrivna i C generellt är betydligt snabbare än program skrivna i Java och därför borde kunna göra mer omfattande sökningar på utsatt tid.

Det är möjligt att en modifierad version av KalahMigKalaha kommer att publiceras på perholmberg.net vid ett senare tillfälle.

Resultat från turneringen