ITI0011RUS:Matches

Рабочая версия! Окончательная версия появится на 2 неделе.

Игра "спички" - это игра в которой два игрока по очереди берут спички со стола. Игрок взявщий последнюю спичку выигрывает.

На столе в начале игры 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:

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 балла)

Программа учится на прошедших играх как нужно играть чтобы выиграть. Это задание отменяет предыдущее дополнительное задание "выигрышный ход" (выбрать можно лишь одно).

Более детальное описание задания появится в ближайшее время.