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) фишки.
- При каждом ходе компьютера он берет из соответствующего мешка фишку случайным образом и "размещает" ее возле мешка. После чего компьютер берет такое количество спичек, которое написано на выбранной фишке.
- Если играя подобным образом компьютер выиграл, то он кладет в мешок две одинаковых фишки (на обоих фишках написано то же число), как та, что была взята из данного мешка. Если компьютер проиграл, то фишка, находящаяся рядом с мешком выбрасывается, если в мешке присутствует фишка под таким же номером (в мешке всегда должна быть по крайней мере одна фишка под кажым номером из промежутка 1 - 3 (точнее говоря 1 - M)).
- Чем больше игр сыграно, тем больше фишек, соответствующих "верному ходу" соберется в мешке, и когда в следующей игре компьютер будет выбирать случайную фишку из мешка, вероятность того, что он выберет "хорошую" фишку (вероятность того, что он сделает оптимальный ход) повышается с каждой выигранной игрой.
Пример:
Рассмотрим случай, в котором в начале игры на столе лежат 10 спичек и за раз можно взять до 3 спичек со стола. Содержимое мешков следующее:
мешок 1 2 3 4 5 6 7 8 9 10 содержимое 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
Активным является тот мешок, номер которого соответствует количеству спичек на столе. В начале игры активным является самый последний мешок под номером 10. Если на столе 5 спичек, то, соответственно, активным является мешок под номером 5, и т.д.
Содержимое мешка соответствует, фишкам, присутствующим в мешке, и соответстующим номерам на них. В начале игры в каждом мешке фишки с номерами 1, 2, 3. Это означает, что в этом состоянии выбор одной, двух, или трех спичек равнозначен (одинаково хорош). На самом деле это не так, но в начале игры "необученный" искуственный интеллект достаточно глупый и не может делать предпочтения между ходами.
Если прочесть задание внимательно и немного подумать, то в случае данной игры в мешке "1" должна находиться фишка "1". В мешке "2" фишки "1" и "2". Выбор прочих фишек привел бы к ходу, который нарушил бы правила игры. Если на столе 1 спичка, со стола нельзя взять больше, чем одну спичку, и т.д.
Рассмотрим игру, которая проходит следующим образом:
- игрок берет 2 спички, на столе остается 8 спичек.
- ИИ случайным образом выбирает фишку с номером "2" из мешка под номером 8 (поскольку на тот момент на столе было 8 спичек). Таким образом, ИИ берет 2 спички со стола, остается 6 спичек.
- игрок берет 1 спичку, на столе остается 5 спичек.
- ИИ случайным образом выбирает фишку с номером "1" из мешка под номером 5, после чего берет 1 спичку со стола, на столе остается 4 спички.
- Игрок берет 2 спички, и 2 спички остаются на столе.
- ИИ случайным образом выбирает фишку с номером "2" из мешка под номером 2. На столе больше не остается спичек, таким образом ИИ выиграл.
Теперь содержимое мешков следующее:
мешок 1 2 3 4 5 6 7 8 9 10 содержимое 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 случайный выбор 2 1 2
Поскольку ИИ выиграл, возвращает он выбранные случайным образом фишки обратно в мешки и добавляет фишки с такими же номерами:
мешок 1 2 3 4 5 6 7 8 9 10 содержимое 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
Теперь у ИИ выше вероятность взять:
- 2 спички, если на столе 8 спичек
- 1 спичку, если на столе 5 спичек
- 2 спички, если на столе 2 спички
В случае, если ИИ проиграл, то он выбрасывает выбранные фишки в случае, если в мешке осталась по крайней мере одна фишка с тем же номером, что и та, которая была выбрана случайным образом. Тоесть если вначале в мешке были, например, фишки 1, 2, 2, 2, 3. ИИ случайным обрмзом выбрал фишку под номером "2", в мешке остаются фишки 1, 2, 2, 3. Если ИИ проиграл, то выбранная фишка удаляется и в мешке остаются фишки 1, 2, 2, 3.
Задача состоит в написании ИИ, который обновляет содержимое мешков после каждой игры. Поначалу ИИ делает случайные ходы, но с каждой следующей игрой он начинает делать более осмысленные ходы.
Следующий пример демонстрирует пример игры:
Enter the initial amount of matches on the table: 10 Enter the maximal amount of matches to take at once: 3 10 matches on the table, you pay pick up to 3 matches. 1. game: | | | | | | | | | | (10) Player takes 3 | | | | | | | (7) AI takes 2 | | | | | (5) Player takes 3 | | | (3) AI takes 2 | (1) Player takes 1 Player has won! Continue (yes/no)? Yes 2. game: | | | | | | | | | | (10) Player takes 1 | | | | | | | | | (9) AI takes 1 | | | | | | | | (8) Playet takes 3 | | | | | (5) AI takes 3 | | (2) Player takes 2 Player has won! Continue (yes/no)? y Continue (yes/no)? yes 3. game: | | | | | | | | | | (10) Player takes 3 | | | | | | | (7) AI takes 2 | | | | | (5) Player takes 3 | | (2) AI takes 2 AI has won! Continue (yes/no)? no
Выводимые программой на экран строки не обязательно должны быть такими же - это всего лишь пример!
Шаблон
Для решения задания вам предоставляется шаблон 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>