🐈

thunder本をPythonとRustとC++で実装する

2025/01/16に公開

thunder本について

みなさんthunder本をご存知でしょうか?最高の本なのでぜひ買ってください。

https://www.amazon.co.jp/ゲームで学ぶ探索アルゴリズム実践入門~木探索とメタヒューリスティクス-青木-栄太/dp/4297133601

thunder本は探索するタイプの問題の解き方について教えてくれます。囲碁・将棋みたいな相手の手番があって自分の手番があって勝ち負けがつくゲーム、などが典型です。
正直この時点では自分もピンとは来てなかったんですが、実際に手を動かして実装する中で面白さに気づきました。読者が絶対に取り残されないように丁寧に解説してありコードもコメントが豊富なので、本当にぜひ一度買って手を動かしてみてください!

実装する

実装したものがリポジトリに置いてあるのでもし参考になる部分があれば幸いです。当たり前ですがC++が早く、ついでRust、Pythonとなっており巷で言われているPythonが遅い問題が実感できて面白かったです。

https://github.com/banbiossa/thunder-book

私は普段はPython使いなので、以下はその目線でお話しします。

C++

提供コード

技評の書籍ページに提供されているサンプルコードがあります。

https://gihyo.jp/book/2023/978-4-297-13360-3/support

こちらのコードはインラインのコメントも多く、めちゃくちゃ素晴らしいです!

一方でテストを書きたいなーとか、共通部分を括り出して変更が必要な部分がどこかを明確に理解したいなーという気持ちがあったので、自分で実装することにしました。

ファイル分割

単体テストとか、共通化するにはファイルを分割したくなります。

NaiveなC++の世界観では gcc main.c -o main のように1ファイルごとにコンパイルすることになります。これを共通部分を分割してコンパイルすると g++ -Wall -g main.cpp game.cpp -o program みたく列挙することになるのでファイルが増えるとなかなか煩雑になります。

古くはこれらはMakefileで自動化していたと思います。CMakeもその系譜にいる認識です。
一方で現代のエンジニアとしては宣言的に全部いい感じにしてほしい!と思うところなので、散々色々試した挙句 Bazel に辿り着きました。

WORKSPACEファイルとかがめんどさくさいけど、一度書いてしまえば後はBUILDファイルを比較的直感的に追加していけます。以下のように書いておいて

load("@rules_cc//cc:defs.bzl", "cc_binary", "cc_library")

cc_library(
    name="maze_state",
    srcs=[
        "auto_move_maze_state.cc",
        "random_action.cc",
        "hill_climb.cc",
        "simulated_annealing.cc",
    ],
    hdrs=[
        "auto_move_maze_state.h",
        "random_action.h",
        "hill_climb.h",
        "simulated_annealing.h",
    ],
    visibility=[
        "//test/ch04:__pkg__",
    ],
)

cc_binary(
    name="score_average",
    srcs=[
        "average_score.cc",
    ],
    deps=[
        ":maze_state",
    ],
)

これで実行するのは bazel run //src/ch04:score_average -c とシンプルになりました。

テスト (GoogleTest)

Bazelを利用する利点としてはもう1つ、テストのためのフレームワークの導入が楽になります。
gtest.BUILDの設定ファイルを書いておけば、以下のように他の言語と同じように単体テストが書けます。

#include <iostream>
#include <string>
#include "gtest/gtest.h"
#include "src/ch04/auto_move_maze_state.h"

using namespace std;

class MazeStateTest : public ::testing::Test
{
protected:
    AutoMoveMazeState state;

    MazeStateTest() : state(0) {}
};

TEST_F(MazeStateTest, ToString)
{
    string actual = state.to_string();
    string expected = R"(
turn: 0
score: 0
@1378
78221
93742
31164
93939
)";
    EXPECT_EQ(actual, expected);
}

TEST_F(MazeStateTest, IsDone)
{
    EXPECT_FALSE(state.is_done());
}

これで書き直す中で出てきた細かな違いや間違いに気づきやすくなりました。

実装してみて

C++は食わず嫌いしていましたが、テストやファイル分割をしたことでかなり自分の知っているプログラミングの土俵に引きずり込めた感覚がありました。アルゴリズム系の本はC++で書かれていることも多く、写経することで「読める、読めるぞ!」の感覚になりめちゃくちゃ楽しくなりました。みなさんもぜひ!

Python

普段Pythonが主戦場なので、自分の理解を試すためにPythonでも実装しました。特に特筆する部分もないですが、ロジックの追いやすさに関してはPythonはやはり長けているのかなと思います。

面白かったのは7章でZobristHashを用いた高速化をするのですが、Pythonではnumpyを用いて実装するほうが高速かつ簡単でした。言語特有のライブラリを用いた工夫の面白さを感じました。

# 難しいところをnumpyに任せる
class NumpyState(state):
    def get_distance_to_nearest_point(self) -> int:
        mat = np.zeros((self.params.height, self.params.width), dtype=bool)
        mat[self.character.y, self.character.x] = True

        for depth in range(self.params.height * self.params.width):
            if np.any(mat & self.points_mat_):
                return depth

            next = mat.copy()
            next[1:, :] |= mat[:-1, :]
            next[:-1, :] |= mat[1:, :]
            next[:, 1:] |= mat[:, :-1]
            next[:, :-1] |= mat[:, 1:]
            next &= ~self.walls_mat_
            if np.all(next == mat):
                break
            mat = next

        return self.params.height * self.params.width

Rust

Rustはずっと勉強したかったのですが、今までしっくりくる題材がなくRustのチュートリアルを触っただけになっていました。その点thunder本は個人的にはやりたいことが明確で最高でした。
何をpubにして他のモジュールからの呼び出しを許可するか、何をmutにして変更させるかなど今まで漠然と理解していたコンセプトがどんどん明確になりました。同じファイルの中でテストを書く、という哲学もstructが小さいうちにいろんな単体テストを書くモチベになり良かったです。自分がなんとなく書いていたコードもこれは本当はtraitを書きたかったんだな、という理解が後からついてきました。

// Rust で書く chokudai search
// returns an action based on chokudai search
fn chokudai_search<F>(
    initial_state: &maze_state::NumberCollectingGame,
    beam_width: usize,
    beam_depth: usize,
    mut stop_condition: F,
) -> usize
where
    F: FnMut() -> bool,
{
    // keep track of all beams
    let mut beams: Vec<BinaryHeap<maze_state::NumberCollectingGame>> =
        vec![BinaryHeap::new(); beam_depth + 1];
    beams[0].push(initial_state.clone());

    while !stop_condition() {
        for t in 0..beam_depth {
            // split_at_mut to satisty the borrow checker
            let (left, right) = beams.split_at_mut(t + 1);
            let beam = &mut left[t];
            let next_beam = &mut right[0];

            for _i in 0..beam_width {
                if beam.is_empty() {
                    break;
                }

                // only peek because holding on to the state won't compile
                if let Some(state) = beam.peek() {
                    if state.is_done() {
                        break;
                    }
                }
                let state = beam.pop().unwrap();

                let legal_actions = state.legal_actions();
                for action in legal_actions {
                    let mut next_state = state.clone();
                    next_state.advance(action);
                    next_state.evaluate_score();
                    next_state.set_first_action(action);
                    next_beam.push(next_state);
                }
            } // end beam_width
        } // end beam_depth
    } // end beam_number/time

    // count down from the deepest beam to find a state
    for t in (0..=beam_depth).rev() {
        let beam = &mut beams[t];
        if !beam.is_empty() {
            return beam.peek().unwrap().get_first_action();
        }
    }
    panic!("beam should have a value to return");
}

終わりに

thunder本をPython/Rust/C++で実装した話を書きました。めちゃくちゃハマりましたし面白かったです。
こういうことをぜひ続けていきたいので、ぜひC++をRustにするお仕事やPythonをRustにするお仕事やC++をPythonにするお仕事があったらください!!

Discussion