ITI0011RUS:Matches
Вернуться на страницу предмета
Игра "спички" - это игра в которой два игрока по очереди берут спички со стола. Игрок взявщий последнюю спичку выигрывает.
На столе в начале игры N спичек. За один ход игроку можно взять со стола от 1 до M спичек (1 < M < N). Это означает, что на каждом ходу игрок обязан взять хотя бы одну спичку. Таким образом делая ходы по очереди игра продолжается до тех пор пока на столе не останется спичек. Игрок, взявщий спичку(и) последним, выиграл.
Значения M и N устанавливаются непосредственно перед началом игры и в процессе игры остаются неизменными.
Пример
Рассмотрим пример, где N = 10 и M = 3.
На столе 10 спичек:
| | | | | | | | | |
Двое игроков берут по очереди спички со стола. Каждый из игроков может взять одну, две, или три спички. Не взять ни одной нельзя, также как и взять более трех спичек.
Выигрывает тот игрок, который брал спички со стола последним.
Игра, например, может проходить так:
- Игрок A взял 2 спички, на столе осталось 8 спичек.
- Игрок B взял 3 спички, на столе осталось 5 спичек.
- Игрок A взял 1 спичку, на столе осталось 4 спички.
- Игрок B взял 1 спичку, на столе осталось 3 спички.
- Игрок A взял 3 спички, на столе больше спичек не осталось, и потому игрок A выиграл.
Выигрышная стратегия в игре
Выигрыть в игре можно просчитав заранее возможные ходы для себя, возможные ходы противника с учетом предполагаемого хода, после чего снова возможные ходы для себя учитывая свой предполагаемый ход в предыдущей попытке и предполагаемый ход противника. Так работает искуственный интеллект во многих играх для двух игроков (шахматы, шашки, гомоку).
К счастью, существует гораздо более простой способ выиграть в этой игре. Для того чтобы выиграть не нужно просчитывать свои ходы и ходы противника на несколько ходов вперед.
Рассмотрим пример игры, где N = 10 и M = 3. Рассмотрим возможные ходы с конца игры. Когда перед игроком A лежат 4 спички:
| | | |
то сколько бы спичек игрок A не брал, всегда выиграет игрок B (предполагая, что стратегия игрока B оптимальна). Тоесть если A возьмет 1 спичку, B возьмет 3 спички. Если A возьмет 2 спички, B тоже возьмет 2 спички. И наконец если A возьмет 3 спички, B возьмет оставшуюся спичку и при любом раскладе выиграет.
Как сделать так, чтобы у противника (игрока A) осталось 4 спички? Если перед игроком A находятся 8 спичек:
| | | | | | | |
то игрок B в любом случае сможет сделать так чтобы у игрока A осталось 4 спички. Логика налогичная, что и в случае игры с 4 спичками. В ответ на ход игрока A игрок B берет столько спичек, чтобы в итоге на столе осталось бы 4 спички.
Общий принцип таков:
- игрок в проигрышном, если остаток от деления N на (M + 1) равен 0. Это значит, что если поделить количество спичек на столе на (M + 1) и взять остаток от деления (остаток от деления 5 / 3 равен 2), то игрок в проигрышном положении, если остаток равен 0.
- в любом случае игрок находится в выигрышном положении и он может высчитать свой выигрышный ход основываясь на том же принципе: выигрышный ход (количество спичек, которые нужно взять со стола) = остаток от деления N на (M + 1).
Основная часть (5 баллов)
Реализовать игру "спички" с фиксированными параметрами N = 10 и M = 3. Тоесть в начале игры на столе 10 спичек, за один ход каждый игрок может взять 1, 2, либо 3 спички. В этой игре человек играет против программы.
Требования к программе:
- Первым ход делает игрок (человек).
- Когда наступила очередь ходить игроку, у него спрашивают сколько спичек он возьмет со стола. Значение вводится с клавиатуры.
- Корректность пользовательского ввода следует проверять. Это означает, например, проверку введенного значения на принадлежность интервалу "разрешенных" значений.
- В случае неверного ввода, тот же вопрос задается снова.
- В случае корректного ввода, программа делает ход.
- Программа берет со стола случайное количество спичек (которые не нарушают правил игры), кроме случаев в которых программа может выиграть в один ход (тоесть на столе 3 или меньшее количество спичек).
- После того как программа сделала свой ход снова наступает очередь игрока сделать свой ход.
- Таким образом ходы делаются по очереди, пока кто-нибудь не выиграет.
- В конце каждого хода программа выводит на экран количество спичек, которые остались на столе.
Дополнительные требования:
- При написании программы следует использовать шаблон, приведенный ниже. Это необходимо для того, чтобы ваше решение можно было бы протестировать.
- В коде должны присутствовать осмысленные коментарии.
- Код должен соответствовать требованиям Checkstyle.
Шаблон GameOfSticks.java:
<source lang="java">
public class GameOfSticks {
public static void main(String[] args) {
}
public static int getComputerMove(int sticksOnBoard) { return -1; } }
</source>
Дополнительное задание: динамические параметры (2 балла)
В начале игры пользователь может задать сколько спичек на столе (N) и сколько спичек максимально можно брать за один ход (M).
Требования (в дополнение к требованиям к основной части задания):
- В начале игры пользователя просят ввести значения M и N.
- Ограничения по вводимым параметрам: 8 <= N < 40, 2 <= M < N/2
Дополнительное задание: выиграшный ход (1 балл)
В случае выигрышного положения программа должна делать оптимальный ход. См. описание выше #Выигрышная стратегия в игре.
Если реализована только основная часть, за решение этого дополнительного задания можно получить 1 балл. Если реализовано дополнительное задание "динамические параметры", то за решение этого дополнительного задание можно получить 2 балла.
Дополнительное задание: обучение выигрышному ходу (3 балла)
Программа учится на опыте предудыщих игр как нужно играть чтобы выиграть. Это задание отменяет предыдущее дополнительное задание "выигрышный ход" (выбрать можно лишь одно).
Одна из возможностей для реализации в игре искуственного интеллекта (AI) - проанализировать ход игры и по нему высчитать формулу, которая позволит игроку (или программе) ходить самым оптимальным образом и выиграть игру. В этом дополнительном задании нужно все сделать в точности наоборот. Следует создать искуственный интеллект, который анализирует более ранние игры и основываясь на результатах этих игр составляет стратегию игры в последующих играх.
Примеры ниже относятся к игре с параметрами N = 10 и M = 3 (тоесть на столе в начале лежат 10 спичек и каждый игрок за раз может взять от 1 до 3 спичек). Если выполнено дополнительное задание, в котором параметры N и M могут меняться, то достаточно того, что история игр сохраняется до тех пор, пока параметры M и N остаются неизменными. Если они поменялись, то историю прошедгих игр следует удалить и начать записывать историю заново. Можно сделать так, что в начале игры игрока просят ввести значения параметров M и N, после чего их менять нельзя.
Пример искуственного интеллекта в игре:
- Представим, что у искуственного интеллекта на каждую спичку, находящуюся на столе, имеется ящик, в котором находятся поначалу 3 (в случае M=3) пронумерованных (1..3) фишек.
- При каждом ходе компьютера он берет из соответствующего ящика фишку случайным образом и "размещает" ее возле ящика. После чего компьютер берет такое количество спичек, которое написано на выбранной фишке.
- Если играя подобным образом компьютер выиграл, то он кладет в каждый ящик две одинаковых фишки (на обоих фишках написано то же число), как та, что была взята из данного ящика. Если компьютер проиграл kaotab, то фишка, находящаяся рядом с ящиком выбрасывается, если в ящике присутствует фишка под таким же номером (в ящике всегда должна быть по крайней мере одна фишка под кажым номером из промежутка 1 - 3 (точнее говоря 1 - M)).
- Чем больше игр сыграно, тем больше фишек, соответствующих "верному ходу" соберется в ящике, и когда в следующей игре компьютер будет выбирать случайную фишку из ящика, вероятность того, что он выберет "хорошую" фишку (вероятность того, что он сделает оптимальный ход) повышается с каждой выигранной игрой.
Пример:
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.
Etteantud mall GameOfSticks.java testimaks AI õppimise funktsionaalsust: <source lang="java"> /**
* (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) { }
/** * 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. * @param sticksOnBoard The number of sticks on the board. * @return Sticks to remove from the board in the given state. */ public static int getComputerMove(int sticksOnBoard) { return -1; }
/** * In case of AI bonus task, 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. If this method returns 0 (game is over), * the coefficients for different states should be modified accordingly. * @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. * @param n The number of sticks initially on the board. */ public static void setNumberOfSticksOnBoard(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. * @param m The number of sticks a player can take during its turn. */ public static void setMaxNumberOfSticksToTake(int m) { // TODO: your code }
/** * In case of AI bonus task, 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. * @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>