застрял с минимаксным алгоритмом - что дальше? Haskell - PullRequest
Новая
       70

застрял с минимаксным алгоритмом - что дальше? Haskell

0 голосов
/ 19 октября 2019

Я пишу основной алгоритм MiniMax для настольной игры для 2 игроков. Пока у меня есть функция, которая оценивает доску и возвращает счет. У меня есть функция, которая возвращает розовое дерево всех возможных ходов (и ходов для этих ходов) и т. Д. На заданную глубину. Я могу найти листья этого дерева и дать им оценку, основанную на моей эвристике, и мой вопрос: что мне делать после этого?

Должен ли я каким-либо образом отредактировать родительский элемент листьев и назначить родительскому узлу новое значение, основанное на значении дочерних элементов, и продолжать, пока не доберусь до корневого узла? новое дерево из листьев, выбирая минимальное / максимальное значение, пока я не доберусь до корневого узла? Если да, как новое дерево запоминает все ходы, необходимые для того, чтобы добраться до листьев?

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

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

Эта функция принимает Int (представляющее Depth дерева), Game (текущее состояние доски), список ближайших возможных ходов и возвращает дерево роз с каждым возможным ходом (и ходами к этим ходам) и счет, связанный с этим ходом. Если игрок темный, его счет положительный, если игрок темный, его счет отрицательный - каждая глубина в розовом дереве является следующим ходом игрока. 

roseTreeAtDepthN :: Int-> Game -> [Position] -> [Rose (Position,score)]

Например: treeAtDepthN 2 initialGame [(2,3),(3,2),(4,5),(5,4)] возвращает: 

[Rose ((2,3),4) [Rose ((2,2),-3) [],Rose ((2,4),-3) [],Rose ((4,2),-3) []],
 Rose ((3,2),4) [Rose ((2,2),-3) [],Rose ((2,4),-3) [],Rose ((4,2),-3) []],
 Rose ((4,5),4) [Rose ((3,5),-3) [],Rose ((5,3),-3) [],Rose ((5,5),-3) []],
 Rose ((5,4),4) [Rose ((3,5),-3) [],Rose ((5,3),-3) [],Rose ((5,5),-3) []]]

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

, позже отредактируйте:

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

Imagine

Полагаю, мне нужна функция, которая превращает [Роза a] в верхней части изображения в розу a в нижней частирисунок.

Спасибо.

1 Ответ

1 голос
/ 22 октября 2019

Ну, на самом деле вам не нужно строить дерево с обновленными оценками. Вам просто нужно вычислить лучший ход (тот, который максимизирует минимальный, худший результат).

Итак, начнем с некоторых предварительных шагов: 

import Data.List
import Data.Ord

type Position = (Int,Int)
type Score = Int
data Rose a = Rose a [Rose a]

Мы можем написать функцию, котораяберет список деревьев движений и выбирает ход (он же Position), который приводит к максимуму минимальных баллов: 

maximin :: [Rose (Position, Score)] -> (Position, Score)
maximin = maximumBy (comparing snd) . map minscore

Помощник minscore вычисляет минимальный балл для дерева ходов, предполагая,лучшая контрпроигра. 

minscore :: Rose (Position, Score) -> (Position, Score)

Если мы находимся на листе, наша лучшая оценка счета - это прямая эвристическая оценка текущей доски, поэтому мы просто возвращаем эту позицию и счет: 

minscore (Rose x []) = x

В противном случае мы рассчитываем счет из лучшей контрплэйки, используя противоположность maximin, а именно minimax: 

minscore (Rose (pos,_) moves)
  = let (_,score) = minimax moves in (pos,score)

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

Полное определение maximin и его зеркальное отображение minimaxэто: 

maximin :: [Rose (Position, Score)] -> (Position, Score)
maximin = maximumBy (comparing snd) . map minscore
  where minscore (Rose x []) = x
        minscore (Rose (pos,_) moves)
          = let (_,score) = minimax moves in (pos,score)

minimax :: [Rose (Position, Score)] -> (Position, Score)
minimax = minimumBy (comparing snd) . map maxscore
  where maxscore (Rose x []) = x
        maxscore (Rose (pos,_) moves)
          = let (_,score) = maximin moves in (pos,score)

Применительно к вашему наглядному примеру: 

example = maximin
  [Rose ((1,1),2) [Rose ((1,2),3) [], Rose ((1,3),-2) [], Rose ((1,4),4) []],
   Rose ((2,2),3) [Rose ((2,3),-7) [], Rose ((2,4),-1) []],
   Rose ((3,3),1) [Rose ((3,4),2) []]]

вы получите: 

> example
((3,3),2)

, который выглядит так, как вы хотели.

Несколько замечаний по производительности:

  • Минимаксный алгоритм на самом деле не использует эвристические оценки внутренних узлов, только на листьях, поэтому вам лучше обработать [Rose Position] и вычислять эвристические оценки только там, где вам это нужно (когдавы обнаружите лист в minscore или maxscore).
  • Альфа-бета-отсечение - это хорошо известная оптимизация минимаксного алгоритма, которая должна использоваться в любой серьезной реализации.

В любом случае, полный код: 

import Data.List
import Data.Ord

type Position = (Int,Int)
type Score = Int
data Rose a = Rose a [Rose a]

maximin :: [Rose (Position, Score)] -> (Position, Score)
maximin = maximumBy (comparing snd) . map minscore
  where minscore (Rose x []) = x
        minscore (Rose (pos,_) moves)
          = let (_,score) = minimax moves in (pos,score)

minimax :: [Rose (Position, Score)] -> (Position, Score)
minimax = minimumBy (comparing snd) . map maxscore
  where maxscore (Rose x []) = x
        maxscore (Rose (pos,_) moves)
          = let (_,score) = maximin moves in (pos,score)

example = maximin
  [Rose ((1,1),2) [Rose ((1,2),3) [], Rose ((1,3),-2) [], Rose ((1,4),4) []],
   Rose ((2,2),3) [Rose ((2,3),-7) [], Rose ((2,4),-1) []],
   Rose ((3,3),1) [Rose ((3,4),2) []]]
...