Недавно мы разобрали игру Ним с точки зрения математики и теории игр и даже написали её простую версию. Сегодня закроем тему и сделаем компьютерный алгоритм, который очень сложно обыграть.
В теории игр есть понятие выигрышного хода, или выигрышной позиции. Грубо говоря: если обеспечить вот такую позицию или делать ходы по вот такому математическому принципу, то ты точно выиграешь. Это одна из самых интересных математикам тем — как описать законы, по которым формируются выигрышные позиции. Выигрышная позиция для победы в Ним такая: нужно ходить так, чтобы после хода XOR всех кучек был равен нулю.
Программа, которую мы написали в прошлый раз, этого не делает — она не умеет считать выигрышность хода и делает всё наобум. Сегодня мы это исправим, а заодно сделаем игру универсальной — там будет сколько угодно кучек и выбор уровня сложности. Всё пишется на языке Python — языке дата-сайентистов, аналитиков и бэкенд-разработчиков.