-- -- | -- Module : CopHeuristic -- Copyright : (c) 2005 -- License : GPL version 2 or later -- Created : 26 Jun 2005 -- module CopHeuristic where import Maybe ( fromJust ) import System.Random import Logging import Pretty import Syntax import Graph import KnowledgeBase import Logging import CR import CopState import Data.List import Debug.Trace onFootSmellDist :: Int onFootSmellDist = 2 byCarSmellDist :: Int byCarSmellDist = 1 reallyLargeDistance = 100 ------------------------------------------------------------------------ -- -- The goodness of a map -- goodness :: GNode -> Int -> Int -> Int -> Int -> Int -> Int -> [GNode] -> KnowledgeBase -> CR Float goodness yourNode nearOtherLocCoeff nearNextRobbedBankCoeff nearBankCoeff nearRobberStartBankCoeff recentlyVisitedNodeCoeff randomCoeff visitedNodes kb = do let graphFoot = kb_footMap kb graphCar = kb_carMap kb robberMoney = kb_robberLoot kb banks = kb_banks kb cops = kb_cops kb worldTime = kb_worldCount kb hqNode = kb_hq kb robberStartNode = lookupNode robber_start kb r <- liftIO $ randomRIO (0,1) nearOtherLocsBase <- nearOtherLocsBonus kb yourNode let randomBonus = fromIntegral randomCoeff * r nearOtherLocs = (fromIntegral nearOtherLocCoeff) * nearOtherLocsBase nearNextRobbedBank = (fromIntegral nearNextRobbedBankCoeff) * nearNextRobbedBankBonus kb graphTriple yourNode banks nearBank = (fromIntegral nearBankCoeff) * nearBankBonus kb graphTriple yourNode banks -- should be computed once only nearRobberStartBank = (fromIntegral nearRobberStartBankCoeff) * nearRobberStartBankBonus kb graphTriple yourNode robberStartNode banks recentlyVisitedNode = (nearVisitedNode graphTriple yourNode visitedNodes) * (fromIntegral recentlyVisitedNodeCoeff) graphTriple = (graphFoot, graphCar, hqNode) bonuses = [ nearOtherLocs, nearNextRobbedBank, nearBank, nearRobberStartBank, randomBonus ] penalties = [ recentlyVisitedNode ] debug $ "For location " ++ showPpr (locOfNode yourNode) ++ " bonuses and penalties are:" debug $ "nearOtherLocBonus = " ++ show nearOtherLocs debug $ "nearNextRobberBankBonus = " ++ show nearNextRobbedBank debug $ "nearBankBonus = " ++ show nearBank debug $ "nearRobberStartBankBonus = " ++ show nearRobberStartBank debug $ "recentlyVisitedNodePenalty = " ++ show recentlyVisitedNode return $ ((sum bonuses) - (sum penalties)) ------------------------------------------------------------------------ type GraphTriple = ( Graph -- foot map , Graph -- car map , GNode -- hq node ) ------------------------------------------------------------------------ -- -- Takes the otherLocs finds a set of possible nodes for each and then -- takes the intersection of all of them. This gives a set of nodes -- in which the robber must be. We then find the shortest distance -- from our current location to one of those nodes. The bonus is -- inversely proportional to this distance. -- -- NOTE: Assumes you are on foot. -- nearOtherLocsBonus :: KnowledgeBase -> GNode -> CR Float nearOtherLocsBonus kb yourNode = do copState <- getState let nm = kb_ownName kb otherRobberSet <- mkRobberSet kb yourNode (otherLocs copState) debug $ "*Your* locs are: " ++ show (yourLocs copState) yourRobberSet <- mkYourNodeSet kb yourNode (yourLocs copState) let robberSet = nub (yourRobberSet ++ otherRobberSet) let sps = map (\n -> length (fastShortestPath yourNode n footSPs)) robberSet dist = case sps of [] -> reallyLargeDistance _ -> minimum sps debug $ "The set of locations the robber could be at is: " ++ show (map (showPpr . locOfNode) robberSet) return $ 1 / (fromIntegral (dist + 1)) where graph = kb_footMap kb nodeMap = kb_loc2node kb footSPs = kb_footSPs kb -- -- Takes a bunch of nodes returned by other cops and finds and *assuming* -- they are completely honest *and* don't under-report the set finds a set -- of nodes that the robber must be in. -- mkRobberSet :: KnowledgeBase -> GNode -> [(Name, [(Location, WorldNum)])] -> CR [GNode] mkRobberSet kb yourNode otherLocs = do -- we only pass on non-empty sets let nonEmptyLocs = filter (not . null . snd ) otherLocs nodeSets <- mapM (mkNodeSet kb yourNode) nonEmptyLocs case filter (not . null) nodeSets of [] -> return [] sets -> return $ foldr1 intersect sets mkNodeSet :: KnowledgeBase -> GNode -> (Name, [(Location, WorldNum)]) -> CR [GNode] mkNodeSet kb yourNode (name, locTimes) = do -- FIXME: Check what form of locomation you are using -- -- For the moment we are disregarding when the notification was given. -- let graph = kb_footMap kb nodeMap = kb_loc2node kb wc = kb_worldCount kb nodeSets = map (\(l,t) -> nodesWithin graph (lookupNode l nodeMap) ((wc - t) `div` 2)) locTimes nodeSet = nub (concat nodeSets) -- union! debug $ "Cop " ++ show name ++ " thinks the robber could be at: " ++ show (map locOfNode nodeSet) return nodeSet mkYourNodeSet :: KnowledgeBase -> GNode -> [(Location, WorldNum)] -> CR [GNode] mkYourNodeSet kb yourNode locTimes = do let graph = kb_footMap kb nodeMap = kb_loc2node kb wc = kb_worldCount kb nodeSets = map (nub . (\(l,t) -> nodesWithin graph (lookupNode l nodeMap) ((wc - t) `div` 2))) locTimes nodeSet = case filter (not . null) nodeSets of [] -> [] sets -> foldr1 intersect sets debug $ "*You* think the robber could be at: " ++ show (map locOfNode nodeSet) return nodeSet -- -- Proximity to the closest bank to the bank that been robbed most recently. -- Always non-negative. -- -- Should also be inversely proportional to the time that bank was robbed -- -- [1 .. 1/(longest path between banks)] -- nearNextRobbedBankBonus :: KnowledgeBase -> GraphTriple -> GNode -> [Bank] -> Float nearNextRobbedBankBonus kb (foot,_,_) yourNode banks = -- which banks have been robbed, if any let rbanks = filter (\b -> bank_lastTimeRobbed b /= Nothing) banks in if null rbanks then 0.0 -- no banks robbed yet -- else this is the most recently robbed bank else let realBank = head $ sortBy mostRecentlyRobbed rbanks bank = bank_node realBank -- the other banks otherbanknodes = (map bank_node banks) \\ [bank] fsps = kb_footSPs kb -- paths to all banks from the robbed bank, with the end -- node as the first element of the tuple bankpaths = map (\b -> (b, length $ fastShortestPath bank b fsps)) otherbanknodes -- now find the closest bank to the robbed bank next_bank_to_rob = fst . head $ sortBy (\(_,p1) (_,p2) -> p1 `compare` p2) bankpaths -- and how far are we from the closest bank? next_bank_distance = length $ fastShortestPath yourNode next_bank_to_rob fsps -- inversely proportional to the distance to the bank in if kb_worldCount kb - (fromJust $ bank_lastTimeRobbed realBank) > 4 then 0.0 else (1.0 / fromIntegral (next_bank_distance + 1)) where mostRecentlyRobbed (Bank { bank_lastTimeRobbed = b1 } ) (Bank { bank_lastTimeRobbed = b2 } ) = b1 `compare` b2 -- --------------------------------------------------------------------- -- -- just being near a bank is a good thing. this encourages us to go to -- banks before any other values kick in -- nearBankBonus :: KnowledgeBase -> GraphTriple -> GNode -> [Bank] -> Float nearBankBonus kb (foot,_,_) yourNode realBanks = let banks = map bank_node realBanks -- all banks fsps = kb_footSPs kb bankpaths = map (\b -> (b, length $ fastShortestPath yourNode b fsps)) banks shortestpath = snd . head $ sortBy (\(_,p1) (_,p2) -> p1 `compare` p2) bankpaths -- inversely proportional to the distance to the bank in (1.0 / fromIntegral (shortestpath + 1)) -- --------------------------------------------------------------------- -- -- Going to the next bank to the bank closest to "54-and-ridgewood" is -- good, as the robber always begins there in tournament play, and will -- rob the first bank unless its stupid. -- robber_start = "54-and-ridgewood" nearRobberStartBankBonus :: KnowledgeBase -> GraphTriple -> GNode -> GNode -> [Bank] -> Float nearRobberStartBankBonus kb (foot,_,_) yourNode robberNode realBanks = -- find the bank closest to the robber-start let banks = map bank_node realBanks -- all banks fsps = kb_footSPs kb bankpaths = map (\b -> (b, length $ fastShortestPath robberNode b fsps)) banks closestBankToRobber = fst . head $ sortBy (\(_,p1) (_,p2) -> p1 `compare` p2) bankpaths -- the other banks otherbanknodes = banks \\ [closestBankToRobber] -- paths to all banks from the 'will-be-robbed' bank, with the -- end node as the first element of the tuple bankpaths' = map (\b -> (b, length $ fastShortestPath closestBankToRobber b fsps)) otherbanknodes -- now find the closest bank to the robbed bank next_bank_to_rob = fst . head $ sortBy (\(_,p1) (_,p2) -> p1 `compare` p2) bankpaths' -- and how far are we from the closest bank? next_bank_distance = length $ fastShortestPath yourNode next_bank_to_rob fsps -- inversely proportional to the distance to the bank in (1.0 / fromIntegral (next_bank_distance + 1)) nearVisitedNode :: GraphTriple -> GNode -> [GNode] -> Float nearVisitedNode (foot,_,_) yourNode visitedNodes = let succs = gsucc foot yourNode succVals = map (\n -> (howLongAgo n visitedNodes) / 2) succs nodeVal = howLongAgo yourNode visitedNodes in sum succVals + nodeVal where howLongAgo n visitedNodes = case elemIndex n visitedNodes of Nothing -> 0 Just i -> fromIntegral (length visitedNodes - i)