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

Вызов

Напишите программу, которая играет в игру крестики-нолики. Он не должен проигрывать (поэтому он должен закончить игру ничьей или победой).

Разрешенные методы ввода / вывода

1. На входе может быть текущая доска. Вы можете предположить, что все предыдущие ходы 2-го игрока были выполнены вашим двигателем.
2. Входные данные могут быть первыми ходами игрока, а ваша функция сохраняет, какие ходы произошли в прошлом. В этом случае функция вызывается несколько раз, по одному разу для каждого хода; или ввод подсказки функции / программы несколько раз.
3. Вы можете сделать дополнительный ввод, говоря, что вы первый игрок, или написать две (возможно, связанные) функции для решения проблемы первого игрока и задачи второго игрока. Если вашей программе нужно использовать метод ввода 2 (множественный вызов), вы можете решить, что будет передано в первом вызове.
4. Выходом может быть доска после вашего хода.
5. Выход может быть вашим ходом.
6. Ход может быть представлен в виде пары чисел (может быть 0-индексирование или 1-индексирование), числа в диапазоне 0 ~ 8 или числа в диапазоне 1 ~ 9.
7. Доска может быть представлена ​​в виде массива 3 × 3 или массива длиной 9. Даже если язык имеет массив с 0 индексами, вы можете использовать 1-индексирование.
8. Клетки на сетке могут использовать любые 3 различных значений , чтобы указать X, Oи опорожнить.

Критерии победы

Самый короткий код на каждом языке победит.

Befunge, 181 168 байт

>>4&5pp20555>>03>16p\::5g8%6p5v
 ^p5.:g605$_ #!<^_|#:-1g61+%8g<
543217539511|:_^#->#g0<>8+00p3+5%09638527419876
v<304p$_v#:->#$$:2`#3_:^
>#\3#13#<111v124236478689189378

Позиции на доске пронумерованы от 1 до 9. По умолчанию вы получаете первый ход, но если вы хотите разрешить компьютеру идти первым, вы можете просто ввести 0 для первого хода. Когда вы сделаете ход, компьютер ответит цифрой, обозначающей их ход.

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

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

Пользователь играет первым: попробуйте онлайн!
Компьютер играет первым: попробуйте онлайн!

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

Пользователь играет первым: попробуйте онлайн!
Компьютер играет первым: попробуйте онлайн!

Обратите внимание, что вам придется подождать, пока тайм-аут TIO, прежде чем вы сможете увидеть результаты.

объяснение

Доска хранится в области памяти Befunge в виде плоского массива из 9 значений с индексами от 1 до 9. Это позволяет нам использовать нулевое смещение в качестве особого случая «без движения», когда мы хотим, чтобы компьютер сначала играл. Ходы игрока сохраняются как 4, а компьютер - как 5. Для начала все позиции инициализируются как 32 (по умолчанию память Befunge), поэтому, когда мы получаем доступ к доске, мы модифицируем с 8, поэтому мы получим либо 0, 4 или 5.

При таком расположении, если мы суммируем значения любых трех позиций на игровом поле, мы знаем, что компьютер находится на расстоянии одного шага от выигрыша, если общее количество равно 10, игрок на один шаг от выигрыша, если общее число равно 8, и позиции распределяются между компьютером и игроком (но все же одна позиция свободна), если общее количество равно 9.

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

Основной список тестируемых троек - это выигрышные комбинации (1/2/3, 1/5/9, 1/4/7 и т. Д.). Сначала мы ищем всего 10 (компьютер собирается выиграть), а затем - 8 (игрок собирается выиграть, и нам нужно заблокировать этот ход). Менее очевидно, мы также проверяем в общей сложности 9 (если игрок и компьютер имеют одну из позиций, это хорошая стратегия для компьютера, чтобы занять третью позицию).

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

Наконец, есть два особых случая. Во-первых, мы всегда стараемся занять центральную позицию перед любым другим ходом. Это достигается с помощью той же процедуры, что и все наши другие ходы, просто проходя одну тройку, 5/5/5 и целевую сумму 0. Кроме того, если во всех других тестах не удалось найти ход, мы стараемся выполнить один из верхних углов в крайнем случае. Опять же, это просто достигается путем тестирования тройки 1/1/1 и 3/3/3 с целевой суммой 0.

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

Python 2: 399 401 349 333 317 370 байт

2x Исправление ошибки: кредит до l4m2

-52 символа: кредит на подземный монорельс

-16 символов: кредит Джонатана Фреха

-26 символов: кредит пользователю 202729

def f(b):
 t=4,9,2,3,5,7,8,1,6;n=lambda k:[t[i]for i,j in enumerate(b)if j==k];p,o,a,I=n(2),n(1),n(0),t.index
 for i in p:
    for j in p:
     for k in a:
        if i+j+k==15and-j+i:return I(k)
 for i in o:
    for j in o:
     for k in a:
        if i+j+k==15and-j+i:return I(k)
 for i in 9,3,7,1:
    if i in a and 5 in p:return I(i)
 for i in 5,4,2,8,6:
    if i in a:return I(i)
 return I(a[0])

Попробуйте онлайн!

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

4 | 9 | 2
--+---+--
3 | 5 | 7
--+---+--
8 | 1 | 6

затем получение трех в ряд равносильно выбору трех чисел в диапазоне [1,9], которые в сумме составляют 15. Этот ответ использует эту идею. Функция берет список, содержащий девять чисел, представляющих доску. 0 обозначает пустое место, 1 занята противником, а 2 обозначает предыдущую игру, выполненную программой. Первые 3 строки показывают, какие цифры выбрала программа (p), оппозиция выбрала (o) и все еще доступны (a). Затем он просматривает доступные числа и видит, добавит ли любое из них в сочетании с двумя уже выбранными числами число к пятнадцати. Если это произойдет, он выберет этот квадрат и выиграет. Если нет немедленных выигрышных ходов, он проверит, сможет ли противник выиграть, используя тот же метод. Если они могут, это займет их выигрышную клетку. Если нет ни выигрышного, ни блокирующего хода, он будет двигаться в углу. Это мешает дуракам мат:

- - - 
- X -
- - -

- O -             # Bad Move
- X -
- - -

- O X
- X -
- - -

- O X
- X -
O - -

- O X
- X -
O - X

Если ни одна из этих ситуаций не произойдет, он выберет квадрат произвольно. Функция выводит число [0,8], представляющее индексированный квадрат 0, выбранный алгоритмом.

Редактировать: алгоритм теперь отдает приоритет центру по диагонали, что предотвратит возможность другого партнера по дуракам, указанную в l4m2 и связанных стратегиях.

Редактировать: Чтобы уточнить, функция принимает доску в виде массива и выводит ход в виде целого числа на [0,8]. Поскольку эта стратегия ввода / вывода настолько неуклюжа, вот сценарий-обертка, который делает ее более интерактивной. Он принимает один аргумент командной строки, который должен быть равен 1, если игрок идет первым, и 0, если программа идет первым.

import sys

def f(b):
 t=4,9,2,3,5,7,8,1,6;n=lambda k:[t[i]for i,j in enumerate(b)if j==k];p,o,a,I=n(2),n(1),n(0),t.index
 for i in p:
    for j in p:
     for k in a:
        if i+j+k==15and-j+i:return I(k)
 for i in o:
    for j in o:
     for k in a:
        if i+j+k==15and-j+i:return I(k)
 for i in 9,3,7,1:
    if i in a and 5 in p:return I(i)
     for i in 5,4,2,8,6:
        if i in a:return I(i)
 return I(a[0])

board = [0,0,0,0,0,0,0,0,0]
rep = {0:"-",1:"X",2:"O"}

turn = int(sys.argv[1])
while True:
    for i in range(3):
        print rep[board[i*3]]+" "+rep[board[i*3+1]]+" "+rep[board[i*3+2]]
        print
    if turn:
        move = int(raw_input("Enter Move [0-8]: "))
    else:
        move = f(board)
    board[move] = turn+1
    turn = (turn+1)%2