Крестики-нолики - Tic-tac-toe

Крестики-нолики

Завершенная игра в крестики-нолики
Другие имена
Жанры	Игра с бумагой и карандашом
Игроки	2
Время установки	Минимальный
Время игры	~ 1 минута
Случайный шанс	Никто
Требуются навыки	Стратегия , тактика, наблюдение

Крестики-нолики ( американский английский ), крестики-нолики ( Commonwealth английский ), или Xs и Os ( ирландский английский ) является целлюлозно-карандаш игра для двух игроков , которые по очереди маркировка пространства в три-на-три сетка с X или O . Игрок, которому удастся разместить три своих знака в горизонтальном, вертикальном или диагональном ряду, становится победителем. Это решенная игра с принудительной ничьей при условии лучшей игры обоих игроков.

Геймплей

В крестики-нолики играют на сетке три на три двумя игроками, которые поочередно помещают метки X и O в одно из девяти мест в сетке.

В следующем примере первый игрок ( X ) выигрывает игру за семь шагов:

Не существует общепринятого правила относительно того, кто играет первым, но в этой статье используется соглашение, согласно которому X играет первым.

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

Из-за простоты крестики-нолики его часто используют в качестве педагогического инструмента для обучения концепциям хорошего спортивного мастерства и той области искусственного интеллекта, которая занимается поиском деревьев игр . Несложно написать компьютерную программу для идеальной игры в крестики-нолики или для перечисления 765 существенно различных позиций ( сложность пространства состояний ) или 26 830 возможных игр вплоть до вращений и отражений ( сложность игрового дерева ) в этом пространстве. Если оба игрока играют оптимально, игра всегда заканчивается вничью, что делает игру в крестики-нолики бесполезной .

Структура заболеваемости крестиками-ноликами

Игру можно обобщить до m , n , k -игры , в которой два игрока поочередно кладут камни своего цвета на доску размером m на n с целью получить подряд k своего цвета. Крестики-нолики - это 3,3,3-игра. Обобщенные крестики-нолики Харари - еще более широкое обобщение крестиков-ноликов. Его также можно обобщить как игру n ^d , в частности игру , в которой n равно 3, а d равно 2. Ее можно обобщить еще больше, играя на произвольной структуре инцидентности , где строки - это линии, а клетки - точки . Структура падения крестиков-ноликов состоит из девяти точек, трех горизонтальных линий, трех вертикальных линий и двух диагональных линий, каждая из которых состоит как минимум из трех точек.

История

Игры, в которые играют на досках «три в ряд», восходят к Древнему Египту , где такие игровые доски были обнаружены на кровельной черепице примерно 1300 г. до н.э.

Ранняя вариация в крестики-нолики игралась в Римской империи примерно в первом веке до нашей эры. Это называлось terni lapilli ( три камешка одновременно ), и вместо того, чтобы иметь какое-либо количество штук, у каждого игрока было только три; таким образом, им приходилось перемещать их в пустые места, чтобы продолжить игру. Маркировка сетки игры была найдена мелом по всему Риму. Другая тесно связанная древняя игра - это моррис с тремя мужчинами, в который также играют на простой сетке и для завершения требуется три фишки подряд, и Picaria , игра пуэблоанцев .

Различные названия игры появились позже. Первая печатная ссылка на «крестики-нолики» (« ноль» - альтернативное слово «ноль»), британское название, появилась в 1858 году в выпуске Notes and Queries . Первое печатное упоминание об игре под названием «тик-нолик» произошло в 1884 году, но это была «детская игра на грифельной доске, состоящая в попытке с закрытыми глазами опустить карандаш на одно из чисел знака. set, количество попаданий оценивается ". «Крестики-нолики» также могут происходить от «тик-нолика», названия старой версии нардов, впервые описанной в 1558 году. В США переименование «крестики-нолики» в «крестики-нолики» произошло в 20 век.

В 1952 году OXO (или крестики-нолики ), разработанная британским ученым-компьютерщиком Сэнди Дугласом для компьютера EDSAC в Кембриджском университете , стала одной из первых известных видеоигр . Компьютерный игрок мог идеально играть в крестики-нолики против человеческого противника.

В 1975 году крестики-нолики также использовались студентами Массачусетского технологического института, чтобы продемонстрировать вычислительную мощность элементов Tinkertoy . Компьютер Tinkertoy, сделанный из (почти) только игрушек Tinkertoy, отлично умеет играть в крестики-нолики. В настоящее время он выставлен в Музее науки в Бостоне .

Комбинаторика

Если рассматривать только состояние платы и принять во внимание симметрию платы (то есть повороты и отражения), имеется только 138 положений клеммной колодки. Комбинаторика исследования игры показывает , что , когда «X» делает первый ход каждый раз, результаты игры заключаются в следующем:

• 91 отличную позицию выиграли (X)
• 44 различных позиции выиграны (O)
• Разыгрываются 3 различные позиции (часто называемые «кошачьей игрой»).

Стратегия

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

Оптимальная стратегия для игрока O. Игрок O может добиться победы или ничьей, только играя первым в центре.

Игрок может сыграть идеальную игру в крестики-нолики (чтобы выиграть или хотя бы сыграть вничью), если каждый раз, когда наступает их очередь играть, он выбирает первый доступный ход из следующего списка, который использовался в книге Ньюэлла и Саймона 1972 года. программа крестики-нолики.

1. Победа: если у игрока две подряд, он может поставить третью, чтобы получить три подряд.
2. Блок: Если у соперника два подряд, игрок должен сам сыграть третьим, чтобы заблокировать противника.
3. Вилка: создайте сценарий, в котором у игрока есть два способа выиграть (две незаблокированные линии по 2).
4. Блокирование вилки оппонента: если для оппонента существует только одна возможная вилка, игрок должен ее заблокировать. В противном случае игрок должен заблокировать все вилки любым способом, который позволяет одновременно сделать две вилки подряд. В противном случае игрок должен собрать двойку в ряд, чтобы заставить противника защищаться, пока это не приведет к тому, что он произведет вилку. Например, если «X» имеет два противоположных угла, а «O» - центр, «O» не должен делать угловой ход для победы. (Выполнение углового хода в этом сценарии дает развилку для "X", чтобы выиграть.)
5. Центр: игрок отмечает центр. (Если это первый ход в игре, угловой ход дает второму игроку больше возможностей сделать ошибку и, следовательно, может быть лучшим выбором; однако это не имеет значения для идеальных игроков.)
6. Противоположный угол: если противник находится в углу, игрок играет в противоположном углу.
7. Пустой угол: игрок играет в угловом квадрате.
8. Пустая сторона: игрок играет в среднем квадрате с любой из четырех сторон.

Первый игрок, который будет обозначен буквой «X», имеет три возможных стратегически различных положения, которые следует отметить во время первого хода. На первый взгляд может показаться, что существует девять возможных позиций, соответствующих девяти квадратам в сетке. Однако, вращая доску, мы обнаружим, что на первом этапе каждая угловая метка стратегически эквивалентна любой другой угловой метке. То же самое верно для каждой отметки края (середины стороны). Таким образом, со стратегической точки зрения есть только три возможных первых метки: угол, край или центр. Игрок X может выиграть или заставить ничью с любой из этих начальных отметок; однако розыгрыш угла дает противнику наименьший выбор клеток, которые необходимо разыграть, чтобы избежать проигрыша. Это может означать, что угол - лучший начальный ход для X, однако другое исследование показывает, что если игроки не идеальны, для X лучше всего начальный ход в центре.

Второй игрок, который должен быть обозначен «O», должен ответить на начальную отметку X таким образом, чтобы избежать принудительной победы. Игрок О должен всегда реагировать на угловой проем с помощью центральной метки и на центральный проем с угловой меткой. На открытие края нужно ответить либо отметкой центра, отметкой угла рядом с X или отметкой края напротив X. Любые другие ответы позволят X принудительно выиграть. Как только открытие завершено, задача O состоит в том, чтобы следовать приведенному выше списку приоритетов, чтобы форсировать ничью, или же получить выигрыш, если X сделает слабую игру.

Более подробно, чтобы гарантировать ничью, О следует использовать следующие стратегии:

• Если X выполняет ход, открывающий угол, O должен занять центр, а затем край, заставляя X блокировать в следующем ходу. Это предотвратит возникновение любых вилок. Когда и X, и O являются идеальными игроками и X решает начать с отметки угла, O занимает центр, а X занимает угол, противоположный исходному. В этом случае O может выбрать любое ребро в качестве второго хода. Однако, если X не является идеальным игроком и сыграл угол, а затем ребро, O не должен играть противоположное ребро в качестве своего второго хода, потому что тогда X не будет вынужден блокировать на следующем ходу и может выполнить ответвление.
• Если X выполняет ход, открывающий край, O должен занять центр или один из углов, примыкающих к X, а затем следовать приведенному выше списку приоритетов, в основном обращая внимание на вилки блока.
• Если X играет центральный вводный ход, O должен занять угол, а затем следовать приведенному выше списку приоритетов, в основном обращая внимание на блокирующие развилки.

Когда X играет в угловой первым, а O не является идеальным игроком, может произойти следующее:

• Если O отвечает центральной меткой (лучший ход для них), идеальный игрок X займет угол, противоположный исходному. Тогда O должен играть перевес. Однако, если O играет угол в качестве своего второго хода, идеальный игрок X отметит оставшийся угол, блокируя 3-в-рядный O и создавая свою собственную вилку.
• Если O отвечает угловой меткой, X гарантированно выиграет, просто взяв любой из двух других углов, а затем последний, вилку. (поскольку, когда X занимает третий угол, O может занять позицию только между двумя X. Тогда X может занять единственный оставшийся угол, чтобы выиграть)
• Если O отвечает отметкой края, X гарантированно выиграет, взяв центр, тогда O может занять только угол, противоположный углу, который X играет первым. Наконец, X может сделать угол, чтобы создать развилку, и тогда X выиграет на следующем ходу.

Дальнейшие подробности

Рассмотрим доску с девятью позициями, пронумерованными следующим образом:

Когда X играет 1 в качестве своего первого хода, тогда O должен взять 5. Затем X берет 9 (в этой ситуации O не должен брать 3 или 7, O должен взять 2, 4, 6 или 8):

• X1 → O5 → X9 → O2 → X8 → O7 → X3 → O6 → X4, эта игра будет ничьей.

или 6 (в этой ситуации O не должен брать 4 или 7, O должен взять 2, 3, 8 или 9. На самом деле, принятие 9 - лучший ход, так как неидеальный игрок X может взять 4, тогда O может возьмите 7, чтобы выиграть).

• X1 → O5 → X6 → O2 → X8, тогда O не должно брать 3, или X может взять 7, чтобы выиграть, и O не должен брать 4, или X может взять 9, чтобы выиграть, O должен взять 7 или 9.
  • X1 → O5 → X6 → O2 → X8 → O7 → X3 → O9 → X4, эта игра будет ничьей.
  • X1 → O5 → X6 → O2 → X8 → O9 → X4 (7) → O7 (4) → X3, эта игра будет ничьей.
• X1 → O5 → X6 → O3 → X7 → O4 → X8 (9) → O9 (8) → X2, эта игра будет ничьей.
• X1 → O5 → X6 → O8 → X2 → O3 → X7 → O4 → X9, эта игра будет ничьей.
• X1 → O5 → X6 → O9, тогда X не должен брать 4, или O может взять 7, чтобы выиграть, X должен взять 2, 3, 7 или 8.
  • X1 → O5 → X6 → O9 → X2 → O3 → X7 → O4 → X8, эта игра будет ничьей.
  • X1 → O5 → X6 → O9 → X3 → O2 → X8 → O4 (7) → X7 (4), эта игра будет ничьей.
  • X1 → O5 → X6 → O9 → X7 → O4 → X2 (3) → O3 (2) → X8, эта игра будет ничьей.
  • X1 → O5 → X6 → O9 → X8 → O2 (3, 4, 7) → X4 / 7 (4/7, 2/3, 2/3) → O7 / 4 (7/4, 3/2, 3 / 2) → X3 (2, 7, 4), эта игра будет ничьей.

В обеих этих ситуациях (X берет 9 или 6 в качестве второго хода), X имеет 1/3 свойство побеждать.

Если X не идеальный игрок, X может взять 2 или 3 в качестве второго хода. Тогда эта игра будет ничьей, X не может выиграть.

• X1 → O5 → X2 → O3 → X7 → O4 → X6 → O8 (9) → X9 (8), эта игра будет ничьей.
• X1 → O5 → X3 → O2 → X8 → O4 (6) → X6 (4) → O9 (7) → X7 (9), эта игра будет ничьей.

Если X делает 1 первый ход, а O не является идеальным игроком, может произойти следующее:

Хотя O занимает единственно хорошую позицию (5) в качестве первого хода, но O занимает плохую позицию в качестве второго хода:

• X1 → O5 → X9 → O3 → X7, тогда X может взять 4 или 8, чтобы выиграть.
• X1 → O5 → X6 → O4 → X3, тогда X может взять 7 или 9, чтобы выиграть.
• X1 → O5 → X6 → O7 → X3, тогда X может взять 2 или 9, чтобы выиграть.

Хотя O занимает хорошие позиции на первых двух ходах, но O занимает плохую позицию на третьем ходу:

• X1 → O5 → X6 → O2 → X8 → O3 → X7, тогда X может взять 4 или 9, чтобы выиграть.
• X1 → O5 → X6 → O2 → X8 → O4 → X9, тогда X может взять 3 или 7, чтобы выиграть.

O занимает плохую позицию первым ходом (кроме 5, все остальные позиции плохие):

• X1 → O3 → X7 → O4 → X9, тогда X может взять 5 или 8, чтобы выиграть.
• X1 → O9 → X3 → O2 → X7, тогда X может взять 4 или 5, чтобы выиграть.
• X1 → O2 → X5 → O9 → X7, тогда X может взять 3 или 4, чтобы выиграть.
• X1 → O6 → X5 → O9 → X3, тогда X может взять 2 или 7, чтобы выиграть.

Вариации

Многие настольные игры разделяют элемент попытки первыми получить n- in-a-row, в том числе три мужских морриса , девять мужских моррис , пенте , гомоку , кубик , соединить четыре , Quarto , Gobblet , Order and Chaos , Toss Across и Mojo . Крестики-нолики - это пример игры m, n, k , в которой два игрока по очереди по очереди играют на доске размером m × n, пока один из них не получит k подряд. Обобщенные крестики-нолики Харари - еще более широкое обобщение. Игра может быть еще более обобщена, если играть на произвольном гиперграфе , где строки являются гиперребрами, а клетки - вершинами .

Другие варианты крестиков-ноликов включают:

• Трехмерные крестики-нолики на доске 3 × 3 × 3. В этой игре первый игрок легко выигрывает, играя в центре, если играют 2 человека.

Можно играть на доске из квадратов 4х4, выигрывая несколькими способами. Выигрыш может включать: 4 по прямой, 4 по диагонали, 4 по ромбу или 4 по квадрату.

Другой вариант, Qubic , играется на доске 4 × 4 × 4; она была решена путем Орен Паташником в 1980 году (первый игрок может заставить победу). Возможны также более высокие размерные вариации.

• В мизере крестики-нолики игрок выигрывает, если противник выпадает n подряд. Игра 3x3 - это ничья. В более общем смысле, первый игрок может нарисовать или выиграть на любой доске (любого размера) с нечетной длиной стороны, играя сначала в центральной клетке, а затем копируя ходы противника.

• В «диких» крестиках-ноликах игроки могут поставить крестик или букву O на каждом ходу.
• Number Scrabble или Pick15 изоморфны крестикам-ноликам, но на поверхности выглядят совершенно иначе. Два игрока по очереди произносят число от одного до девяти. Конкретное число не может повторяться. Игра выигрывает игрок, который назвал три числа, сумма которых равна 15. Если используются все числа и никто не получает три числа, которые в сумме составляют 15, то игра считается ничьей. Нанесение этих чисел на магический квадрат 3 × 3 показывает, что игра точно соответствует крестикам-ноликам, поскольку три числа будут расположены по прямой линии тогда и только тогда, когда их общее количество равно 15.

• В другой изоморфной игре используется список из девяти тщательно подобранных слов, например, «попытаться», «или», «быть», «на», «любой», «лодка», «мимо», «десять» и «ухо». . Каждый игрок выбирает одно слово по очереди, и чтобы выиграть, игрок должен выбрать три слова с одной и той же буквой. Слова могут быть нанесены на сетку крестиков-ноликов таким образом, что выигрывает линия «три в ряд».
• Числовые крестики-нолики - это вариация, изобретенная математиком Рональдом Грэмом . В этой игре используются числа от 1 до 9. Первый игрок играет с нечетными числами, второй - с четными. Все номера можно использовать только один раз. Выигрывает игрок, поставивший в ряд 15 очков (сумма 3-х чисел).
• В 1970-х годах Tri-ang Toys & Games разработала игру для двух игроков под названием Check Lines , в которой доска состояла из одиннадцати отверстий, расположенных геометрическим узором из двенадцати прямых линий, каждая из которых содержала три отверстия. У каждого игрока было ровно пять жетонов, и он играл по очереди, помещая по одному жетону в любую лунку. Победителем стал первый игрок, чьи жетоны были расположены в две линии по три (которые по определению были пересекающимися линиями). Если ни один из игроков не выиграл к десятому ходу, последующие ходы заключались в перемещении одного из своих жетонов в оставшуюся пустую лунку с ограничением, что этот ход мог быть только из соседней лунки.
• Квантовые крестики-нолики позволяют игрокам размещать квантовую суперпозицию чисел на доске, т. Е. Ходы игроков являются «суперпозициями» ходов в исходной классической игре. Этот вариант был изобретен Алланом Гоффом из Novatia Labs.

Английские имена

Игра имеет различные английские названия, в том числе:

• Tick-tack-toe, tic-tac-toe, tick-tat-toe или tit-tat-toe ( США , Канада )
• Крестики-нолики или крестики-нолики ( Великобритания , Ирландия , Австралия , Новая Зеландия , Южная Африка , Зимбабве , Индия )

Иногда крестики-нолики (где игроки продолжают добавлять «фигуры») и три мужских морриса (когда фигуры начинают двигаться после того, как определенное число было размещено) путают друг с другом.

В популярной культуре

• Джордж Купер написал слова, а Джон Роджерс Томас написал музыку к песне «Tit, Tac, Toe» в 1876 году.
• Эпизод 452 из This American Life рассказывает истинную историю о правовой защите команды , которая стремилась опрокинуть состояние Флориды решения выполнить психически-больной убийцей , выявляя крестики-нолики играющего цыпленка в качестве доказательства . В середине 1970-х были популярны аркадные игры с цыплятами, играющими в крестики-нолики; животные обучались с использованием оперантного кондиционирования , при этом движения выбирались компьютером и указывались цыпленку светом, невидимым для игрока-человека.
• В 1983 году научно-фантастического фильма WarGames , глобальная термоядерная война описывается как похожа на крестики-нолики, в том , что , если все стороны участвовать в полномасштабном использовании своих арсеналов с наиболее эффективными стратегиями возможных, ни одна из сторон не будет на самом деле выиграть .

На основе крестиков-ноликов и их разновидностей основаны различные игровые шоу :

• На Голливудских площадях девять знаменитостей заполнили ячейки сетки крестиков-ноликов; игроки кладут символы на доску, правильно соглашаясь или не соглашаясь с ответом знаменитости на вопрос. Вариации шоу включают в себя сказочный Квадраты и Hip Hop Квадраты . Британская версия называлась Celebrity Squares . Австралия имела различные версии под именами знаменитостей Квадраты, Указано Квадраты и Квадраты All Star .
• В Tic-Tac-Dough игроки раскладывают символы на доске, отвечая на вопросы в различных категориях, которые перемешиваются после того, как оба игрока сделали оба хода.
• В игре Beat the Teacher участники отвечают на вопросы, чтобы выиграть ход, чтобы повлиять на сетку крестиков-ноликов.
• В «Цена правильная» в нескольких национальных вариантах есть ценовая игра под названием «Секрет X», в которой игроки должны угадать цены двух небольших призов, чтобы выиграть Xs (в дополнение к одному бесплатному X) и разместить их на пустой доске. Они должны разместить крестики в таком положении, чтобы угадать расположение титульного «секрета X», спрятанного в центральном столбце доски, и сформировать линию крестиков-ноликов по горизонтали (поперек) или диагонали (вертикальные линии не допускаются). В этом варианте игры нет ОС.
• В Minute to Win It в игре Ping Tac Toe один участник играет с девятью наполненными водой стаканами и бело-оранжевыми шарами для пинг-понга, пытаясь получить по три подряд любого цвета. Они должны менять цвета после каждого успешного приземления и должны быть осторожны, чтобы не блокировать себя.

Смотрите также

• Теорема Хейлза – Джеветта
• Выберите 15
• м, н, к игра

использованная литература

внешние ссылки

• Словарное определение крестиков-ноликов в Викисловаре
• СМИ, связанные с крестиками-ноликами на Викискладе?
• «Крестики-нолики» . Wolfram MathWorld . 11 марта 2002 г.
• «этимология» - почему галстук в крестики-нолики называется «кошачьей игрой»? " " . Обмен английским языком и использованием стека . 5 марта 2014 г. - Обсуждение термина «кошачья игра» для рисованной игры в крестики-нолики.