stuck with minimax algorithm - what next? Haskell

Question

I'm writing a basic MiniMax algorithm for a 2 player board game. So far I have a function that evaluates a board and returns a score. I have a function that returns a rose tree of all possible moves (and moves for those moves) etc... to a given depth. I can find the leaves of that tree and give them a value based of my heuristic and my question is what do I do after that?

Do I somehow edit the parent of the leaves and assign the parent node a new value based on the children's value and keep going until I get to the root node?

Am I meant to create a new tree from the leaves up, picking the min / max value until i get to the root node? If so, how does the new tree remember all the moves needed to get to the leaves?

I only want to use imports from the standard library (I don't want to have to download a package). Any suggestions would be great, been struggling with this for a few days. Thanks

---

I tried to pick out some parts of my code to give examples but there's just a lot of functions tangled together. If it helps at all here are the type signatures for the main functions and an explanation of what they do:

This function takes in an Int (representing Depth of tree), a Game (current state of board), list of immediate possible moves and returns a rose tree with each possible move (and moves to those moves) and a score associated with that move. If player is Dark its score is positive, if player is dark its score is negative - each depth in the rose tree is the next players move.

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

For example: treeAtDepthN 2 initialGame [(2,3),(3,2),(4,5),(5,4)] returns :

[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) []]]

I have another function which allows me to get the leaves of a tree. I use the function that evaluates the game state in treeAtDepthN for each move but I realize that probably isn't necessary and should only be used on the leaves of the tree. I'm not sure if this helps at all.

---

later edit:

Not sure what to do next for my minimax algorithm. I have a function that prints all possible moves to a certain depth, I have a heuristic that evaluates those each move, I'm just not sure how I turn it into one function that returns the best move. I only want to use functions given in the Haskell library (Don't want to download any packages ect).

data Rose a = Rose a [Rose a]
    deriving Show

I thought I might be easier to understand if I drew a picture explaining the functions I have. I Have two solutions I can think of which are outlined in the picture, I'm not sure which approach I should go for, if any. :

I guess I want a function that turns the [Rose a] at the top of the picture to the rose a at the bottom of the picture.

Thanks.

Answer 1

Well, you don't actually need to build a tree with updated scores. You just need to calculate the best move (the one that maximizes the minimum, worst-case score).

So, start with some preliminaries:

import Data.List
import Data.Ord

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

We can write a function that takes a list of move trees and selects the move (aka Position) that results in the maximum of the minimum scores:

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

The helper minscore calculates the minimum score for a move tree, assuming best counterplay.

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

If we're at a leaf, our best estimate of the score is the direct heuristic evaluation of the current board, so we just return that position and score:

minscore (Rose x []) = x

Otherwise, we calculate the score from best counterplay using the opposite of maximin, namely minimax:

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

Note that minscore always returns the next move (pos) from the root of the tree, but the score will be taken from the root (for leaves) or by further recursive calculation (for nodes).

The full definition of maximin and its mirror image minimax is:

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)

Applied to your pictorial example:

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) []]]

you get:

> example
((3,3),2)

which looks like what you wanted.

A few notes on performance:

• The minimax algorithm doesn't actually use the heuristic scores of internal nodes, only at the leaves, so you might be better off processing a [Rose Position] and only calculating a heuristic score where you need it (when you detect a leaf in minscore or maxscore).
• Alpha-beta pruning is a well-known optimization of the minimax algorithm, and ought to be used in any serious implementation.

Anyway, the full code is:

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) []]]