Kombinatoorne mänguteooria

Kombinatoorne mänguteooria, tuntud ka kui CGT, on rakendusmatemaatika ja teoreetilise arvutiteaduse haru, mis uurib kombinatoorseid mänge ja erineb "traditsioonilisest" või "majanduslikust" mänguteooriast. CGT tekkis seoses erapooletute mängude teooriaga, eelkõige kahe mängija mänguga Nim, rõhuasetusega teatud tüüpi kombinatooriliste mängude "lahendamisele".

Mäng peab vastama mitmele tingimusele, et olla kombinatoorne mäng. Need on järgmised:

Mängus peab olema vähemalt kaks mängijat.
Mäng peab olema järjestikune (st mängijad peavad vaheldumisi mängima.)
Mängus peab olema täiuslik informatsioon (st mingit teavet ei tohi varjata, nagu pokkeris).
Mäng peab olema deterministlik (s.t. ei tohi olla juhuslik). Õnn ei ole mängu osa.
Mängul peab olema kindel arv võimalikke käike.
Mäng peab lõpuks lõppema.
Mäng peab lõppema, kui üks mängija ei saa enam liikuda.

Kombinatoorne mänguteooria piirdub suures osas kombinatooriliste mängude alamhulga uurimisega, mis on kahe mängijaga, piiratud ning millel on võitja ja kaotaja (st ei lõpe viikuga).

Neid kombinatoorseid mänge saab kujutada puudena, mille iga tipp on mäng, mis tuleneb konkreetsest käigust mängust, mis asub puu otseses allosas. Nendele mängudele saab määrata mänguväärtusi. Nende mänguväärtuste leidmine pakub CG-teoreetikutele suurt huvi, nagu ka mängude liitmise teoreetiline kontseptsioon. Kahe mängu summa on mäng, milles iga mängija peab oma mänguvoorul liikuma ainult ühes kahest mängust, jättes teise mängu samaks.

Elwyn Berlekamp, John Conway ja Richard Guy on selle teooria rajajad. Nad töötasid koos 1960ndatel aastatel. Nende avaldatud teos kandis pealkirja Winning Ways for Your Mathematical Plays.

Definitsioonid

Teoorias on kaks mängijat, keda nimetatakse vasakuks ja paremaks. Mäng on midagi, mis võimaldab vasakul ja paremal teha käike teistesse mängudesse. Näiteks malemängus on tavaline algseadistus. Võiks aga mõelda ka malemängust pärast esimest käiku kui teisest mängust, mille seadistus on teistsugune. Seega nimetatakse iga positsiooni ka partiiks.

Mängude tähistus on {L|R}. L {\displaystyle L} $L$ on mängud, kuhu vasakpoolne mängija saab liikuda. R {\displaystyle R} $R$ on mängud, kuhu saab liikuda parem mängija. Kui te tunnete malenotatsiooni, siis tavaline malekomplekt on mäng

{ a 3 , a 4 , N a 3 , b 3 , b 4 , c 3 , c 4 , N c 3 , ... | a 6 , a 5 , N a 6 , b 6 , b 5 , c 6 , c 5 , N c 6 , ... } {\displaystyle \{a3,a4,Na3,b3,b4,c3,c4,Nc3,\dots |a6,a5,Na6,b6,b5,c6,c5,Nc6,\dots \}} $\{a3,a4,Na3,b3,b4,c3,c4,Nc3,\dots |a6,a5,Na6,b6,b5,c6,c5,Nc6,\dots \}$

Punktid "..." tähendavad, et käike on palju, seega ei ole kõik näidatud.

Male on väga keeruline. Parem on mõelda lihtsamate mängude peale. Nim näiteks on palju lihtsam mõelda. Nimi mängitakse nii:

On null või rohkem loendurihunnikut.
Ühel mänguvoorul võib mängija võtta ühest hunnikust nii palju mängumärke, kui ta soovib.
Mängija, kes ei suuda teha käiku, kaotab.

Lihtsaim mäng Nim algab üldse ilma loenduriteta! Sellisel juhul ei saa kumbki mängija liikuda. See on näidatud {|}. Mõlemad pooled on tühjad, sest kumbki mängija ei saa liikuda. Esimene mängija ei saa liikuda ja seega kaotab. CGT-s kirjutatakse {|} sageli sümboliks 0 (null).

Järgmise lihtsaima mängu puhul on ainult üks hunnik, millel on ainult üks loendur. Kui vasakpoolne mängija läheb esimesena, peab see mängija võtma loenduri, jättes paremale mängijale käiguta ({|} või 0). Kui selle asemel liigub parem mängija esimesena, ei ole vasakule enam ühtegi käiku. Seega võivad nii vasak- kui ka parempoolne mängija teha käigu 0. See on näidatud kujul {{|}|{|}} ehk {0|0}. Esimene mängija, kes esimesena liigub, võidab. Mängud, mis on võrdsed {0|0}, on väga olulised. Need kirjutatakse sümboliga * (täht).

Küsimused ja vastused

K: Mis on kombinatoorne mänguteooria?

V: Kombinatoorne mänguteooria (CGT) on rakendusmatemaatika ja teoreetilise arvutiteaduse haru, mis uurib kombinatoorseid mänge ja erineb "traditsioonilisest" või "majanduslikust" mänguteooriast.

K: Millistele tingimustele peab mäng vastama, et seda saaks pidada kombinatooriliseks mänguks?

V: Selleks, et mängu saaks pidada kombinatooriliseks mänguks, peab selles olema vähemalt kaks mängijat, see peab olema järjestikune (st mängijad vahelduvad kordamööda), selles peab olema täiuslik teave (st teave ei ole varjatud), see peab olema deterministlik (st ei tohi olla juhuslik), õnne ei tohi mängus osaleda, peab olema kindel arv võimalikke käike, mäng peab lõpuks lõppema ja mäng peab lõppema, kui üks mängija ei saa enam käia.

K: Millist tüüpi mängudele keskendub kombinaatoriline mänguteooria?

V: Kombinatoorne mänguteooria keskendub peamiselt kahe mängijaga piiratud mängudele, millel on võitjad ja kaotajad (st mis ei lõpe võrdsete tulemustega).

K: Kuidas esitatakse seda tüüpi mänge?

V: Seda tüüpi mänge saab kujutada puude abil, mille iga tipp esindab mängu tulemuseks olevat konkreetset käiku otse puu all olevast käigust.

K: Millised on CG-teoreetikute eesmärgid?

V: Mõned CG-teoreetikute eesmärgid hõlmavad nii seda tüüpi mängude väärtuste leidmist kui ka "mängu lisamise" kontseptsiooni mõistmist, mille puhul iga mängija teeb kahes erinevas mängus ainult ühe käigu, jättes teise mängu oma käigu ajal muutmata.

K: Kes asutas CGT?

V: Elwyn Berlekampi, John Conwayt ja Richard Guy'd peetakse CGT asutajateks nende 1960. aastatel avaldatud teoses "Winning Ways for Your Mathematical Plays".