CODEWITHSUNDEEP
haskellminimax
kkkjjj
kkkjjj

Reputation: 43

Minimax in haskell

I'm trying to write a minimax function for connectfour game, here is my unfinished code

minimax:: RT Board ->Int
minimax (Tree board subtrees) = case subtrees of 
    []                                                                  >evaluate board (get_turn board)  
    _                                                                  ->case get_turn board of 
            Player_X                                                   ->maximum (next_socres)  
            Player_O                                                   ->minimum  (next_socres) 
 where next_socres = map evaluate (map get_board subtrees) 

--get the node from sub trees
get_board:: RT Board -> Board
get_board (Tree board subtrees) = board

--evaluate moves(not finished)
evaluate :: Board -> Player -> Int
evaluate board me'   
    |[me,me,me,Blank] `isInfixOf_e` all_stone_lines                         = 10
    |[opp,opp,opp,Blank] `isInfixOf_e` all_stone_lines                      = -10
    |otherwise                                                              = 0 
    where
        me = get_stone_of me'
        opp = opponent' me
        all_stone_lines = combine_list stones_from_rows (combine_list     stones_from_cols (combine_list stones_from_left_dias                  stones_from_right_dias))   
        stones_from_rows = map (get_from_row board) [1..board_size] 
        stones_from_cols = map (get_from_column board) [1..board_size] 
        stones_from_left_dias = map (get_from_left_diagonal board) [-(board_size-1)..(board_size-1)]
        stones_from_right_dias = map (get_from_right_diagonal board) [2..(2*board_size)]

I want to use map to evaluate every subtrees before it compute the whole tree, but I don't know how to use map here... And I realised that if my code compiled, it will not be a recursion. Can anyone teach me how to do?

Upvotes: 1

Views: 2064

Answers (1)

Jean-Baptiste Potonnier
Jean-Baptiste Potonnier

Reputation: 568

You have multiple problems in your implementation that are more algorithm problems than Haskell.

Minimax is a recursive algorithm, building a score by evaluating all the moves that are possible from a position, up to a certain depth (or the end of the game).

During the recursion, Max player is alternating with Min player.

From this, the minimax function should have the board, the maximum depth and the player type as parameter.

Something like :

minimax :: Board -> Int -> Bool -> Int
minimax board depth isMax = ...

minimax should also call itself on all the possible boards generated by moves. Then you apply the maximum or minimum, depending of the isMax parameter.

Another thing is that you are trying to recurse on a tree. The tree that you often see in the literature is nothing more than the recursive calls of the minimax function.

In other words, you don't need a tree as parameter, the tree is implicitly built by successive minimax calls.

As a side note, while abstracting from a particular game, it may be useful to add as a parameter a function do determine if the board is representing a finished game.

Upvotes: 3

Related Questions