ITI0011:Tikumäng

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:

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.