Недавно мы разобрали игру Ним с точки зрения математики и теории игр и даже написали её простую версию. Сегодня закроем тему и сделаем компьютерный алгоритм, который очень сложно обыграть.
Напомним, о чём речь:
- теория игр — это не только про игры, а про любые ситуации, в которых может что-то происходить, меняться и зависеть от разных факторов;
- игрок — это тот, кто находится в этой ситуации и принимает решения;
- смысл теории игр в том, чтобы понять, как нужно действовать игрокам в разных ситуациях, чтобы получить нужный результат. Но не интуитивно, а с точки зрения законов математики
Всё это мы разобрали на примере игры Ним: есть несколько кучек, в каждой из которых лежит сколько-то камней. За один ход игрок может взять из любой одной кучки любое ненулевое число камней. Игроки берут камни по очереди. Побеждает тот, кто забирает последние камни.
В теории игр есть понятие выигрышного хода, или выигрышной позиции. Грубо говоря: если обеспечить вот такую позицию или делать ходы по вот такому математическому принципу, то ты точно выиграешь. Это одна из самых интересных математикам тем — как описать законы, по которым формируются выигрышные позиции.
Выигрышная позиция для победы в Ним такая: нужно ходить так, чтобы после хода XOR всех кучек был равен нулю. Вот как это работает:
0 XOR 0 = 0
0 XOR 1 = 1
1 XOR 0 = 1
1 XOR 1 = 0
Программа, которую мы написали в прошлый раз, этого не делает — она не умеет считать выигрышность хода и делает всё наобум. Сегодня мы это исправим, а заодно сделаем игру универсальной — там будет сколько угодно кучек и выбор уровня сложности. Всё пишется на языке Python — языке дата-сайентистов, аналитиков и бэкенд-разработчиков.
# подключаем модуль для работы со случайными числами
import random
# формируем кучки с камнями
stack_1 = random.randint(2,10)
stack_2 = random.randint(2,10)
# выбранная кучка
select = 0
# сколько камней взяли из кучки
taken = 0
# кто делает текущий ход
current_player = 'Игрок'
# забираем камни из кучки
def take(stack, num):
# будем менять глобальную переменную внутри функции
global taken
# если ход делает компьютер
if current_player == 'Компьютер':
# случайным образом выбираем количество камней, которые заберём из кучки
taken = random.randint(1,stack)
# выводим состояние текущего хода
print(current_player + ' взял ' + str(taken) + ' камней из ' + str(num) + ' кучки')
# уменьшаем кучку на выбранное количество камней
stack = stack - taken
# возвращаем количество камней в кучке
return(stack)
# выводим текущее состояние кучек
def result():
# сообщаем, сколько камней в каждой кучке
print('Камней в 1 кучке: ' + str(stack_1))
print('Камней в 2 кучке: ' + str(stack_2))
# если в кучках не осталось камней — текущий игрок победил
if stack_1 == 0 and stack_2 == 0:
print('Игра окончена, победил ' + current_player)
# выходим из программы
exit()
# ход компьютера
def take_computer():
# будем работать с глобальными переменными
global stack_1, stack_2, current_player
# если в первой кучке нет камней
if stack_1 == 0:
# берём камни из второй
stack_2 = take(stack_2, 2)
# то же самое для второй кучки
elif stack_2 == 0:
stack_1 = take(stack_1, 1)
# если камни в кучках есть
else:
# выбираем случайным образом номер кучки
choice = random.randint(1,2)
# если выбрана первая кучка — берём камни оттуда
if choice == 1:
stack_1 = take(stack_1, 1)
# то же самое для второй кучки
else:
stack_2 = take(stack_2, 2)
# выводим на старте состояние кучек
result()
# запускаем бесконечный цикл
while True:
# если ходит компьютер
if current_player == 'Компьютер':
# он делает свой ход
take_computer()
# выводим состояние кучек
result()
# меняем текущего игрока
current_player = 'Игрок'
# если ходит игрок
else:
# спрашиваем у него номер кучки и количество камней
select = int(input('Выберите кучку: '))
taken = int(input('Сколько камней забрать: '))
# если игрок выбрал первую кучку — берём оттуда
if select == 1:
stack_1 = take(stack_1, 1)
# а если вторую — то оттуда
else:
stack_2 = take(stack_2, 2)
# выводим состояние кучек
result()
# меняем текущего игрока
current_player = 'Компьютер'Подготавливаем переменные
В прошлый раз мы сделали две кучки и жёстко привязали их к своим переменным. Сделаем игру Ним универсальной и добавим туда сколько угодно кучек — их количество будет регулироваться отдельной переменной.
Это позволит сделать игру универсальной и добавит интерес игроку — если с двумя кучками будет просто, всегда можно сделать больше.
# подключаем модуль для работы со случайными числами
import random
# кучки с камнями
stacks = []
# количество кучек
nums = 3
# перебираем все кучки и заполняем их случайными значениями
for i in range(nums):
stacks.append(random.randint(2,10))
# выбранная кучка
select = 0
# сколько камней взяли из кучки
taken = 0
# кто делает текущий ход
current_player = 'Игрок'Забираем камни из кучки
Так как у нас кучки хранятся в одной переменной, то для выбора кучки достаточно знать её порядковый номер. Это значит, что мы можем упростить функцию выбора кучек и передать в неё только номер кучки, откуда нужно забрать камни.
Ещё функция не будет ничего возвращать: мы сразу уменьшим нужную кучку на выбранное количество камней.
# забираем камни из кучки
def take(where):
# будем менять глобальные переменные внутри функции
global taken, stacks
# если ход делает компьютер
if current_player == 'Компьютер':
# случайным образом выбираем количество камней, которые заберём из кучки
taken = random.randint(1,stacks[where])
# выводим состояние текущего хода
print(current_player + ' взял ' + str(taken) + ' камней из ' + str(where) + ' кучки')
# уменьшаем кучку на выбранное количество камней
stacks[where] = stacks[where] - taken
# заканчиваем работу функции
return()Выводим текущее состояние кучек
В старой функции было всё просто: две переменной для кучек и простой вывод. Теперь кучки хранятся в списке, поэтому нам нужно перебрать его, чтобы вывести количество камней в каждой. Также сразу будем складывать общее количество камней: если оно будет нулевым, то текущий игрок победил и игра останавливается.
# выводим текущее состояние кучек
def result():
# общая сумма камней в кучках, на старте нулевая
sum = 0
# перебираем все кучки
for i in range(nums):
# выводим состояние каждой
print('Камней в ' + str(i) + ' кучке: ' + str(stacks[i]))
# добавляем количество камней к общей сумме
sum = sum + stacks[i]
# если в кучках не осталось камней
if sum == 0:
# выводим победителя
print('Игра окончена, победил ' + current_player)
# выходим из программы
exit()Выбираем уровень сложности
Чтобы было интереснее играть, добавим выбор уровня сложности перед основным циклом игры. Логика будет такая:
- Запрашиваем сложность — от 1 до 10.
- Перед каждым ходом компьютера берём случайное число в этом диапазоне.
- Если оно меньше уровня сложности — компьютер делает идеальный ход, а если больше — то обычный.
Это нужно для того, чтобы дать игроку шанс победить. Чем ниже уровень сложности, тем чаще будет выпадать случайное число, которое больше него, и тем чаще компьютер будет делать обычный (а не идеальный) ход.
# выбираем уровень сложности
difficult = int(input('Выберите сложность от 1 до 10: '))
Ход компьютера
Теперь оптимизируем ход компьютера. Раньше мы делали много проверок, потому что у каждой кучки была своя переменная и нужно было обрабатывать их по отдельности. Теперь, когда все кучки в едином списке, мы можем упростить код: выбрать случайную непустую кучку и передать это число в функцию, где забираются камни:
# ход компьютера
def take_computer():
# будем работать с глобальными переменными
global stacks
# запускаем бесконечный цикл
while True:
# выбираем номер кучки
choice = random.randint(0,nums-1)
# если выбрали не пустую
if stacks[choice] != 0:
# берём оттуда камни
take(choice)
# и выходим из функции
return()Находим лучший ход для компьютера
Когда математики разбирали эту игру, они выяснили, что лучший ход в этой игре — это тот, после которого XOR всех кучек становится равным нулю. Получается, нам нужно сделать так:
- Перебираем все кучки по очереди.
- Если кучка не пустая — перебираем в ней все камни, от 1 до общего количества камней.
- Каждый раз уменьшаем выбранную кучку на это количество камней и считаем общий XOR всех кучек.
- Если результат равен нулю — выводим его на экран, уменьшаем текущую кучку на выбранное количество камней и выходим из функции.
- Если мы так и не нашли идеальный ход (то есть не вышли из функции в какой-то момент), то делаем обычный случайный ход.
Также нам понадобится создать копию кучек, чтобы можно было свободно экспериментировать с количеством забранных камней и случайно не потерять исходные данные.
# находим лучший ход
def best_move():
# будем менять глобальную переменную
global stacks
# перебираем все кучки
for i in range(nums):
# если в текущей кучке есть камни
if stacks[i] != 0:
# перебираем камни из этой кучки
for j in range(1, stacks[i]+1):
# создаём копию кучек
temp_stacks = stacks.copy()
# уменьшаем текущую кучку на текущее выбранное количество камней
temp_stacks[i] = temp_stacks[i] - j
# считаем XOR первых двух кучек
xor = temp_stacks[0] ^ temp_stacks[1]
# считаем XOR оставшихся кучек
for k in range(2, nums):
xor = xor ^ temp_stacks[k]
# если общий XOR равен нулю
if xor == 0:
# выводим лучший ход
print('Лучший ход: забрать ' + str(j) + ' камней из ' + str(i) + ' кучки где ' + str(stacks[i]))
# уменьшаем нужную кучку на это число камней
stacks[i] = stacks[i] - j
# выходим из функции
return()
# если дошли сюда, значит, идеального хода нет, делаем обычный
take_computer()Основной цикл игры
По сравнению со старым кодом здесь будут два больших дополнения: влияние уровня сложности и механика выбора кучек игроком.
С уровнем сложности так: мы получаем случайным образом новое число — назовём его фактор удачи. Если фактор удачи выше уровня сложности — компьютер делает обычный ход и берёт камни как попало. В противном случае компьютер рассчитывает идеальный ход и делает очередной шаг к победе.
А вот механика выбора кучек игроком стала проще: нам достаточно передать в функцию отбора камней номер выбранной кучки. Благодаря тому, что кучки хранятся в одном списке, к конкретной кучке можно обратиться по её номеру.
# выводим на старте состояние кучек
result()
# запускаем бесконечный цикл
while True:
# если ходит компьютер
if current_player == 'Компьютер':
# определяем, повезёт обойти уровень сложности или нет
luck = random.randint(1,10)
# если случайное число больше уровня сложности
if luck > difficult:
# компьютер берёт камни случайным образом
take_computer()
# иначе, если случайное число меньше уровня сложности
else:
# компьютер делает идеальный ход
best_move()
# выводим состояние кучек
result()
# меняем текущего игрока
current_player = 'Игрок'
# если ходит игрок
else:
# спрашиваем у него номер кучки и количество камней
select = int(input('Выберите кучку: '))
taken = int(input('Сколько камней забрать: '))
# забираем камни из выбранной кучки
take(select)
# выводим состояние кучек
result()
# меняем текущего игрока
current_player = 'Компьютер'
# подключаем модуль для работы со случайными числами
import random
# кучки с камнями
stacks = []
# количество кучек
nums = 3
# перебираем все кучки и заполняем их случайными значениями
for i in range(nums):
stacks.append(random.randint(2,10))
# выбранная кучка
select = 0
# сколько камней взяли из кучки
taken = 0
# кто делает текущий ход
current_player = 'Игрок'
# забираем камни из кучки
def take(where):
# будем менять глобальные переменные внутри функции
global taken, stacks
# если ход делает компьютер
if current_player == 'Компьютер':
# случайным образом выбираем количество камней, которые заберём из кучки
taken = random.randint(1,stacks[where])
# выводим состояние текущего хода
print(current_player + ' взял ' + str(taken) + ' камней из ' + str(where) + ' кучки')
# уменьшаем кучку на выбранное количество камней
stacks[where] = stacks[where] - taken
# заканчиваем работу функции
return()
# выводим текущее состояние кучек
def result():
# общая сумма камней в кучках, на старте нулевая
sum = 0
# перебираем все кучки
for i in range(nums):
# выводим состояние каждой
print('Камней в ' + str(i) + ' кучке: ' + str(stacks[i]))
# добавляем количество камней к общей сумме
sum = sum + stacks[i]
# если в кучках не осталось камней
if sum == 0:
# выводим победителя
print('Игра окончена, победил ' + current_player)
# выходим из программы
exit()
# находим лучший ход
def best_move():
# будем менять глобальную переменную
global stacks
# перебираем все кучки
for i in range(nums):
# если в текущей кучке есть камни
if stacks[i] != 0:
# перебираем камни из этой кучки
for j in range(1, stacks[i]+1):
# создаём копию кучек
temp_stacks = stacks.copy()
# уменьшаем текущую кучку на текущее выбранное количество камней
temp_stacks[i] = temp_stacks[i] - j
# считаем XOR первых двух кучек
xor = temp_stacks[0] ^ temp_stacks[1]
# считаем XOR оставшихся кучек
for k in range(2, nums):
xor = xor ^ temp_stacks[k]
# если общий XOR равен нулю
if xor == 0:
# выводим лучший ход
print('Лучший ход: забрать ' + str(j) + ' камней из ' + str(i) + ' кучки где ' + str(stacks[i]))
# уменьшаем нужную кучку на это число камней
stacks[i] = stacks[i] - j
# выходим из функции
return()
# если дошли сюда, значит, идеального хода нет, делаем обычный
take_computer()
# ход компьютера
def take_computer():
# будем работать с глобальными переменными
global stacks
# запускаем бесконечный цикл
while True:
# выбираем номер кучки
choice = random.randint(0,nums-1)
# если выбрали не пустую
if stacks[choice] != 0:
# берём оттуда камни
take(choice)
# и выходим из функции
return()
# выбираем уровень сложности
difficult = int(input('Выберите сложность от 1 до 10: '))
# выводим на старте состояние кучек
result()
# запускаем бесконечный цикл
while True:
# если ходит компьютер
if current_player == 'Компьютер':
# определяем, повезёт обойти уровень сложности или нет
luck = random.randint(1,10)
# если случайное число больше уровня сложности
if luck > difficult:
# компьютер берёт камни случайным образом
take_computer()
# иначе, если случайное число меньше уровня сложности
else:
# компьютер делает идеальный ход
best_move()
# выводим состояние кучек
result()
# меняем текущего игрока
current_player = 'Игрок'
# если ходит игрок
else:
# спрашиваем у него номер кучки и количество камней
select = int(input('Выберите кучку: '))
taken = int(input('Сколько камней забрать: '))
# забираем камни из выбранной кучки
take(select)
# выводим состояние кучек
result()
# меняем текущего игрока
current_player = 'Компьютер'
