Игра в 2048 с минимаксным алгоритмом
Как применить Minimax к 2048
2048 - простая игра, но программировать компьютер для ее решения нетривиально
Minimax - это алгоритм, предназначенный для состязательных игр, то есть игр, в которых участвует противник. В этой статье мы увидим, как применить алгоритм минимакса для решения игры 2048 года. Это первая статья из трех частей. Этот будет состоять из планирования нашей игровой программы на концептуальном уровне, а в следующих двух статьях мы увидим реальную реализацию Python.
Здесь я предполагаю, что вы уже знаете, как работает алгоритм минимакса в целом, и сосредоточитесь только на том, как применить его к игре 2048 года. Итак, если вы еще не знаете об алгоритме минимакса, взгляните на:
Основные 4 вещи, о которых нам нужно подумать, применяя минимакс к 2048, и не только к 2048, но и к любой другой игре:
1. Как мы можем думать о 2048 году как об игре для двоих? Кто такой Макс? Кто такая Мин?
2. Как мы определяем, что состояние игры является конечным?
3. Как мы оцениваем оценку / полезность игрового состояния?
4. Как мы определяем потомков игрового состояния?
Первый пункт выше заключается в том, что так работает минимакс, ему нужно 2 игрока: Макс и Мин. Остальные 3 вещи возникают из псевдокода алгоритма, как они выделены ниже:
Когда мы писали общую форму алгоритма, мы сосредоточились только на результатах выделенных функций / методов («он должен определять, является ли состояние терминальным», «он должен возвращать оценку», «он должен возвращать дочерние элементы этого состояние »), не задумываясь о том, как они на самом деле сделаны; это зависит от игры.
Теперь, когда мы хотим применить этот алгоритм к 2048 году, мы переключаем наше внимание на часть «как »: как мы на самом деле делаем это для нашей игры?
Как мы можем думать о 2048 году как об игре для двоих? Кто такой Макс? Кто такой Мин?
Вспомните из алгоритма минимакса, что нам нужно 2 игрока, один, который максимизирует счет, а другой минимизирует его; мы называем их Макс и Мин.
Когда мы играем в 2048 году, нам нужен большой счет. Итак, кто такой Макс? Мы. Мы хотим максимизировать наш результат.
А кто хочет свести к минимуму наш счет? Ну… никто. Есть сама игра, компьютер, который случайным образом порождает части, в основном состоящие из 2 и 4. Но на самом деле это не противник, поскольку нам действительно нужны эти части, чтобы набирать очки. И я не думаю, что игра ставит эти фигуры в невыгодное положение, она просто размещает их случайным образом.
Но минимаксный алгоритм требует противника. Итак, мы будем рассматривать Min как саму игру, которая размещает эти плитки, и хотя в игре плитки размещаются случайным образом, мы будем считать, что наш Min-игрок пытается разместить плитки самым худшим для нас способом.
Как мы решаем, что состояние игры является конечным?
Это просто: состояние игры считается конечным, когда либо игра окончена, либо мы достигли определенной глубины. Мы будем считать, что игра окончена, когда игровое поле заполнено плитками и мы не сможем сделать ход.
Порог глубины в дереве игры предназначен для ограничения вычислений, необходимых для каждого хода. Если мы позволим алгоритму пройти все дерево игры, это займет слишком много времени. Мы хотим ограничить эту глубину так, чтобы алгоритм давал нам относительно быстрый ответ на каждый ход, который нам нужно сделать. Для игры 2048 года хорошо подходит глубина 5–6.
Как мы оцениваем балл / полезность игрового состояния?
Цель игры 2048 - объединить плитки в более крупные, пока вы не получите 2048, или даже превзойдете это число. На изображении статьи выше вы можете увидеть, как наш алгоритм получает плитку 4096. Но точная метрика, которую мы должны использовать в минимаксе, спорна. Можно подумать, что хорошей функцией полезности будет максимальное значение тайла, поскольку это основная цель. Но что, если у нас будет больше игровых конфигураций с тем же максимумом? Как мы их различаем? Я думаю, нам следует подумать, есть ли еще другие большие части, чтобы мы могли объединить их немного позже.
Итак, должны ли мы рассматривать сумму всех значений тайлов как нашу полезность? Но эту сумму также можно увеличить, заполняя доску маленькими плитками, пока у нас не останется ходов. Я считаю, что мы должны наказывать игру за то, что она занимает слишком много места на доске. Так что деление этой суммы на количество непустых плиток кажется мне хорошей идеей. Мы хотим, чтобы наши изделия имели максимальную ценность на как можно меньшем пространстве.
Как мы определяем потомков игрового состояния?
В дереве минимаксной игры дочерними элементами игрового состояния S являются все другие игровые состояния, которые достижимы из S только одним ходом. То, как мы определяем потомков S, зависит от того, какой тип игрока совершает переход от S к одному из его потомков.
Если игрок - Макс (кто мы - пытаемся выиграть игру), то он может нажать одну из клавиш со стрелками: вверх, вниз, вправо, влево. В зависимости от состояния игры не все эти ходы могут быть возможны. Итак, возможные ходы Макса также могут быть подмножеством этих 4.
И в этом случае дочерние элементы S - это игровые состояния, в которые Макс может попасть при выполнении одного из этих ходов.
Какие ходы может делать Мин? Задача Мин - разместить плитки на пустых клетках доски. Большинство этих плиток имеют размер 2 и 4, но также могут использоваться плитки, равные тому, что у нас есть на доске. Однако мы будем рассматривать только 2 и 4 как возможные плитки; это позволяет избежать ненужного большого фактора ветвления и сэкономить вычислительные ресурсы. Как мы уже говорили ранее, мы считаем, что Мин пытается сделать худший из возможных ходов против нас, а именно разместить маленькую плитку (2/4).
Итак, если игрок Мин, возможные ходы - это перекрестное произведение между набором всех пустых квадратов и набором {2, 4}. И дочерние элементы S - это все игровые состояния, которые могут быть достигнуты одним из этих ходов.
Ниже приведен простой пример этого:
На изображении выше 2 незатененных квадрата - единственные пустые квадраты на игровом поле. И ходы, которые может сделать Мин, - это поставить 2 на каждый из них или поставить 4, что дает в общей сложности 4 возможных хода.
На этом пока все. В следующей статье мы увидим, как представить игровую доску на Python через класс Grid. Этот класс будет содержать всю игровую логику, которая нам нужна для нашей задачи.
Надеюсь, эта информация была для вас полезной, и спасибо за внимание!
Эта статья также размещена на моем собственном сайте здесь. Не стесняйтесь смотреть!
