Totoro Beam Search C++ Starter

Anonymous

5,662 views

GitHub

Open Source Your Knowledge, Become a Contributor

Technology knowledge has to be shared and made accessible for free. Join the movement.

Create Content

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

#pragma GCC optimize "O3,mavx2,omit-frame-pointer,inline,unroll-loops"
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <chrono>
#include <map>
#include <cmath> 
#include <bitset>
#include <set>
#include <cstring>
#include <iomanip> 
using namespace std;
using namespace chrono;
// If you liked the starter, please have at least one message containing a JoJo reference.
// Thank you for your appreciation!
vector<string> greetings = {" Omae wa mou shindeiru",  // Reference: Fist of the North Star 
    " May your journey overflow with curses and blessings.", // Reference: Made in Abyss
    " Opponent eval: 1ms, score: MUDA"}; // Reference: JoJo's Bizarre Adventures
int turn = 0;
bitset<37> r0; // tiles with 0 richness
struct Node {
    int tile;
    array<Node*,6> nhex; // neighbours
    array<array<bitset<37>,3>,6> shadow; // precomputed shadows of various tree levels
    int r; // richness for this Tile
    Node(int t1) {
        tile = t1;
    }
};
array<Node*,37> mapp;
void initialize(int x2) {
    for (int dir = 0; dir < 6; dir++) {
        if (mapp[x2]->nhex[dir] != NULL) {
            mapp[x2]->shadow[dir][0][mapp[x2]->nhex[dir]->tile] = 1;
            if (mapp[x2]->nhex[dir]->nhex[dir] != NULL) {
                mapp[x2]->shadow[dir][1][mapp[x2]->nhex[dir]->nhex[dir]->tile] = 1;
                
                if (mapp[x2]->nhex[dir]->nhex[dir]->nhex[dir] != NULL) {
                    mapp[x2]->shadow[dir][2][mapp[x2]->nhex[dir]->nhex[dir]->nhex[dir]->tile] = 1;
                }
            }

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

Open Source Your Knowledge: become a Contributor and help others learn. Create New Content

Open Source Your Knowledge, Become a Contributor

About

Code

TODO

Feedback and Suggestions

Apprendre le C++

Using Pragma For Compile Optimization

Computing with Data

How to randomize bits and integers efficiently in C++