tak-ai 0.1.0.0 → 0.1.0.1
raw patch · 3 files changed
+152/−1 lines, 3 files
Files
- src/Negamax.hs +84/−0
- src/TakkyCore.hs +66/−0
- tak-ai.cabal +2/−1
+ src/Negamax.hs view
@@ -0,0 +1,84 @@+{-# LANGUAGE TypeFamilies, FlexibleInstances, BangPatterns #-}+module Negamax (+ Game(..),+ chooseplay+) where++import Data.List++class Game a where+ type Play a :: * -- ^ A play in the game.+ plays :: a -> [(Play a, a)] -- ^ All possible plays from a given game state,+ -- and their successor states.+ eval :: a -> Double -- ^ An assessment of how good the current game state looks.+ ourmove :: a -> Bool -- ^ Whether the next play is ours or our opponents.+ finished :: a -> Bool -- ^ Whether the game has finished.++chooseplay+ :: (Show a, Game a)+ => Int -- ^ Number of levels to look ahead.+ -> a -- ^ The game state+ -> (Play a, a, Double) -- ^ The chosen play, successor state, and the+ -- corresponding maximised minimum score+chooseplay levels state+ | length (plays state) == 0 = error $ "No plays from " ++ show state+ | otherwise = (play, nextState, score)+ where (_, _, score, Just (play, nextState), _) = chooseplay' levels state (-1e101) 1e101++maxGuaranteedScore+ :: (Game a, Show a)+ => Int -- ^ Number of levels to look ahead.+ -> a -- ^ The game state+ -> Double -- ^ The current maximum score that we are guaranteed+ -> Double -- ^ The minimum score that our opponent is guaranteed+ -> Double -- ^ The maximum guaranteed score+maxGuaranteedScore levels state alpha beta+ | levels <= 0 = eval state+ | length (plays state) == 0 = eval state+ | otherwise = score+ where (_, _, score, _, _) = chooseplay' levels state alpha beta++chooseplay'+ :: (Game a, Show a)+ => Int+ -> a+ -> Double+ -> Double+ -> (Double, Double, Double, Maybe (Play a, a), Int)+chooseplay' levels state alphaStart betaStart = bestScore+ where+ bestScore = foldl evalPlay (alphaStart, betaStart, initScore, Nothing, 0) sortedPlays+ initScore+ | ourmove state = -1e101+ | otherwise = 1e101+ evalPlay (alpha, beta, minimax, bestState, count) (play, nextState) =+ let score = maxGuaranteedScore (levels - 1) nextState alpha beta+ (minimax', bestState') = if ourmove state+ then if score > minimax+ then (score, Just (play, nextState))+ else (minimax, bestState)+ else+ if score < minimax+ then (score, Just (play, nextState))+ else (minimax, bestState)+ alpha' = if ourmove state+ then max alpha minimax'+ else alpha+ beta' = if ourmove state+ then beta+ else min beta minimax'+ in+ if count > 100+ then (alpha, beta, minimax, bestState, count)+ else if beta <= alpha+ then (alpha, beta, minimax, bestState, count)+ else (alpha', beta', minimax', bestState', count + 1)+ sortedPlays =+ map fst $ sortPlays (not $ ourmove state) $ zip ps estimates+ estimates = map (\ s -> maxGuaranteedScore (levels - 2) s (-1e101) 1e101) states+ states = map snd ps+ ps = plays state++sortPlays :: Bool -> [(a, Double)] -> [(a, Double)]+sortPlays invert = sortBy $ \ (_, a) (_, b) ->+ if invert then compare a b else compare (-a) (-b)
+ src/TakkyCore.hs view
@@ -0,0 +1,66 @@+{-# LANGUAGE TypeFamilies #-}+module TakkyCore where++import qualified Data.Foldable as Foldable+import System.IO.Unsafe+import System.Random.Shuffle++import Tak+import PlayTakBot++import qualified Negamax++data Takky = Takky String String++instance Bot Takky where+ botName (Takky username _) = username+ botPassword (Takky _ password) = password+ botEvaluate _ colour botGameState = evaluate colour botGameState+ botChoosePlay _ botGameState = Negamax.chooseplay 3 botGameState ++instance Negamax.Game (BotGameState) where+ type Play BotGameState = Play+ plays botGameState = unsafePerformIO $+ shuffleM $ map (\ (GameBranch p n) -> (p, botGameState{bgsTree = n})) branches+ where GameNode _ _ branches = bgsTree botGameState + eval (BotGameState (GameNode _ score _) _) = score+ ourmove (BotGameState (GameNode state _ _) colour) = stPlaysNext state == colour+ finished (BotGameState (GameNode state _ _) _) = stFinished state /= Nothing++--instance Show Takky where+-- show (Takky tree _) = show $ showState $ treeGameState tree++-- | Assigns a score to the current state of the game, from the perspective of+-- black or white. Higher scores indicate an advantageous position.+-- For now, just see who owns more squares.+evaluate :: Colour -> GameState -> Double+evaluate colour state =+ let rand = 0 in --(unsafePreformIO randomIO :: Double) / 100 in+ case stFinished state of+ Nothing ->+ rand + territoryScore (stBoard state) colour+ Just (RoadWin colour') -> if colour == colour'+ then 1e100+ else -1e100+ Just (FlatWin colour' _ _) -> if colour == colour'+ then 1e100+ else -1e100+ Just (Draw _ _) -> 0.0++territoryScore :: Board -> Colour -> Double+territoryScore board ourColour = Foldable.foldr fn 0 board where+ fn [] score = score+ fn ((Flat, colour) : rest) score+ | colour == ourColour = (score + 1) + scoreRest ourColour colour rest+ | otherwise = (score - 1) + scoreRest ourColour colour rest+ fn ((_, colour) : rest) score = score + scoreRest ourColour colour rest++scoreRest :: Colour -> Colour -> Square -> Double+scoreRest ourColour topColour rest = foldr fn 0 rest where+ fn (_, colour) score = score + if colour == topColour+ then if colour == ourColour+ then 0.75+ else -0.75+ else if colour == ourColour+ then 0.25+ else -0.25
tak-ai.cabal view
@@ -1,5 +1,5 @@ name: tak-ai-version: 0.1.0.0+version: 0.1.0.1 synopsis: AI(s) for playing Tak on playtak.com description: Takky is a simple bot, using a modest lookahead of 4 plies, and a heuristic@@ -17,6 +17,7 @@ executable takky main-is: takky.hs+ other-modules: Negamax, TakkyCore hs-source-dirs: src ghc-options: -O2 -threaded "-with-rtsopts=-N" build-depends: base < 5, tak, random-shuffle