Kombinatoriska spel: Tic-Tac-Toe Theory

  Combinatorial Games: Tic-Tac-Toe Theory är en monografi om matematiken i tic-tac-toe och andra positionsspel , skriven av József Beck . Den publicerades 2008 av Cambridge University Press som volym 114 i bokserien Encyclopedia of Mathematics and its Applications ( ISBN 978-0-521-46100-9 ).

Ämnen

Ett positionsspel är ett spel där spelare omväxlande tar besittning av en given uppsättning element, med målet att bilda en vinnande konfiguration av element; till exempel, i tic-tac-toe och gomoku , är elementen kvadraterna i ett rutnät, och de vinnande konfigurationerna är rader av rutor. Dessa exempel är symmetriska: båda spelarna har samma vinnande konfigurationer. Emellertid inkluderar positionella spel även andra möjligheter, såsom maker-breaker-spel där en spelare ("makaren") försöker bilda en vinnande konfiguration och den andra ("brytaren") försöker skjuta upp det resultatet på obestämd tid eller tills slutet av spelet. I symmetriska positionsspel kan man använda ett strategistöldargument för att bevisa att den första spelaren har en fördel, men att inse denna fördel med en konstruktiv strategi kan vara mycket svårt.

Enligt Hales–Jewett-satsen , i tic-tac-toe-liknande spel som involverar bildande av linjer på ett rutnät eller högre dimensionellt gitter, kan rutnät som är små i förhållande till sin dimension inte leda till ett ritat spel: när hela rutnätet är uppdelat mellan de två spelarna kommer en av dem nödvändigtvis att ha en linje. Ett av bokens huvudresultat är att något större rutnät leder till en "svag vinst", ett spel där en spelare alltid kan tvinga fram en linje (inte nödvändigtvis innan den andra spelaren gör det), men att rutnätet är större än en viss tröskel leder till ett "starkt drag", ett spel där båda spelarna kan hindra den andra från att bilda en linje. Dessutom kan tröskeln mellan en svag vinst och en stark oavgjort ofta bestämmas exakt. Beviset för detta resultat använder en kombination av den probabilistiska metoden , för att bevisa förekomsten av strategier för att uppnå det önskade resultatet, och avrandomisering , för att göra dessa strategier explicita.

Boken är lång (732 sidor), organiserad i 49 kapitel och fyra avsnitt. Del A tittar på skillnaden mellan svaga vinster (spelaren kan tvinga fram en vinnande konfiguration) och starka vinster (den vinnande konfigurationen kan tvingas existera innan den andra spelaren vinner). Det visar att, för maker-breaker-spel över punkterna på planet där spelarna försöker skapa en kongruent kopia av någon ändlig poänguppsättning, har maker alltid en svag vinst, men för att göra det måste ibland tillåta breaker att bildas en vinnande konfiguration tidigare. Den innehåller också en omfattande analys av tic-tac-toe-liknande symmetriska linjebildande spel, och diskuterar Erdős–Selfridge-satsen enligt vilken glesa uppsättningar av vinnande konfigurationer leder till ritade maker-breaker-spel. Del B av boken diskuterar den potentialbaserade metoden genom vilken Erdős–Selfridge-satsen bevisades, och utökar den till ytterligare exempel, inklusive några där tillverkaren vinner. Del C täcker mer avancerade tekniker för att bestämma resultatet av ett positionsspel, och introducerar mer komplexa spel av denna typ, inklusive väljar-väljare-spel där en spelare väljer två ovalda element och den andra spelaren väljer vilket som ska ge till varje spelare. Del D inkluderar nedbrytning av spel och användning av tekniker från Ramsey-teorin för att bevisa satser om spel. En samling öppna problem inom detta område finns i slutet av boken.

Publik och mottagning

Detta är en monografi, riktad till forskare inom detta område snarare än till en populär publik. Recensenten William Gasarch skriver att även om detta arbete förutsätter lite bakgrundskunskap hos sina läsare, utöver lågnivåkombinatorik och sannolikhet, "är materialet fortfarande svårt". På samma sätt klagar recensenten Kyle Burke på att "många definitioner och förklaringar är besvärligt 'mattetyngda'; odefinierade termer från avancerad matematik finns i överflöd i små exempel, där enklare beskrivningar skulle räcka".

Mycket av boken handlar om ny forskning snarare än att bara sammanfatta det som tidigare var känt. Recensenten Ales Pultr kallar denna bok "en mycket grundlig och användbar behandling av ämnet (hittills otillräckligt presenterad i litteraturen), med ett enormt lager av resultat, kopplingar till andra teorier och intressanta öppna problem". Gasarch håller med: "När du har kommit igenom det kommer du att ha lärt dig en hel del matematik." En pseudonym recensent för European Mathematical Society tillägger att boken kan vara "en milstolpe i utvecklingen av kombinatorisk spelteori" .