About
Friends
-
Loading...cyberkov 3 days ago -
Loading...cygenb0ck about 13 hours ago -
Loading...legba7 1 day ago -
Loading...lfittl 3 days ago -
Loading...enki 3 days ago -
Loading...antifuchs 14 minutes ago -
Loading...monochrom about 10 hours ago -
Loading...angelol 12 days ago -
Loading...c3o 1 day ago -
Loading...redtux about 10 hours ago -
Loading...Thai 2 days ago -
Loading...kintel 9 days ago -
Loading...Andi 16 days ago -
Loading...kyrah about 5 hours ago -
Loading...wizard23 3 days ago -
Loading...danyx 18 minutes ago -
Loading...kewagi about 11 hours ago -
Loading...lydschi 6 days ago -
Loading...upsidedown 2 months ago -
Loading...oib 12 days ago -
Loading...sushimako 1 day ago -
Loading...worm23 1 day ago -
Loading...reox about 10 hours ago -
Loading...red667 2 days ago
Click here to check if anything new just came in.
March 10 2010
March 03 2010
March 02 2010
2010-02-28---tronbot-google ai challenge
I participated in the google ai challenge. In the end I was placed 134 out of 708: My profile url.
Since I am working on a Monte Carlo tree search based Computer Go program, I figured I would try to use that as a basis for my bot.
In general it worked quiet ok. Especially in close range combat it is often able to play quite well:
At longer range and when looking for the longest path in endgame situations lack of depth in the tree search shows and quiet many mistakes are made.
I also experimented with using the distance between the players as a heuristic to bias the tree search into deeper branches, this was only mildly successful however. It seemed to be very hard to strike a balance between the heuristic not making a difference and turning my bot into a chaser.
In the final version my bots strategy is as follows:
Test if there is a path reaching the opponent using the a* pathfinding algorithm.
# ###############
## ... #
## .#1 #
## # .### #
# # . #
# # . #
# # ..... # #
# # .#### #
# ### # . #
# #### # . #
# # . # #
# # . # #
# # ###. # #
# # .... # #
# # .# #
# ..# ### #
# . # ### #
# ####. # #
# # .... # #
# .. # #
# . # #
# ###. # ##
# 2#. ##
# ... ##
###############
a* found shortest path between players
In case there is not, enter special endgame mode: the value of nodes in tree search is number of moves divided by flood fill size. I am unhappy with the endgame, this should make less mistakes.
In case opponents can still reach each other, use a biased tree search:
p and P are nodes searched for player 1
e and E are nodes searched for player 2 (enemy)
1 is the principal variation for player 1
1 is the principal variation for player 2
###############
#1PPPPPPP #
#111PPPPP #
#1111PPP e#
#PPP1PP eE#
#PPPPPPP eEE#
#PPPPPPPe eEEE#
#PPPPPPEEEeEEE#
#PPP p EEEEEEE#
#PPp EEEEEEE#
#Pp EEE2EEE#
# EEE2222#
# EEEEEE22#
# EEEEEEE22#
###############
nodes evaluated for each player in tree search at long range
At long range nodes closing in to the opponent are preferred.
Nodes are evaluated using flood fill if they divide opponents into separate areas.
Otherwise random playouts until either player crashes are used.
###############
## PPP e #
#### pPPPPWEEE#
# #PPPP111222#
# #PPP11W22E2#
# #PPP11W2EEE#
# #####1W2EEE#
# ##1122EEE#
# PPPW#EEE #
# PP ##E #
# # #
# #####
# ####
# ####
###############
nodes evaluated for each player in tree search at closer range
Tree search terminates as soon as 0.9 seconds are spent and return the best move found so far.
After reading a little about strategies other people have used, it may also have been a bad heuristic to just approach the other bot. "Voronoi territory" - the number of points that can be reached by each bot first - may have been a better choice. In general a good heuristic is key for Monte Carlo tree search to be able to deeply explore the tree without missing the wrong branches, so this could have helped a lot.
Further links:
February 08 2010
On Great Teachers and the Remarkable Life: A Deliberate Practice Case Study

Predicting Greatness
The impact of teachers is profound. If you rank the world’s countries by their students’ academic performance, the US is somewhere in the middle. In a 2009 New Yorker article, Malcolm Gladwell notes that replacing “the bottom six percent to ten percent of public-school teachers with teachers of average quality” could be enough to close the gap between our current position...
February 03 2010
January 26 2010
Rabbits and warrens. - Jason’s .plan
amqp / rabbitmq tutorialJanuary 15 2010
January 14 2010
January 13 2010
January 11 2010
January 09 2010
university of alberta GAMES Group Home Page
university of albertaJanuary 08 2010
January 07 2010
2010-01-07---sudoku
Sometime in autumn 2009 i created a sudoku solver in haskell as a
programming exercise for myself. I am pretty happy with the result, it
took no more than an afternoon to implement and has been able to solve
everything I tried in a couple of seconds. Now I can happily smile to
myself whenever I see someone solving sudokus from the newspaper

Below is a commented and syntax highlighted version of the main module, the complete code in git is also online.
If you are interested in more haskell solutions to the sudoku problem, make sure to check out the Sudoku page on haskellwiki
-- Lefants haskell sudoku solver -- ----------------------------- {-# OPTIONS -O2 -Wall -Werror -Wwarn #-} -- This is the main module, containing the actual logic. module Sudoku ( solveOne, ) where import Data.List {- There are two helpers: * sudoku-test runs some (very very basic) tests. * sudoku-run is the binary for normal invocation, it will read from stdin and output to stdout. use it like this: $ cat <<EOF | ./sudoku-run .98...... ....7.... ....15... 1........ ...2....9 ...9.6.82 .......3. 5.1...... ...4...2. EOF 798624315 315879246 264315978 129587463 683241759 457936182 942158637 531762894 876493521 -} {- The Coord type is a three-dimensional coordinate, the 3rd one is the box the field is in, like indicated here: +-----------+ |111|222|333| |111|222|333| |111|222|333| +-----------+ |444|555|666| |444|555|666| |444|555|666| +-----------+ |777|888|999| |777|888|999| |777|888|999| +-----------+ -} type Coord = (Int, Int, Int) -- Value holds a solution value or a list of remaining valid -- candidates for the field. data Value = Element Int | Options [Int] deriving (Show) -- An actual field consists of a coordinate and a Value (as described -- above). type Pair = (Coord, Value) -- This is the main exported function. It will read in a string of -- digits or . and feed it to the solve' function which will find a -- solution using solve and then return a prettified string -- representation. solveOne :: String -> String solveOne ls = concatMap pretty $ sortBy compareC $ solve' $ zip triples $ map readOne ls -- This will return a list of three-dimensional coordinates as -- explained with the Coord type above. triples :: [Coord] triples = zip3 a b $ map z pairs where pairs = [(a', b') | b' <- [1..9], a' <- [1..9]] (a, b) = unzip pairs z :: (Int, Int) -> Int z (x, y) = x2z + y2z where x2z = ((x - 1) `div` 3) + 1 y2z = ((y - 1) `div` 3) * 3 -- Pretty representation of field values pretty :: (t, Value) -> String pretty (_, Element e) = show e pretty (_, Options _) = "" -- Used for sorting coordinates from left to right and top to bottom. compareC :: (Ord t2, Ord t3) => ((t2, t3, t4), t) -> ((t2, t3, t5), t1) -> Ordering compareC (c1, _) (c2, _) = compareT c1 c2 where compareT (a1, b1, _) (a2, b2, _) | b1 == b2 = compare a1 a2 | otherwise = compare b1 b2 -- Read in a predefined single value or failing that initialize the -- list of options. readOne :: Char -> Value readOne c = case c `elem` (map (head.show) ([1..9] :: [Int])) of True -> Element (read [c]) False -> Options [1..9] -- solve' and solve contain the actual solving logic. solve' will -- partition the initial list of fields into ones containing single -- elements (already defined / solved) and those containing a list of -- remaining options. solve' :: [Pair] -> [Pair] solve' ls = solution where Just solution = solve done todo (done, todo) = partition isElement ls isElement :: (t, Value) -> Bool isElement (_, Element _) = True isElement (_, Options _) = False -- solve takes two lists of coordinate / value pairs as parameters: -- the first one contains solved single element fields, the second all -- the lists with remaining options. solve :: [Pair] -> [Pair] -> Maybe [Pair] -- if all the fields have one element we are done. solve es [] = Just es solve es os = case as of -- no more Options, no solutions possible [] -> Nothing -- try first option (a : as') -> -- recurse using backtracking, if we can solve it case solve ((c, Element a) : es) os' of -- we are done Just es' -> Just es' -- this branch contains no solutions, retry without it Nothing -> solve es ((c, Options as') : os') where -- first prune all Options list at the current level, then order -- branches with *few* options first ((c, Options as) : os') = sortBy lessOptions $ map revaluate os lessOptions (_, Options xs) (_, Options ys) = compare (length xs) (length ys) lessOptions (_, Element _) _ = error "illegal lessOptions call" lessOptions (_, Options _) (_, Element _) = error "illegal lessOptions call" -- filter out other Options from list that are made impossible -- by choosing a certain one revaluate :: Pair -> Pair revaluate (c'@(x, y, z), Options aas) = {-# SCC "revaluate" #-} (c', Options aas') where aas' = aas \\ otherValues otherValues = map (\(_, Element e) -> e) ((filter (\e -> x == px e) es) ++ (filter (\e -> y == py e) es) ++ (filter (\e -> z == pz e) es)) revaluate ((_, _, _), Element _) = error "illegal revaluate call" -- helper functions to project a single coordinate from a Pair px :: Pair -> Int px ((x, _, _), _) = x py :: Pair -> Int py ((_, y, _), _) = y pz :: Pair -> Int pz ((_, _, z), _) = z
Maybe Soup is currently being updated? I'll try again automatically in a few seconds...
