Skip to content
This repository

ICFP Programming Contest 2011 repository

branch: master
README
Team: atomically $ save Madoka

## Team Member and their major role:

- Hiroshige Hayashizaki (@akane_magica)
  supreme tuning on LTG machine language
- Shun Sakuraba (@chunjp)
  the bridge of abstract and machine level;
  wrote both commentful Haskell codes and SKIful LTG codes
- Takayuki Muranushi (@nushio)
  wrote the tournament system and the simulation validator
- Hideyuki Tanaka (@tanakh)
  wrote the LTG Monad and the simulator
  
## Used Programming Languages:

- Haskell (all purpose)

- Ruby (scripting)
- Ocaml (for some searching)

## The source codes

   src/Makefile           The makefile
   src/*.hs               AIs
   src/LTG/Base.hs        Definitions for LTG cards
   src/LTG/Exception.hs   Handles for error/recovery mechanism
   src/LTG/Monad.hs       The LTG Monad
   src/LTG/Simulator.hs   The built-in game simulator
   src/LTG/SoulGems.hs    Building blocks library for AI strategies
  
  
## About Our Solution:

- We implemented a DSL for programming LTG playing AIs (artificial
  intelligences) in Haskell.

- The core of the language is the LTG monad. We can write LTG AIs by
  composing the LTG monad. When we `runLTG :: LTG a -> IO ()` the
  monad, it returns a executable program for the LTG. With LTG Monad
  we can describe wide hierarchy of abstractness: from the raw
  sequence of highly-tuned raw-level instructions, to human readable
  strategic instructions (such as 'attack these range' or 'summon
  zombie').

  Such high-level library functions provides safeness, robustness and
  speed. For example, user can build complex strategies and when it
  fails at any point (e.g. the slot it uses is accidentally dead) it
  can safely fall back to recovery. Other functions, such as 'set a
  numeric value to the slot' will performed number construction, so
  that it re-uses partially build numbers from the slot and other
  slots, and it automatically revives the target slot if it's dead.

  The game simulator is integrated within the DSL, So that our AI can
  know the current and past state of the game clearly. Also the
  programmer can instruct the built-in simulator to record the game to
  a file, so that we can understand how our AIs are doing.
   
  All of these features are seamlessly composable, and independently
  extensible.
  

- Our main strategy "Kyoko" series, "Y2CAtkQb" being the final
  product, is to send a zombie to the opponent that issues many 'Help
  i i n' instructions in sequence while incrementing index i. Each of
  the instruction can kill a slot with vital in range [n .. 2.1n].
  Generally, a single zombie issue can kill over ~50 slots.

  And she's really, really fast. She can summon the first zombie in
  136 turns and can kill a "Sitting Duck" (an AI that does nothing) in
  186 turns. She can overwhelm most other strategies just by this
  speed.
  
  The construction process of the zombie is complex, and is prone to
  interceptions from the opponents. Thanks to the accurate simulation
  of the game state and the error handling mechanism, our AI is robust
  against such interceptions. If she detects an error (such as a slot
  being used for construction is killed) she immediately fall-backs to
  a recovery mode, revive the slots, and then re-start the
  construction. At the second run, she uses the caching mechanism:
  she searches for the sub-expressions of the expression she wants to
  build, and try to re-use what she can find on the memory (most
  possibly the immature results of previous disrupted construction.)
  With caching, our AI can issue the second attack really fast too,
  even when the first attack fails.
  
  We noticed the importance and speciality of the slot 0 at the early
  stage of the contest. Although our AIs need to use slot 0
  frequently, the life-time needed for Slot 0 is minimized. One of the
  building-block function "lazyApply" applies a function on slot f1 to
  a value on slot f2 (f1, f2 /= 0) using slot 0 as a work area. It
  requires that slot 0 is kept alive only for several turns. The slot
  0 is occupied about the half of the time until the zombie is ready,
  but the use of slot 0 is in many tiny time segment, so that when the
  construction process is interrupted, the AI goes to recovery mode
  and then resumes the process.
                 
- We also wrote a team-local contest hosting system. Thanks to
  Haskell's powerful and safe parallel programming capability, we
  could easily write the contest system that can hold hundreds of LTG
  match in parallel on a 64-core distributed computer system.
  
  The contest system used remote procedure call (RPC) library
  msgpack-rpc and software transactional memory (STM) library from the
  Hackage.

  
P.S.

  We enjoyed the contest very much!
  Thank you for the interesting problem!
Something went wrong with that request. Please try again.