Världens bästa Tetris AI
Colin Fahey är vad jag vet den ende som systematiskt samlat algoritmer som spelar Tetris och genom att ha standardiserade regler också kunnat jämföra algoritmerna sinsemellan. Under sektion 10. Best one-piece Tetris-playing algorithm in the world beskrivs en algoritm som är skriven av fransmannen Pierre Dellacherie och som officiellt är den bästa kända altoritmen. Den gör ca 675.000 bitar i snitt per spel i en hastighet av 160 bitar per sekund på en 800 Mhz dator. Algoritmen som detta projekt (TetrisAi) använder sig av är något vassare och gör 1.800.000 bitar i snitt per spel i en hastighet av 15.000 bitar per sekund (C++ versionen) på en 2.8 Ghz Pentium. Den gör alltså nästan tre gånger så många bitar per spel och är ca 25 gånger så snabb om man tar hänsyn till skillnad i klockfrekvens. Har under de senaste tio åren inte hittat någon algoritm som gör fler bitar per spel (d.v.s spelar bättre) men dock en som är snabbare och det är HP's Tetris som enligt hans egna uppgifter gör 24.000 bitar per sekund på en 2.2 Ghz PC.
Hur algoritmen fungerar
När programmet TetrisAi ska hitta det bästa sättet att placera aktuell bit, går den igenom alla giltiga sätt att placera biten. För varje giltigt drag/placering rensas eventuellt kompletta/fulla rader varefter positionen är redo att värderas av algoritmen. Om utöver aktuell bit även nästa bit är känd och/eller sökdjupet (level) är större än antalet kända bitar, är algoritmen för vilka positioner som ska värderas något mer komplicerad vilket jag kommer beskriva då Scala-versionen får stöd för detta. Den position som har den lägsta värderingen ses av algoritmen som det bästa draget för aktuell bit. Antag att vi har följande position:
Siffrorna i vänsterkant visar y-värdet och siffrorna i underkant visar x-värdet. Som algoritmen ser ut nu, och som den sett ut sedan C++ versionen skrevs någon gång mellan 2001-2002, är att den värderar positionen utifrån tre egenskaper som den adderar ihop för att få fram den slutliga värderingen. Värdet på positionen kallas i algoritmen för equity och är en benämning tagen från Backgammon där den används som beteckning på värdet av en position. Det finns för övrigt ganska många likheter mellan Backgammon och Tetris t ex att man inte vet vilka bitar i Tetris eller tärningsslag i Backgammon som ska komma. Följande tre egenskaper mäts:
Konturens höjd
Denna egenskap mäter hur högt bygget är eller rättare sagt hur hög konturen är för respektive kolumn (x-värde):
Ju högre konturen är, desto större värde adderas till equity. Värdet 2,5 adderas för kolumnerna 1, 5 och 6, värdet 2,2 för kolumnerna 2, 4 och 7, värdet 1,8 för kolumnerna 0 och 3 och slutligen värdet 1,3 för kolumnerna 8 och 9. Totalt adderas 2,5*3 + 2,2*3 + 1,8*2 + 1,3*2 = 20.3 till equity. Detta exempel har en väldigt låg höjd med en storlek på 10x5 mot normalt 10x20. Hade spelplanen varit normalstor hade värdet blivit 0.1*10 = 1 i stället för 20.3, och då varit den egenskap (av tre) som påverkat värderingen av positionen minst.
Konturens struktur
Nästa egenskap som mäts och adderas till equity är avgränsade områden i konturen. Ett sådant område är avskilt med väggar på dess båda sidor. När spelet börjar är detta avgränsade område 10x20. Det minsta möjliga området är 1x1 likt C i bilden nedan. Ju högre området är desto större värde adderas till equity. Ju bredare desto lägre värde adderas till equity med undantag för bredden 3 som har en större konstant än bredden 2 och anses alltså vara sämre.
För att beräkna värdet av ett område multipliceras en konstant som varierar med bredden med en annan konstant som varierar med höjden. Område A har bredden 1 vilket ger konstanten 4,25 och höjden två som ger konstanten 1,19 och produkten 5,0575. Område B har bredden 3 som ger konstanten 3.1 och höjden 1 som ger konstanten 0,42 och produkten 1,302.
Det finns ytterligare en parameter att ta hänsyn till i denna beräkning och det är huruvida väggarna på respektive sida om området har samma höjd. Område B har samma höjd (y=2) på de väggar som avgränsar området (kolumnerna 1 och 5) till skillnad från område D där höjden på väggarna skiljer sig (kolumn 6 har y=2 och kolumn 10 har y=0). Område B anses vara något gynsammare än D:
- A: 1x2 = 4,25*1,19 = 5.0575
- B: 3x1 = 3,1*0,42 = 1,302
- C: 1x1 = 4,25*0,42 = 1,785
- D: 3x1 = 3,1*0,5 = 1,55
- E: 2x2 = 2,39*1,19 = 2,8441
Det finns en felaktighet i hur områden som angränsar mot den högra väggen (kolumn 10) beräknas i C++ versionen (version 1.0). Där sätts y-värdet för kolumn 10 till 2 (lägsta y-värde på konturen) varpå område D uppfattas som ett område vars omslutande väggar har samma höjd och får därför samma värdering som område B. Detta är åtgärdat i aktuell version av algoritmen: TengstrandBoardEvaluator1 (version 1.1) och verifierat med testet TengstrandBoardEvaluator1Test.
Håligheter
Denna egenskap mäter håligheter i positionen. Till håligheter räknas rader där det finns hål som täcks av någon ovanliggande rad. I bilden nedan är rad 3 täckt av rad 2 i kolumn 6.
För varje rad med början på den högsta konturen (y=2) t.o.m sista raden (y=4) görs en sak till förutom att beräkna nyss nämnda konstant. För varje kolumn i raden görs följande: i fallet att en ruta är tom kontrolleras det om rutan är täckt genom att se i fall konturen för kolumnen är mindre än y-värdet för raden vilket i så fall betyder att vi hittat ett hål. Därefter beräknas värdet som ska adderas till equity genom att multiplicera alla konstanter från och med raden som motsvarar konturen för den kolumn där hålet hittats till och med aktuell rad. Värdet 10 i beräkningen är positionens bredd:
- Rad 3: (1 - 0.1*0.3)*10 = 9,7
- Rad 4: (1 - 0,3*0,5)*10 = 8,5
Rad 4 multipliceras med konstanterna för rad 3 t.o.m 4 (3 då kolumn 4 är täckt av rad 3).
Totalt motsvarar egenskapen håligheter värdet 9,7+8,5 = 18,2 som equity räknas upp med.
Equity för respektive egenskap:
- Konturens höjd: 20,3
- Konturens struktur: 12,5386
- Håligheter: 18,2
Inga kommentarer:
Skicka en kommentar