ITI0011:Tikumäng

Tagasi kursuse lehele

Tööversioon! Lõplik versioon 2. nädalaks.

Tikumäng on kahe mängija mäng, kus mängijad võtavad kordamööde tikke laualt. Kes võtab viimase tiku, on võitnud.

Laual on alguses N tikku. Mängija tohib oma käigu korral võtta laualt 1 kuni M tikku (1 < M < N). See tähendab, et mängija peab vähemalt 1 tiku võtma. Sedasi kordamööde käies mängitakse seni, kuni laual pole ühtegi tikku. Mängija, kes viimase(d) tiku(d) võttis, on võitja.

M ja N lepitakse enne mängu algust kokku ning neid mängu jooksul ei muudeta.

Lihtsam variant

Vaatame varianti, kus N = 10 ja M = 3.

Laual on 10 tikku:

| | | | | | | | | |

Kaks mängijat võtavad vaheldumisi laualt ikke ära. Kumbki võib võtta kas ühe, kaks või kolm tikku. Võtmata jätta ei tohi ja üle kolme võtta ei või.

Võidab mängija, kes võtab viimase tiku laualt.

Näiteks üks võimalik mängukäik on selline:

• Mängija A võtab kaks tikku, lauale jääb 8 tikku.
• Mängija B võtab 3 tikku, lauale jääb 5 tikku.
• Mängija A võtab 1 tiku, lauale jääb 4 tikku.
• Mängija B võtab 1 tiku, lauale jääb 3 tikku.
• Mängija A võtab kõik 3 tikku, lauale ei jää enam ühtegi tikku ja mängija A on võitnud.

Kuidas tikumängus võita

Üks viis tikumängus võitmiseks oleks mõelda ette oma võimalikud käiguvariandid, vastase võimalikud kägivariandid, seejärel tekkivad oma käiguvariandid jne. Sedasi tehakse paljude kaheinimese mängude puhul (male, kabe, gomoku).

Õnneks on tikumängu võitmine palju lihtsam. Selle võitmiseks ei pea käike ette vaatama.

Vaatleme mängu, kus N = 10 ja M = 3. Alustame käikude vaatamist tagantpoolt. Kui mängijal A on ees neli tikku:

| | | |

siis ükskõik, mitu tikku mängija A võtab, võidab vastasmängija B (eeldusel, et vastasmängija teeb optimaalse käigu). Ehk siis, kui A võtab 1 tiku, võtab B 3 tikku. Kui A võtab 2 tikku, võtab B 2 tikku. Ning kui A võtab 3 tikku, võtab B 1 tiku.

Kuidas teha nii, et vastasel jääks ette 4 tikku? Kui mängijal A on ees kaheksa tikku:

| | | | | | | |

siis saab mängija B igal juhul tekitada olukorra, kus mängijale A jääb ette 4 tikku. Loogika on sama nagu 4 tiku puhul. Peale mängija A käiku võtab mängija B niipalju tikke, et lauale jääks 4 tikku.

Üldpõhimõte on järgmine:

• mängija on kaotusseisus, kui N jagatud (M + 1)-ga annab jäägiks 0. See tähendab, et kui jagan laual olevate tikkude arvu summa arvuga (M + 1) ja võtan jäägi (näiteks 5 / 3 annab jäägi 2), siis seis on kaotusseis, kui jääk on 0.
• igal muul juhul on mängija võiduseisus ning võidukäigu saab ta arvutada sama põhimõtte järgi: võidukäik (võetavate tikkude arv) = jääk N jagatud (M + 1) korral

Põhiosa (5p)

Realiseerida tikumäng fikseeritud parameetritega N = 10 ja M = 3. Ehk siis mängu alguses on laual 10 tikku. Igal käigul tohib võtta 1, 2 või 3 tikku.

Nõuded programmile:

• Alustab inimene.
• Inimese käigu ajal küsitakse tikkude arvu, mille kasutaja saab sisestada klaviatuurilt.
• Sisendit tuleb kontrollida. See tähendab, et sisestatud tikkude arv peab olema lubatud vahemikus.
• Kui sisend pole korrektne, korratakse sisendi küsimise protsessi.
• Kui kasutaja on teinud korrektse käigu, on arvuti käik.
• Arvuti teeb oma käigu ajal suvalise (random) käigu, mis vastab reeglitele. Välja arvatud juhul, kui arvuti saab ühe käiguga võita (kui laual on 3 või vähem tikke).
• Peale arvuti käiku on jälle inimese käik.
• Sedasi käiakse kordamööda, kuni üks mängija võidab
• Peale iga mängija käiku kuvatakse mänguseis (tikkude arv laual).

Lisaks:

• programm peab olema kirjutatud kasutades allolevat malli. See on vajalik, et saaksite oma koodi testida.
• kood peab olema mõistlikult kommenteeritud.
• kood peab vastama checkstyle nõuetele.

Etteantud GameOfSticks.java mall:

<source lang="java">

public class GameOfSticks {

public static void main(String[] args) {

}

public static int getComputerMove(int sticksOnBoard) { return -1; } }

</source>

Lisaülesanne: dünaamilised parameetrid (2p)

Mängu alguses saab kasutaja määrata, mitu tikku on laual alguses (N) ja mis on maksimaalne käigu suurus (M).

Nõuded (lisaks põhiosale):

• mängu alguses küsitakse kasutajale tikkude arvu, millest mängu alustatakse (N), ja maksimaalne tikkude arv, mis korraga võtta tohib (M).
• parameetrite piirangud: 8 <= N < 40, 2 <= M < N/2

Lisaülesanne: võidukäik (1p)

Arvuti peab oma käigu ajal tegema optimaalse (võimaluse korral võidu-) käigu. Vt kirjeldust eespoolt #Kuidas tikumängus võita.

Kui realiseeritud on vaid põhiosa, saab selle lisaülesande lahendamise eest 1p. Kui realiseeritud on lisaosa dünaamiliste parameetrite kohta, saab selle ülesande eest 2p.

Lisaülesanne: võidukäigu õppimine (3p)

Arvuti õpib mängitud mängude pealt, kuidas peaks mängima, et võita. See lisaülesanne tühistab eelmise võidukäigu lisaülesande (ehk siis valida tuleb üks).

Üks viis teha tikumängule tehisintellekt (AI) on analüüsida mängu ülesehitust ning selle järgi koostada valem, millega saab arvutada mängija (või arvuti) kõige optimaalseima käigu. Selles lisaosas on vaja teha täpselt vastupidist. Tuleb luua tehisintellekt, mis analüüsib varasemaid mänge ning nende tulemuste põhjal formuleerib järgnevatele mängudele strateegia.

Siinne kirjeldus on toodud N = 10 ja M = 3 kohta (ehk siis laual on alguses 10 tikku ja korraga võib ära võtta 1 kuni 3 tikku). Kui oled realiseerinud lisaosa, kus N ja M võivad muutuda, piisab sellest, kui ajalugu hoitakse seni, kuni M ja N on samad. Kui neid muudetakse, võid alustada algseisust (ehk siis ajalugu puudub).

AI näide tikumängule:

• Oletame, et AI-l on iga laual oleva tiku jaoks kott ja selle sees on esialgu 3 (M=3 korral) nummerdatud (1..3) kuuli.
• Igal arvuti käigul võtab arvuti vastavalt seisule õigest kotist (mis viimase laualoleva tiku kohta käib) suvalise kuuli ning "paigutab" selle koti kõrvale. Seejärel enda käiguna eemaldab arvuti laualt niimitu tikku, kui kuulil kirjas oli.
• Kui arvuti võidab selliselt oma käike valides, siis paneb ta igasse kotti kaks samasugust kuuli, mis sellest kotist välja sai võetud (mõlemal kuulil on sama arv). Kui arvuti kaotab, viskab ta kottide kõrval olevad kuulid minema juhul, kui kotis on sellise arvuga kuul (kotis peab alati olema vähemalt üks kuul igast arvust 1 - 3 (1 - M))
• Mida rohkem mänge mängitakse, seda rohkem "hea valiku" kuule koguneb ning kotist suvalise kuuli võtmisel on tõenäolisem, et arvuti teeb häid käike.

Näide:

Vaatame olukorda, kus alguses on 10 tikku ja korraga võib võtta kuni 3 tikku. Koti sisud on järgmised:

kott	1	2	3	4	5	6	7	8	9	10
sisu	1,2,3	1,2,3	1,2,3	1,2,3	1,2,3	1,2,3	1,2,3	1,2,3	1,2,3	1,2,3

Aktiivne on see kott, kui palju on tikke laual. Alguses on kõige viimane kott aktiivne. Kui laual on 5 tikku, siis vastavalt kott number 5 jne.

Koti sisu näitab, milliste väärtustega kuulid selles kotis on. Alguses on igal pool 1, 2, 3. See tähendab, et sellisest seisust on võrdne võimalus võita, kui võtta kas 1, 2 või 3 tikku (tegelikult see nii ei ole, aga alguses on AI rumal ning ei oska ühte valikut teisele eelistada).

Kui nüüd täpsemalt mõelda, siis antud mängu puhul kotis "1" peaks olema vaid kuul "1". Kotis "2" kuulid "1" ja "2". Muud kuulid annaks tulemuseks käigu, mida ei ole võimalik sooritada. Kui laual on 1 tikk, ei saa sealt ära võtta rohkem kui ühe tiku jne.

Vaatame mängu, mis kulgeb järgmiselt:

• mängija võtab 2 tikku, alles jääb 8 tikku
• AI võtab suvaliselt kuuli "2" kotist number 8 (kuna 8 tikku oli sel hetkel laual). Seega AI võtab 2 tikku, 6 tikku jääb järele.
• mängija võtab 1 tiku, järele jääb 5 tikku.
• AI valib suvaliselt kuuli "1" kotist number 5, st võtab 1 tiku laualt, 4 tikku jääb järele.
• mängija võtab 2 tikku, 2 jääb järele.
• AI valib suvaliselt kuuli "2" kotist number 2. Lauale ei jää ühtegi tikku, arvuti võidab.

Nüüd on AI olukord selline:

kott	1	2	3	4	5	6	7	8	9	10
sisu	1,2,3	1,3	1,2,3	1,2,3	2,3	1,2,3	1,2,3	1,3	1,2,3	1,2,3
valitud		2			1			2

Kuna AI võitis, siis paneb ta valitud kuulid kotti tagasi ning lisab uued samade väärtustega kuulid:

kott	1	2	3	4	5	6	7	8	9	10
sisu	1,2,3	1,2,2,3	1,2,3	1,2,3	1,1,2,3	1,2,3	1,2,3	1,2,2,3	1,2,3	1,2,3

Nüüd on AI-l suurem võimalus võtta:

• 2 tikku, kui laual on 8 tikku
• 1 tikk, kui laual on 5 tikku
• 2 tikku, kui laual on 2 tikku

Kui arvuti kaotab, siis ta viskab valitud kuulid ära juhul, kui kotis on vähemalt üks selline kuul alles. Ehk siis, kui algselt oli kotis näiteks kuulid 1, 2, 2, 2, 3. Juhuslikult valib arvuti kuuli "2", kotti jääb 1, 2, 2, 3. Kui arvuti kaotab, siis visatakse see valitud kuul ära, kotti jääb 1, 2, 2, 3.

Ülesanne on kirjutada AI, mis uuendab kottide sisu iga mängu korral. Esialgu mängib AI suvaliselt, kuid mida mäng edasi, seda targemaid käike hakkab tegema.

Järgnev näide demonstreerib kuidas programm peaks käituma:

Sisesta tikkude arv mängu alguses: 10
Sisesta võimalik võetavate tikkude kogus ühel käigul: 3

1. mäng:
10 tikku laual ja korraga saab võtta kuni 3 tikku.

| | | | | | | | | | (10)

Mängija võtab 3
| | | | | | |       (7)
Arvuti võtab 2
| | | | |           (5)
Mängija võtab 3
| | |               (3)
Arvuti võtab 2
|                   (1)
Mängija võtab 1

Mängija võitis!
Kas mängid veel (jah/ei)? jah

2.Mäng:

| | | | | | | | | | (10)

Mängija võtab 1
| | | | | | | | |   (9)
Arvuti võtab 1
| | | | | | | |     (8)
Mängija võtab 3
| | | | |           (5)
Arvuti võtab 3
| |                 (2)
Mängija võtab 2

Mängija võitis!
Kas mängid veel (jah/ei)? jah

3.Mäng:

| | | | | | | | | | (10)

Mängija võtab 3
| | | | | | |       (7)
Arvuti võtab 2
| | | | |           (5)
Mängija võtab 3
| |                 (2)
Arvuti võtab 2

Arvuti võitis!
Kas mängid veel (jah/ei)? ei

Näidatud väljund ei pea täpselt selline olema. See on lihtsalt üks näide.