- Правила гри [ правити | правити код ]
- аналіз [ правити | правити код ]
- За хрестики [ правити | правити код ]
- За нулики [ правити | правити код ]
- Дерево ігрових ситуацій [ правити | правити код ]
- Комп'ютерне рішення [ правити | правити код ]
- Довші лінії [ правити | правити код ]
- Модифікація поля [ правити | правити код ]
- Обмін значків [ правити | правити код ]
- Зміна умови виграшу [ правити | правити код ]
- Подовження ходу [ правити | правити код ]
Хрестики нолики [1] - логічна гра між двома противниками на квадратному полі 3 на 3 клітини або більшого розміру (аж до «нескінченного поля»). Один з гравців грає «хрестиками», другий - «нуликами». У традиційній китайській грі ( Гомокі ) Використовуються чорні і білі камені.
Правила гри [ правити | правити код ]
Гравці по черзі ставлять на вільні клітини поля 3х3 знаки (один завжди хрестики, інший завжди нулики). Перший, який вибудував у ряд 3 своїх фігури по вертикалі, горизонталі або діагоналі, виграє. Перший хід робить гравець, що ставить хрестики.
Зазвичай після закінчення партії виграла, закреслює рисою свої три знака (нулика або хрестика), що становлять суцільний ряд.
аналіз [ правити | правити код ]
Для кожної зі сторін загальновідомі алгоритми, які гарантують нічию при будь-якій грі противника, а при його помилку дозволяють виграти. Таким чином, гра знаходиться в стані «Нічийної смерті» .
Нижче наведені деякі з таких стратегій. Вважається, що гравець завжди дотримується два правила, які мають пріоритет над усіма іншими:
- Правило 1. Якщо гравець може негайно виграти, він це робить.
- Правило 2. Якщо гравець не може негайно виграти, але його противник міг би негайно виграти, зробивши хід в якусь клітку, гравець сам робить хід у цю клітку, запобігаючи негайний програш.
За хрестики [ правити | правити код ]
Перший хід зробити в центр. Решта ходи, якщо не застосовуються правила 1-2, робляться в той з вільних кутів, який найдалі від попереднього ходу налякав, а якщо і це неможливо - в будь-яку клітину.
Х
Доведемо, що ця стратегія призводить до перемоги або нічиєї. Якщо нулик піде на сторону, то позиція (з точністю до симетрії) виявиться така:
Про Х Х
Після чого правила 1 і 2 приведуть до позиції:
Х О О Х Х
Виграш.
Якщо ж нулик піде в кут, позиція (з точністю до симетрії) буде наступна:
Про Х Х
Залежно від наступного ходу нулика, виникне одна з трьох позицій:
Про Про Х Х Х Про Х Про Х Х Про Х Про Х Х
У першій і третій позиції - виграш. У другій - нічия.
За нулики [ правити | правити код ]
Вcпомінаем, що правила 1-2, якщо вони можуть бути застосовані, мають пріоритет над усім, написаним нижче.
- Якщо хрестики зробили перший хід у центр, до кінця гри ходити в будь-який кут, а якщо це неможливо - в будь-яку клітину.
Про Х
- Якщо хрестики зробили перший хід у кут, відповісти ходом в центр.
Х Про
- Наступним ходом зайняти кут, протилежний першому ходу хрестиків, а якщо це неможливо - піти на сторону.
ХО ХО
- Якщо хрестики зробили перший хід на сторону, відповісти ходом в центр.
- Якщо наступний хід хрестиків - в кут, зайняти протилежний кут:
Х О О Х
- Якщо наступний хід хрестиків - на протилежну сторону, піти в будь-який кут:
ОХ ОХ
- Якщо наступний хід хрестиків - на сторону поруч з їх першим ходом, піти в кут поруч з обома хрестиками
Про Х Х Про
Дерево ігрових ситуацій [ правити | правити код ]
Дерево ігрових ситуацій для гри хрестики-нулики, де гравець за «хрестики» ходить першим і надходить за наведеним вище алгоритмом, а гравець за «нулики» може надходити як завгодно (причому наведено по одній вершині для раціонального і для нераціонального вчинку, тобто будь-якого іншого), складається з 50-ти вузлів.
Комп'ютерне рішення [ правити | правити код ]
Для вирішення такого роду ігор на комп'ютері будується дерево ігрових ситуацій відповідно до методу міні-макс . Повне число вузлів в такому дереві одно 255168. Це число виходить як сума всіх можливих варіантів ходів - 9 варіантів на першому кроці, 8 - для кожного з 9 на другому кроці, 7 - на кожному з 72 варіантів на третьому кроці і т. Д. , за вирахуванням ситуацій дострокового закінчення гри (виграшу).
Довші лінії [ правити | правити код ]
Можна розглядати гру, в якій переможцем вважається гравець, першим побудував n ⩾ 3 {\ displaystyle n \ geqslant 3} 
Гра до 4 однакових знаків на нескінченному полі нецікава, бо початківець досить швидко будує «вилку» і виграє. Гра при n ⩾ 6 {\ displaystyle n \ geqslant 6} 
основний переможної тактикою при грі на нескінченному полі вважається побудова перетинів ( «вилок»), які не дають противнику можливості блокувати всі можливі шляхи побудови п'ятірки. Щоб не програти, необхідно своєчасно переривати лінії противника довжиною в три фігури і більше.
Практика показала, що при рівних правилах для гравців той, хто робить перший хід, має перевагу, що дозволяє при досить кваліфікованої грі здобути перемогу, що згодом було доведено строго [2] [3] . Для збереження інтересу до гри пропонувалися різні варіанти модифікації правил гри. Так, з введенням фолів (Заборонених ходів) для гравця, що починає першим - йому заборонено будувати вилки 3 × 3, 4 × 4, а також вибудовувати «довгий ряд» зі своїх фігур - вийшла нова гра під назвою рендзю , З великою різноманітністю стратегій гри і рівними шансами гравців.
Модифікація поля [ правити | правити код ]
Збільшення розміру поля вже обговорювалося вище. Найпростішим, але збільшує тактичне багатство гри, є додавання однієї клітини уздовж однієї зі сторін поля 3х3.
Іншим варіантом є зміна топології поля. Наприклад, можна вважати протилежні сторони поля склеєними, утворюючи при цьому яку поверхню циліндра або тора , або проективну площину . Також можна збільшувати розмірність, наприклад, грати в кубі 4x4x4, в гиперкубе і так далі.
Обмін значків [ правити | правити код ]
Можна скасувати правило, яке вказує гравцям ставити тільки свій вид значків.
Наприклад, варіантом гри може бути: гравці ставлять хрестик або нулик (що захочуть); перший виграє, якщо побудує лінію потрібної довжини з однакових значків, другий - якщо до заповнення поля цього не відбудеться.
Інший варіант: «свій» значок змінюється з кожним ходом.
Зміна умови виграшу [ правити | правити код ]
Замість того, щоб закінчувати гру побудовою першої лінії потрібної довжини, можна на цьому не зупинятися і продовжити до повного заповнення поля. Наприклад, на будь-якому полі можна грати на те, хто більше побудує «четвірок» зі своїх знаків.
Також існує варіант хрестиків-нуликів Сілвермена . У ньому використовується ігрове поле 4х4 клітини. Хрестики виграють, якщо виникає ряд з 4-х однакових значків (хрестиків або нуликів), інакше виграють нулики.
Подовження ходу [ правити | правити код ]
Ще один варіант модифікації гри - виставляти на кожному ході не один свій знак, а два або більше. така гра Connect6 , В якій чорні роблять перший хід, виставляючи один знак, після чого гравці по черзі виставляють по два знака, перемагає перший, який побудував лінію з 6 або більше своїх знаків.
- ↑ У XIX столітті, поряд з назвою «хрестики-нулики» (див. Н. А. Лейкін , «Навчальний день в німецькій школі», 1871), також використовувалися «Херіка-Оніка» або «Херіка» - за старою назвою букв російського алфавіту «Х» - «хер» і «О» - «воно» ( «Хер» в словнику Даля архівна копія від 14 червня 2011 року на Wayback Machine ), «Нулики» ( Н. П. Гіляров-Платонов , «З пережитого», 1886
- ↑ Allis, LV (1994). Searching for solutions in games and artificial intelligence, Ph.D. Thesis, University of Limburg, Maastricht.
- ↑ Allis, LV, Herik, HJ van den, and Huntjens, MPH (1996). Go-Moku Solved by New Search Techniques. Computational Intelligence, Vol. 12.