Codegolf - Играйте В Крестики-Нолики И Никогда Не Проиграйте

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

Испытание

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

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

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

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

Выигрывает самый короткий код на каждом языке.

#код-гольф #настольная игра #крестики-нолики

Бефунге, 181 168 байт

 
 
 
 
 
 
 
 
 
 
 # Checks if the given player has 3 in a row and returns 1 if so
def evaluate(board,turn):

for i, d in (0,1),(3,1),(6,1),(0,3),(1,3),(2,3),(0,4),(2,2):

if board[i]==b[i+d]==b[i+2*d]==turn: return 1

# Negamax recursive function
def negamax(board, turn, depth=8):

# Checks if player or opponent has won

if evaluate(board,turn): return 0,1

if evaluate(board,-turn): return 0,-1

# Checks if board is full

if all(board): return 0,0

# Goes through all possible moves in the board (available spots)

best_score = -2

for index in range(9):

if board[index]==0:

# Make the move, evaluate position, and unmake the move

board[index] = turn

score = -negamax(board, -turn, depth-1)[1]

board[index] = 0

# If score was better than previous best score, update best score and move

if score > best_score:

best_score, best_move = score, index

# Return best move and score after it has gone through all possibilities

return best_move, best_score
 
 
 
 
 
 
 
 
 
 
 

Позиции на доске пронумерованы от 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.

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

Питон 3, 18 байт

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

Этот блестящий ИИ всегда будет добиваться ничьей, а иногда и побеждать, если вы позволите.

Сетка нумеруется по спирали, вот так:

и компьютер всегда идет первым. Для первого хода введите «10». Это немного избыточно, потому что оно всегда идет в одном и том же месте, но оно уже встроено в алгоритм, поэтому ¯\_(ツ)_/¯

Если сначала идти посередине, игра, по сути, превращается в одномерную, и единственный способ выиграть - это 3 игры подряд по сторонам. Делит все оставшиеся 8 квадратов на пары и всегда переходит на другой квадрат пары. Например, если вы пойдете на клетку 1, она пойдет на клетку 2. Если вы пойдете на клетку 2, она пойдет на клетку 1. Хорошая особенность этой системы в том, что она никогда не сделает незаконный ход, а также никогда не проиграет. .

На самом деле это был фокус, изобретенный Мартином Гарднером, с помощью которого можно предсказать исход игры в крестики-нолики. Все игры заканчиваются одинаково, включая ротацию, иначе компьютер побеждает. Оно «никогда не проигрывает».

2 исправления ошибок: заслуга l4m2

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

-16 символов: заслуга Джонатана Фреча

-26 символов: заслуга пользователя 202729.

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

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

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

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

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

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

Питон 3: 341 байт

Итак, моя первая попытка игры в гольф, отличный вызов! Хотя я сам думал о чем-то подобном, имея в виду полноценную игру. Вот код AI:

Попробуйте онлайн
Попробуйте код здесь.

Ввод/вывод

Функция 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]) takes a 1D array as input where X and O are represented by 1 and -1, and empty squares by 0. Example board:

равно

Затем он выводит лучший ход (индекс доски от 0 до 8) для данного игрока вместе с его оценкой:

• Оценка = 1: текущий игрок побеждает.
• Оценка = -1: Победа другого игрока.
• Счет = 0: ничья, если оба игрока играют идеально.

\
Объяснение

Функция «n» — это структура Negamax, в которой она проходит все дерево возможных решений от заданного состояния доски до завершения игры (игрок выигрывает или доска заполнена). Для каждого возможного хода он сначала идет в глубину и до конца проверяет все возможные результаты этого хода.

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