# CS代考程序代写 algorithm {-

{-

Module: Minimax.

*** PART I (60pt) and PART II (10pt) ***

-}

module Players.Minimax where

import Data.Maybe

import Data.Graph

import Data.Ord

import Data.Tree

import Data.List

import Data.Array

import Types

import Constants

import Cell

import Action

import Board

import Player

import Game

import Players.Dumb (dumbAction)

{-

StateTree util.

-}

— Map a function through the nodes of the tree.

mapStateTree :: (v -> w) -> StateTree v a -> StateTree w a

mapStateTree f (StateTree x ts) = StateTree (f x) [(a, mapStateTree f t) | (a, t)<-ts]
-- Calculate the depth of the tree (used to test pruneDepth).
stateTreeDepth :: StateTree v a -> Int

stateTreeDepth (StateTree _ []) = 0

stateTreeDepth (StateTree _ ts) = 1 + (maximum (map (stateTreeDepth . snd) ts))

— Calculate the breadth of the tree (used to test pruneBreadth).

stateTreeBreadth :: StateTree v a -> Int

stateTreeBreadth (StateTree _ []) = 0

stateTreeBreadth (StateTree _ ts) = max (length ts) (maximum (map (stateTreeBreadth . snd) ts))

{-

Result util.

-}

— Negating the result is simply negating the score. You may ignore this although it may be useful

— to implement the minimax algorithm.

negResult :: Result -> Result

negResult (Result x as) = Result (-x) as

{-

*** Part I.a (10pt) ***

First, we will generate a tree containing all the possible game states.

-}

— Given a game, return a tree that encodes all the possible future game states.

— [Hint: Use ‘validActions’ and ‘performAction’.]

— [Note: To speed things up, you may want to, at this stage, heuristically select which actions are

— more relevant. In particular, you probably don’t want to consider every single possible wall.]

generateGameTree :: Game -> GameTree

generateGameTree = undefined

{-

*** PART I.b (5pt) ***

Re-order the tree so that when traversed by the minimax algorithm, when it traverses the

branches at each node, finds either the higher scores or the lower scores first, depending on

the depth of the tree.

-}

— Higher scoring nodes go first.

— [Hint: You should use ‘lowFirst’.]

highFirst :: (Ord v) => StateTree v a -> StateTree v a

highFirst = undefined

— Lower scoring nodes go first.

— [Hint: You should use ‘highFirst’.]

lowFirst :: (Ord v) => StateTree v a -> StateTree v a

lowFirst = undefined

{-

*** Part I.c (5pt) ***

We don’t want to look at all possible future game states as that would consume too much time and

memory. Instead, we will only look a given number of steps into the future. Formally, the future

game states are encoded in a tree, so we need a function that reduces the depth of a tree.

-}

— Given a depth and a tree, return the same tree but cutting off the branches when the depth is

— exceeded.

— [Hint: You may want to use guards and recursion.]

pruneDepth :: Int -> StateTree v a -> StateTree v a

pruneDepth = undefined

{-

*** Part I.d (5pt) ***

Similarly, we can also make our tree smaller by not considering all the possible game states at

a given point. We need a function that reduces the breadth (or width) of a tree.

-}

— Given a breadth (Int n) and a tree, return the same tree but only keeping the first n branches at

— every node.

— [Hint: Use ‘take’.]

pruneBreadth :: Int -> StateTree v a -> StateTree v a

pruneBreadth = undefined

{-

*** Part I.e (15pt) ***

A crucial part of the minimax algorithm is defining a good utility function. It should measure

how good a game position is for the current player. In our case, a game state should be better

than another one if the player is closer to its winning positions.

-}

— Assign a value to each game (from the point of view of the current player).

— [Hint 1: You may want to calculate the distance between the player’s current cell and its winning

— positions.]

— [Hint 2: One way would be to use ‘reachableCells’ repeatedly.]

utility :: Game -> Int

utility = undefined

— Lifting the utility function to work on trees.

evalTree :: GameTree -> EvalTree

evalTree = mapStateTree utility

{-

*** Part I.f (20pt) ***

Finally, we ask you to implement the minimax algorithm. Given an evaluation tree, it should

return the a high scoring action (according to the minimax algorithm).

-}

— Given an evaluation tree (it stores a score in the node and each branch is labelled with the

— action that leads to the next child) return a list of actions

— [Hint 1: Use a helper function to keep track of the highest and lowest scores.]

— [Hint 2: Use the ‘Result’ datatype.]

minimaxFromTree :: EvalTree -> Action

minimaxFromTree = undefined

{-

*** Part II (10pt) ***

Extension of Part I.e, using alpha-beta pruning. You will need to change the ‘minimax’ function

below to make it use this function.

-}

— Same as above but now use alpha-beta pruning.

— [Hint 1: Extend the helper function in I.e to keep track of alpha and beta.]

— [Hint 2: Use the ‘Result’ datatype.]

minimaxABFromTree :: EvalTree -> Action

minimaxABFromTree = undefined

{-

Putting everything together.

-}

— Given depth for pruning (should be even).

depth :: Int

depth = 4

— Given breadth for pruning.

breadth :: Int

breadth = 10

— Function that combines all the different parts implemented in Part I.

minimax :: Game -> Action

minimax =

minimaxFromTree — or ‘minimaxABFromTree’

. pruneBreadth breadth

. highFirst

. evalTree

. pruneDepth depth

. generateGameTree

— Given a game state, calls minimax and returns an action.

minimaxAction :: Board -> [Player] -> String -> Int -> Maybe Action

minimaxAction b ps _ r = let g = Game b ps in minimaxAction’ g (minimax g)

where

— Goes through the list of actions until it finds a valid one.

minimaxAction’ :: Game -> Action -> Maybe Action

minimaxAction’ g’ (Move s)

| validStepAction g’ s = Just (Move s)

| otherwise = error “Minimax chose an invalid action.”

minimaxAction’ g’ (Place w)

| validWallAction g’ w = Just (Place w)

| otherwise = error “Minimax chose an invalid action.”

— Make minimaxPlayer in the usual way using ‘minimaxAction’.

makeMinimaxPlayer :: String -> Cell -> Int -> [Cell] -> Player

makeMinimaxPlayer n c rws wps = Player {

name = n,

turn = 1,

currentCell = c,

remainingWalls = rws,

winningPositions = wps,

isHuman = False,

chooseAction = minimaxAction }