ITI0011RUS:Matches - Redigeerimiste ajalugu

Aleksandr: /* Дополнительное задание: обучение выигрышному ходу (3 балла) */

2015-02-22T14:11:51Z

Дополнительное задание: обучение выигрышному ходу (3 балла)

Aleksandr – 22. veebruar 2015, kell 09:51

2015-02-22T09:51:49Z

Aleksandr: /* Дополнительное задание: выиграшный ход (1 балл) */

2015-02-15T11:19:07Z

Дополнительное задание: выиграшный ход (1 балл)

Aleksandr: /* Дополнительное задание: обучение выигрышному ходу (3 балла) */

2015-02-13T20:48:17Z

Дополнительное задание: обучение выигрышному ходу (3 балла)

Aleksandr: /* Дополнительное задание: обучение выигрышному ходу (3 балла) */

2015-02-13T20:39:01Z

Дополнительное задание: обучение выигрышному ходу (3 балла)

Aleksandr: /* Дополнительное задание: обучение выигрышному ходу (3 балла) */

2015-02-13T20:16:00Z

Дополнительное задание: обучение выигрышному ходу (3 балла)

Aleksandr: /* Дополнительное задание: обучение выигрышному ходу (3 балла) */

2015-02-13T20:01:14Z

Дополнительное задание: обучение выигрышному ходу (3 балла)

Näita muudatusi

Aleksandr – 6. veebruar 2015, kell 21:08

2015-02-06T21:08:16Z

Aleksandr: Uus lehekülg: 'Вернуться на страницу предмета
Рабочая версия! Окончательная версия появ...'

2015-02-06T21:07:00Z

Uus lehekülg: 'Вернуться на страницу предмета <div style="color: #f00;">Рабочая версия! Окончательная версия появ...'

Uus lehekülg

Вернуться на [[ITI0011RUS|страницу предмета]]

<div style="color: #f00;">Рабочая версия! Окончательная версия появится на 2 неделе.</div>

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

На столе в начале игры N спичек. За один ход игроку можно взять со стола от 1 до M спичек (1 < M < N). Это означает, что на каждом ходу игрок обязан взять хотя бы одну спичку. Таким образом делая ходы по очереди игра продолжается до тех пор пока на столе не останется спичек. Игрок, взявщий спичку(и) последним, выиграл.

Значения M и N устанавливаются непосредственно перед началом игры и в процессе игры остаются неизменными.

== Пример ==

Рассмотрим пример, где N = 10 и M = 3.

На столе 10 спичек:

<pre>
| | | | | | | | | |
</pre>

Двое игроков берут по очереди спички со стола. Каждый из игроков может взять одну, две, или три спички. Не взять ни одной нельзя, также как и взять более трех спичек.

Выигрывает тот игрок, который брал спички со стола последним.

Игра, например, может проходить так:

* Игрок A взял 2 спички, на столе осталось 8 спичек.
* Игрок B взял 3 спички, на столе осталось 5 спичек.
* Игрок A взял 1 спичку, на столе осталось 4 спички.
* Игрок B взял 1 спичку, на столе осталось 3 спички.
* Игрок A взял 3 спички, на столе больше спичек не осталось, и потому игрок A выиграл.

== Выигрышная стратегия в игре ==

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

К счастью, существует гораздо более простой способ выиграть в этой игре. Для того чтобы выиграть не нужно просчитывать свои ходы и ходы противника на несколько ходов вперед.

Рассмотрим пример игры, где N = 10 и M = 3. Рассмотрим возможные ходы с конца игры. Когда перед игроком A лежат 4 спички:
<pre>
| | | |
</pre>
то сколько бы спичек игрок A не брал, всегда выиграет игрок B (предполагая, что стратегия игрока B оптимальна). Тоесть если A возьмет 1 спичку, B возьмет 3 спички. Если A возьмет 2 спички, B тоже возьмет 2 спички. И наконец если A возьмет 3 спички, B возьмет оставшуюся спичку и при любом раскладе выиграет.

Как сделать так, чтобы у противника (игрока A) осталось 4 спички? Если перед игроком A находятся 8 спичек:
<pre>
| | | | | | | |
</pre>
то игрок 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 балла) ==

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

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

@@ 247. rida: / 247. rida: @@
 Выводимые программой на экран строки не обязательно должны быть такими же - это всего лишь пример!
 Для решения задания вам предоставляется шаблон '''GameOfSticks.java''':
 <source lang="java">
 /**
   * (Bigger) homework 01 - Game of sticks.
@@ 262. rida: / 268. rida: @@
 	 */
 	public static void main(String[] args) {
+	}
@@ 267. rida: / 291. rida: @@
 	 * 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!
+	 * The move itself should <strong>NOT</strong> 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) {
+	public static int getComputerMove() {
 		return -1;
+	}
 	/**
-	 * In case of AI bonus task, makes the AI move
+	 * Makes the AI move
-	 * and returns the number of sticks on the board after the 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),
+	 * to store the move. So, if there are 10 sticks on the board and
-	 * the coefficients for different states should be modified accordingly.
+	 * AI takes 3, this method should return 7.
 	 * @return The number of sticks after the AI move.
 	 */
@@ 294. rida: / 326. rida: @@
 	 * 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) {
+	public static void setInitialNumberOfSticksOnBoard(int n) {
 		// TODO: your code
+	}
@@ 304. rida: / 337. rida: @@
 	 * 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.
 	 */
@@ 311. rida: / 345. rida: @@
 	/**
-	 * In case of AI bonus task, this method should accept
+	 * 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.
@@ 326. rida: / 362. rida: @@
+	}
+}
 </source>

←Vanem redaktsioon		Redaktsioon: 22. veebruar 2015, kell 09:51
1. rida:		1. rida:
	Вернуться на [[ITI0011RUS\|страницу предмета]]		Вернуться на [[ITI0011RUS\|страницу предмета]]
−
−	~~<div style="color: #f00;">Рабочая версия! Окончательная версия появится на 2 неделе.</div>~~

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

←Vanem redaktsioon		Redaktsioon: 15. veebruar 2015, kell 11:19
100. rida:		100. rida:


−	== Дополнительное задание: ~~выиграшный~~ ход (1 балл) ==	+	== Дополнительное задание: выигрышный ход (1 балл) ==

	В случае выигрышного положения программа должна делать оптимальный ход. См. описание выше [[#Выигрышная стратегия в игре]].		В случае выигрышного положения программа должна делать оптимальный ход. См. описание выше [[#Выигрышная стратегия в игре]].

@@ 165. rida: / 165. rida: @@
 Задача состоит в написании ИИ, который обновляет содержимое мешков после каждой игры. Поначалу ИИ делает случайные ходы, но с каждой следующей игрой он начинает делать более осмысленные ходы.
-Järgnev näide demonstreerib kuidas programm peaks käituma:
+Следующий пример демонстрирует пример игры:
 <pre>
-Sisesta tikkude arv mängu alguses: 10
+Enter the initial amount of matches on the table: 10
-Sisesta võimalik võetavate tikkude kogus ühel käigul: 3
+Enter the maximal amount of matches to take at once: 3
-. mäng:
+matches on the table, you pay pick up to 3 matches.
-tikku laual ja korraga saab võtta kuni 3 tikku.
 | | | | | | | | | | (10)
-Mängija võtab 3
+Player takes 3
 | | | | | | |       (7)
-Arvuti võtab 2
 | | | | |           (5)
-Mängija võtab 3
 | | |               (3)
-Arvuti võtab 2
 |                   (1)
-Mängija võitis!
+Player takes 1
-Kas mängid veel (jah/ei)? jah
-.Mäng:
+. game:
 | | | | | | | | | | (10)
-Mängija võtab 1
+Player takes 1
 | | | | | | | | |   (9)
-Arvuti võtab 1
 | | | | | | | |     (8)
-Mängija võtab 3
 | | | | |           (5)
-Arvuti võtab 3
 | |                 (2)
-Mängija võitis!
+Player takes 2
-Kas mängid veel (jah/ei)? jah
-.Mäng:
+. game:
 | | | | | | | | | | (10)
-Mängija võtab 3
+Player takes 3
 | | | | | | |       (7)
-Arvuti võtab 2
 | | | | |           (5)
-Mängija võtab 3
 | |                 (2)
-Arvuti võitis!
+AI takes 2
-Kas mängid veel (jah/ei)? ei
 </pre>
-Näidatud väljund ei pea täpselt selline olema. See on lihtsalt üks näide.
+Выводимые программой на экран строки не обязательно должны быть такими же - это всего лишь пример!
-Etteantud mall '''GameOfSticks.java''' testimaks AI õppimise funktsionaalsust:
+Для решения задания вам предоставляется шаблон '''GameOfSticks.java''':
 <source lang="java">
 /**

@@ 116. rida: / 116. rida: @@
 Пример искуственного интеллекта в игре:
-* Представим, что у искуственного интеллекта на каждую спичку, находящуюся на столе, имеется ящик, в котором находятся поначалу 3 (в случае M=3) пронумерованных (1..3) фишек.
+* Представим, что у искуственного интеллекта на каждую спичку, находящуюся на столе, имеется мешок, в котором находятся поначалу 3 (в случае M=3) пронумерованных (1..3) фишки.
-* При каждом ходе компьютера он берет из соответствующего ящика фишку случайным образом и "размещает" ее возле ящика. После чего компьютер берет такое количество спичек, которое написано на выбранной фишке.
+* При каждом ходе компьютера он берет из соответствующего мешка фишку случайным образом и "размещает" ее возле мешка. После чего компьютер берет такое количество спичек, которое написано на выбранной фишке.
-* Если играя подобным образом компьютер выиграл, то он кладет в каждый ящик две одинаковых фишки (на обоих фишках написано то же число), как та, что была взята из данного ящика. Если компьютер проиграл kaotab, то фишка, находящаяся рядом с ящиком выбрасывается, если в ящике присутствует фишка под таким же номером (в ящике всегда должна быть по крайней мере одна фишка под кажым номером из промежутка 1 - 3 (точнее говоря 1 - M)).
+* Если играя подобным образом компьютер выиграл, то он кладет в мешок две одинаковых фишки (на обоих фишках написано то же число), как та, что была взята из данного мешка. Если компьютер проиграл, то фишка, находящаяся рядом с мешком выбрасывается, если в мешке присутствует фишка под таким же номером (в мешке всегда должна быть по крайней мере одна фишка под кажым номером из промежутка 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:
+Рассмотрим случай, в котором в начале игры на столе лежат 10 спичек и за раз можно взять до 3 спичек со стола. Содержимое мешков следующее:
 <pre>
-kott	1	2	3	4	5	6	7	8	9	10
+мешок	        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
+содержимое	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
 </pre>
-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.
+Активным является тот мешок, номер которого соответствует количеству спичек на столе. В начале игры активным является самый последний мешок под номером 10. Если на столе 5 спичек, то, соответственно, активным является мешок под номером 5, и т.д.
-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).
+Содержимое мешка соответствует, фишкам, присутствующим в мешке, и соответстующим номерам на них. В начале игры в каждом мешке фишки с номерами 1, 2, 3. Это означает, что в этом состоянии выбор одной, двух, или трех спичек равнозначен (одинаково хорош). На самом деле это не так, но в начале игры "необученный" искуственный интеллект достаточно глупый и не может делать предпочтения между ходами.
-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.
+Если прочесть задание внимательно и немного подумать, то в случае данной игры в мешке "1" должна находиться фишка "1". В мешке "2" фишки "1" и "2". Выбор прочих фишек привел бы к ходу, который нарушил бы правила игры. Если на столе 1 спичка, со стола нельзя взять больше, чем одну спичку, и т.д.
-Vaatame mängu, mis kulgeb järgmiselt:
+Рассмотрим игру, которая проходит следующим образом:
-* mängija võtab 2 tikku, alles jääb 8 tikku
+* игрок берет 2 спички, на столе остается 8 спичек.
-* 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.
+* ИИ случайным образом выбирает фишку с номером "2" из мешка под номером 8 (поскольку на тот момент на столе было 8 спичек). Таким образом, ИИ берет 2 спички со стола, остается 6 спичек.
-* mängija võtab 1 tiku, järele jääb 5 tikku.
+* игрок берет 1 спичку, на столе остается 5 спичек.
-* AI valib suvaliselt kuuli "1" kotist number 5, st võtab 1 tiku laualt, 4 tikku jääb järele.
+* ИИ случайным образом выбирает фишку с номером "1" из мешка под номером 5, после чего берет 1 спичку со стола, на столе остается 4 спички.
-* mängija võtab 2 tikku, 2 jääb järele.
+* Игрок берет 2 спички, и 2 спички остаются на столе.
-* AI valib suvaliselt kuuli "2" kotist number 2. Lauale ei jää ühtegi tikku, arvuti võidab.
+* ИИ случайным образом выбирает фишку с номером "2" из мешка под номером 2. На столе больше не остается спичек, таким образом ИИ выиграл.
-Nüüd on AI olukord selline:
+Теперь содержимое мешков следующее:
 <pre>
-kott	1	2	3	4	5	6	7	8	9	10
+мешок	        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
+содержимое	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
+случайный выбор		2			1			2
 </pre>
-Kuna AI võitis, siis paneb ta valitud kuulid kotti tagasi ning lisab uued samade väärtustega kuulid:
+Поскольку ИИ выиграл, возвращает он выбранные случайным образом фишки обратно в мешки и добавляет фишки с такими же номерами:
 <pre>
-kott	1	2	3	4	5	6	7	8	9	10
+мешок	        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
+содержимое	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
 </pre>
-Nüüd on AI-l suurem võimalus võtta:
+Теперь у ИИ выше вероятность взять:
-* 2 tikku, kui laual on 8 tikku
+* 2 спички, если на столе 8 спичек
-* 1 tikk, kui laual on 5 tikku
+* 1 спичку, если на столе 5 спичек
-* 2 tikku, kui laual on 2 tikku
+* 2 спички, если на столе 2 спички
-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.
+В случае, если ИИ проиграл, то он выбрасывает выбранные фишки в случае, если в мешке осталась по крайней мере одна фишка с тем же номером, что и та, которая была выбрана случайным образом. Тоесть если вначале в мешке были, например, фишки 1, 2, 2, 2, 3. ИИ случайным обрмзом выбрал фишку под номером "2", в мешке остаются фишки 1, 2, 2, 3. Если ИИ проиграл, то выбранная фишка удаляется и в мешке остаются фишки 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:

@@ 108. rida: / 108. rida: @@
 == Дополнительное задание: обучение выигрышному ходу (3 балла) ==
-Программа учится на прошедших играх как нужно играть чтобы выиграть. Это задание отменяет предыдущее дополнительное задание "выигрышный ход" (выбрать можно лишь одно).
+Программа учится на опыте предудыщих игр как нужно играть чтобы выиграть. Это задание отменяет предыдущее дополнительное задание "выигрышный ход" (выбрать можно лишь одно).
 Более детальное описание задания появится в ближайшее время.

ITI0011RUS:Matches - Redigeerimiste ajalugu

Aleksandr: /* Дополнительное задание: обучение выигрышному ходу (3 балла) */

Aleksandr – 22. veebruar 2015, kell 09:51

Aleksandr: /* Дополнительное задание: выиграшный ход (1 балл) */

Aleksandr: /* Дополнительное задание: обучение выигрышному ходу (3 балла) */

Aleksandr: /* Дополнительное задание: обучение выигрышному ходу (3 балла) */

Aleksandr: /* Дополнительное задание: обучение выигрышному ходу (3 балла) */

Aleksandr: /* Дополнительное задание: обучение выигрышному ходу (3 балла) */

Aleksandr – 6. veebruar 2015, kell 21:08

Aleksandr: Uus lehekülg: 'Вернуться на страницу предмета Рабочая версия! Окончательная версия появ...'

Aleksandr: Uus lehekülg: 'Вернуться на страницу предмета
Рабочая версия! Окончательная версия появ...'