ITI0011:Tikumäng

Tagasi kursuse lehele

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 on välja toodud #Mall sektsiooni all. Iga meetodi juures on kirjas, millise alamülesande kohta see käib. Required: main part tähendab seda, et selle meetodi peate implementeerima põhiosa testimise jaoks. Ehk siis põhiosa jaoks on vaja implementeerida meetodid:

• main() - põhiline loogika kordamööda käimise jms kohta läheb sinna.
• getNumberOfSticksOnBoard() - tagastab, mitu tikku on laual. Selleks on vajalik üks klassi muutuja, näiteks public static int sticks; klassi ploki sisse, kuid väljapoole meetoditest, mille väärtust iga käiguga muudetakse ja see meetod peaks selle lihtsalt tagastama.
• newGame() - alustab uut mängu. Sisuliselt peab see taastama tikkude seisu vastavalt N väärtusele.
• makeComputerMove() - arvuti teeb oma käigu. võidukäigu olemasolu korral võidukäik. muul juhul suvaline lubatud käik. meetod tagastab laual olevate tikkude arvu peale käiku. Kui laual on 10 tikku ja kutsutakse makeComputerMove(). Arvuti teeb näiteks käigu, mis võtab 3 tikku, see meetod peab tagastama sellisel juhul 7 (so allesjäänud tikkude arv).
• makeHumanMove(int) - etteantud numbri puhul tehakse vastav inimese käik. Meetod peaks kontrollima sisendit (kas mainitud käik on lubatud)

Ülejäänud meetodid võivad tühjaks jääda.

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

#Mall - peate implementeerima lisaks põhiosale järgmised meetodid:

• setInitialNumberOfSticksOnBoard(int) - meetodisse antakse kaasa üks täisarv, mis tähistab mängu alguses olevate tikkude arvu. See väärtus tuleks klassimuutujasse ära salvestada ja hiljem erinevates kontrollides ja arvutustes kasutada.
• setMaxNumberOfSticksToTake(int) - sarnaselt eelmisega, meetodiga antakse kaasa maksimaalne võetavate tikkude arv, mis tuleb ära salvestada klassimuutujasse. Hiljem tuleb seda väärtust kasutada erinevates arvutustes.

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.

Selle lisaülesande puhul peate muutma makeComputerMove() selliselt, et suvalise käigu asemel tagastatakse alati parim võimalik käik. Kui parimat käiku pole võimalik teha, siis tuleb tagastada suvaline.

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). Võib teha ka nii, et alguses küsitakse ära M ja N ning neid muuta ei saa.

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.

#Mall - peate täiendavalt implementeerima sellised meetodid:

• getComputerMove() - tagastab antud seisust võimaliku arvuti käigu, aga seda käiku ei mängita - ehk siis ühtegi tikku laualt ära ei võeta sellega. Kui seda meetodit samast seisust mitu korda välja kutsuda, peaks saama erinevaid tulemusi.
• makeComputerMove() ja makeHumanMove(int) meetodite puhul tuleb teha täiendused. Juhul, kui meetod tagastab 0 (ehk siis kumbki mängijates on võitnud), tuleb uuendada kottide seisu.

Mall

Etteantud mall GameOfSticks.java: <source lang="java">

import java.io.ByteArrayInputStream; import java.io.InputStream;

/**

* (Bigger) homework 01 - Game of sticks.
*
*/

public class GameOfSticks {

/** * The main method, which is the entry point of the program. * This is the method where the main logic of your game is. * @param args Arguments from the command line */ public static void main(String[] args) { }

/** * Returns the number of sticks on the board. * Required: main part. * @return Number of sticks on the board. */ public static int getNumberOfSticksOnBoard() { // TODO: should return the current number of sticks on board return -1; }

/** * Starts a new game (resets sticks on the board to N). * Required: main part. */ public static void newGame() { // your code here }

/** * In case of AI bonus task, gets the possible move * for AI given the board state (number of sticks on the board). * The move itself should NOT be done! * This method will be used to test your AI learning ability. * * Required: AI task. * @return Sticks to remove from the board in the given state. */ public static int getComputerMove() { return -1; }

/** * Makes the AI move * and returns the number of sticks on the board *after* the move. * The program should internally keep the track of the board state * (the number of sticks on the board). * The program should make the move and make the required operations * to store the move. So, if there are 10 sticks on the board and * AI takes 3, this method should return 7.

*

* AI has to make a legal move (1 <= move <= M). *

* In case of AI bonus task, if this method returns 0 (game is over), * the coefficients for different states should be modified accordingly. *

* Required: main part. * @return The number of sticks after the AI move. */ public static int makeComputerMove() { return -1; } /** * Sets the number of sticks initially on the board. * If this method is never called, your program should * still work with default value n = 10. * Required: dynamic game parameters. * @param n The number of sticks initially on the board. */ public static void setInitialNumberOfSticksOnBoard(int n) { // TODO: your code } /** * Sets the number of sticks a player can take during its turn. * If this method is never called, your program should * still work with default value m = 3. * Required: dynamic game parameters. * @param m The number of sticks a player can take during its turn. */ public static void setMaxNumberOfSticksToTake(int m) { // TODO: your code } /** * This method should accept * human player move. Internally, the program should * keep the board state (the number of stick on the board). * * This method is required to test the AI working part. * If this method returns 0 (game is over), * the coefficients for different states should be modified accordingly. * Required: main part. * @param sticksToTake The human player's move, how many sticks * the player takes. * @return The number of sticks after human player move. */ public static int makeHumanMove(int sticksToTake) { // TODO: your code return 0; } } </source>

Näpunäiteid

Mõned peatükid Java juhendist:

• Java:Muutujad#Klassimuutujad
• Java:Muutujad#Magic number - kui checkstyle plugin Eclipse'is hädaldab "magic number"
• Java:Kogumid