Bookworm 🐛

Bookworm is a BattleSnake bot written in Rust for the March 2020 tournament. Combines the strategies of pruned turn tree exploration, minimax, and heuristic scoring. The snake is given a time budget to explore the turn tree; the fewer the snakes, the deeper the exploration.

A server instance playing against itself using the built-in host mode. See play-host.sh as an example.

Building and running

Just run cargo build --release to produce a self-contained binary at target/release/bookworm. The binary can be invoked with a number of modes and options, which the -h flag explains in detail. The available modes are:

• server: Runs as a typical snake API server, ready to be play.
• host: Locally hosts a match between given snakes, logging each turn state. Implements 2020 rules.
• benchmark: A series of common operations are timed and logged.

Development

Unit tests can be run with cargo test, though some strategy tests will fail currently. To quickly build and run the bot, use cargo run <mode>. Note that the development build is significantly slower at runtime than the release build, so you may need to increase the --timeout for host mode and give the server more time budget with --budget to achieve similar lookahead depths.

Todos and improvement ideas:

• Heuristics and strategy
  • Implement more unit tests for behaviour
  • Seed the turn tree exploration with some longer term "plays" instead of just single space movements
  • Allow for chances of death instead of assumed worst case
  • If death unavoidable, prefer head-to-head
  • Are there heuristic elements we can skip sometimes?
• Performance
  • Can I write some const fn to move work to compile time?
  • Can I use fixed arrays or vec![0.0; src.len()] anywhere?
  • Look for places to use .copied() instead of .cloned()
  • Avoid indexing into vecs; use if let Some(x) = vec.get(i)
  • infallible DS to avoid empty checks
  • Move hosting to us-west-1 to be closer to BS host
• Pathfinding (if used)
  • JPS
  • Dynamic heuristic weight

The "wat" list

Questionable life choices:

• Turn 114: Feeding rule change?
• Turn 230: Gave enemy opportunity to easily kill us head-to-head
• Turn 383: Gave enemy opportunity to easily trap us
• Turn 300: Trapped self... why??
• Turn 36: Giving up too early
• Turn 13: Allow for chance of survival
• Turn 21: Prefer going up because less likely blue_bottle will go there
• Turn 74: Ran into another snake, but should prefer possibility of head-to-head death
• Turn 240: Could have trapped enemy but didn't
• Turn 122: Ditto above
• Turn 15: Didn't understand stacked tail rule?

References and resources

• https://github.com/BattlesnakeOfficial/rules/blob/master/standard.go
• https://github.com/BattlesnakeOfficial/engine/blob/master/rules/tick.go
• https://github.com/anvaka/ngraph.path
• https://github.com/riscy/a_star_on_grids
• https://www.redblobgames.com/pathfinding/grids/algorithms.html
• http://likebike.com/posts/How_To_Write_Fast_Rust_Code.html