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).

Täpsem kirjeldus lähiajal.