Back
Close

Totoro Beam Search C++ Starter

AntiSquid
2,054 views

About

C++ starter code for the CG Spring Challenge 2021. (Totoro / Photosynthesis / Whatever you want to call it)

Algorithm is Chokudai's variant of Beam Search.

Totoro has a lot of high ranking bots with just basic heuristics (if/else conditions), therefore a basic search with some decent eval will get you very far on the leaderboard. Best way to do this is by analysing the game and spot best plays. Doing this will then get you accustomed to the code.

You're meant to improve on the code and optimize it yourself. Bitsets are a personal preference.

Beam Search is about taking n most promissing moves and exploring their future outcomes. This variant however has n (the beam width) starting at 1 and then gradually increase with each iteration.

Code

TODO

  • Fix the sorting function
  • Write the eval / scoring
  • Optimize the code. For example a Heap could do a lot more than a vector for states or look up zobrist hash for copying gamestates.
  • Reuse states next turn.
  • Improve by adding opponent prediction or a separate search
  • Fix the time limit conditions.
  • You can precompute a lot more than just shadows (see the initialize() function). For example distances, tree costs and much more.
  • Further improve based on strategies listed on the forums: https://www.codingame.com/forum/t/spring-challenge-2021-feedbacks-strategies/190849

Feedback and Suggestions

are very much appreciated. Looking forward to hear from you.

Thanks!

~ AntiSquid

Create your playground on Tech.io
This playground was created on Tech.io, our hands-on, knowledge-sharing platform for developers.
Go to tech.io
codingame x discord
Join the CodinGame community on Discord to chat about puzzle contributions, challenges, streams, blog articles - all that good stuff!
JOIN US ON DISCORD
Online Participants