Ну, на самом деле вам не нужно строить дерево с обновленными оценками. Вам просто нужно вычислить лучший ход (тот, который максимизирует минимальный, худший результат).
Итак, начнем с некоторых предварительных шагов:
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) []]]