FactorioでのB木

 (razberry.substack.com)
4 ポイント 投稿者 GN⁺ 2023-11-17 | 1件のコメント | WhatsAppで共有
  • Database Internals 読書会で B-Tree の章を読んだあと、データ構造をコードではなく Factorio の工場設備として実装し、概念を視覚的に検証した
  • BST はキーをソート可能な場合にのみ左右分岐が可能で、値が片側に偏ると検索効率が線形リスト並みに低下しうる
  • ディスクベースの保存では BST の再平衡コストと複数ページ読み込みが負担となり、B-Tree は1ノードに複数キーを入れることでこの問題を軽減する構造である
  • Factorio での実装では木箱と紫のフィルターアームでノードと比較演算を表現し、任意のアイテム整列順を定めて検索経路を作った
  • B-Tree 版はノードごとに 3個のキーと4本のポインタを使い、2段階で BST よりはるかに多くのキーを保持できるが、値の表現と手動ソートの問題は残っている

BSTとB木の違い

  • 二分探索木(BST) は各ノードが1つのキーを持ち、より小さいキーは左ノードへ、より大きいキーは右ノードへ送る
    • 例ではルートキー 8、左に 3、右に 10 から始まる
    • キー値の大小を比較できるソート可能な値でのみ動作する
  • 値が片側にばかり追加されると BST のバランスは崩れる
    • 最悪の場合 8 -> 10 -> 14 のような線形ソート済みリストとほぼ同じになる
    • ピボットとして 10 をルートに置き、8 と 14 を左右に配置する形で不均衡を直せる
  • ディスクベースの保存では BST は不利である
    • 再平衡を繰り返すとディスクとポインタを頻繁に更新する必要がある
    • 隣接ノードが異なるページに保存されうるため、1回の検索でも複数ページを読むことがある
  • B-Tree は1つのノードに複数のキーを持ち、キー数 + 1 本のポインタで子ノードを指す
    • 例の [17 | 24] ノードは、17 より小さいキー、17 と 24 の間のキー、24 より大きいキーを持つ3つの子ノードへ分岐する

Factorio内で実装した探索木

  • Factorio は工場建設ゲームであり、この実装では各ツリーノードをゲーム内の設備として表現した
  • まず単純な BST を作った
    • 各ノードは1つのキーを持つ木箱と、別のノードへつながる2つの経路を持つ
    • 素材の間にデフォルトの比較方法がないため、wood, coal, stone, brick, copper, iron, steel の順に任意のソート基準を置いた
    • 紫のフィルターアームが比較判定を担当する
      • 1本目のアームはアイテムが brick と等しいかを確認する
      • 2本目のアームは wood, coal, stone のように brick より小さいかを判定する
      • 3本目のアームは copper, iron, steel のようにより大きい値を振り分ける
    • 右上にはコンベヤベルトに誤って入ったアイテムを片付けるガベージコレクタも置いてある
  • B-Tree の実装では1ノードにさらに多くの設備が必要になる
    • 各ノードに 3個のキー、3本のフィルターアーム、3つの木箱、4本の子ポインタを置く
    • 同じ深さでより多くの情報を持てる
    • 2段階では BST は2個のキーを持つが、B-Tree は12個のキーを持てる
    • 3段階では B-Tree は48個のキーまで増える
  • 48個のアイテムを Factorio で手作業で選び、並べ替えたくはなかったため、よりよい値の表現方法を見つけるまでは B-Tree を空のままにしている
  • BST と B-Tree を並べて比較し、YouTube 動画もあわせて掲載している

関連記事

1件のコメント

 
GN⁺ 2023-11-17
Hacker Newsのコメント

  • 非効率な設計ではあるが、Factorioで計算機科学の理論を実装するということは、必然的に最適ではないやり方でプレイするという意味でもある
    FactorioはB-Treeを見せびらかすために作られたゲームではなく、ツールも結局はFactorioをプレイするように設計されている

    1. 2-3木、赤黒木、B-Treeのような自己平衡木の核心は、単一の木構造そのものではなく、自分で平衡を保つ部分にあるが、Factorioでは木が自分自身を再構成するようにはできないので、最大の特徴が抜け落ちている
    2. 最適化の観点では、インサータはベルトより遅い。ベルト1本あたりインサータを4個使っても毎秒約12個しか運べず、青ベルトは毎秒45個を押し出せる。ベルトだけを使う最適設計なら、毎秒45個で動作するスプリッターを使うべき
    3. したがって、スプリッターと計算機科学が交わる地点は、FactorioのスプリッターとBenesネットワークである。2入力2出力クロスバーだけで作ったネットワークを学ぶなら、https://en.wikipedia.org/wiki/Clos_networkから見るとよい。Benesネットワークは2入力2出力サイズのClosネットワークにすぎず、Closネットワークは5対7のような任意サイズも可能
      Factorioで探すべきメタは「混合ベルト」設計のようだ
    • より具体的な形として、1本のベルトが複数の素材をバランスよく載せて自分自身を周回する寿司ベルトがある
      ある設計は決められた比率で新しいアイテムを受け入れるだけで、別の設計は乱れたときに実際に再びバランスを取る。個人的にはこれが一番気に入っている: https://www.youtube.com/watch?v=7Gt5Zx0bsOQ
      この例はゲーム内の回路ロジックを使っているが、Factorioフォーラムには回路なしのセクションもある: https://forums.factorio.com/viewforum.php?f=202
      面白いのは、Factorioの「fish」オブジェクトが役に立たないジョークアイテムで、どこにも使われないため、ときにはnull値、ベルトが1周を完了したことを示すフラグ、デバッグツールとして使われることだ: https://forums.factorio.com/viewtopic.php?p=544302#p544302
    • コンベアベルト上にJSONを載せられるようにする「Scriptorio」のようなFactorio拡張があったらどうだろうと思う。JavaScriptやLuaの関数工場も併用する形だ
      そうすれば、挿入・検索するオブジェクトだけでなく、B-Tree自体もコンベアベルトとインサータで移動できる
      工場を通るコンベアベルトのループで再帰検索関数を書き、リーフに到達するまで木を1レベルずつ剥がしながら回し、ループを切って結果を出力することもできる
      標準的なJavaScriptというより、データフローに近い興味深い実行モデルだ。異なるコンベアベルト、インサータ、工場から同じ基盤JSONオブジェクトを複数の参照で指すようにして、「量子トンネリング」や「遠隔作用」を許すべきだろうか。有用かもしれないが、Factorioは伝統的に各物理アイテムが固有のアイデンティティを持つものとして扱うので、複数参照をサポートしないほうがより「現実的」かもしれない。あるいは「Quantum Tunneling JSON」技術を研究した後で、「JSON Reference Entangler Factory」でだけ複数参照を作れるようにしてもよい
    • Closネットワークの記事をざっと眺めてみると、Factorioでそのようなネットワークを作れるなら、ここに見えるような単純なニューラルネットワーク設計も可能に思える: [1]
      特定の位置に到着する資源密度に重みを付けて出力を変えるようなことも可能そうだ。ここに見えるメカニズム [2] を見ると、合流・分岐と3種類のベルト速度で密度重み付きの意思決定を作れそうだ
      [1] https://www.asimovinstitute.org/wp-content/uploads/2019/04/N...
      [2] https://wiki.factorio.com/Belt_transport_system#Splitters
    • 次は自己平衡まで実装できるか見てみたい。ボットがここで役に立ちそうだと思ったが、ボットに設計図を動的に建設させられるのかはよく分からない
    • だからFactorioはやらない。その程度の脳のリソースは人類のために使えるし、成果物を見せればソーシャルメディアの反応も得られる
      画面上の数字と引き換えに脳を要求するゲームは、自分のリストでは最下位だ。私は何か新しいことを学びたい
      パズル要素はあるかもしれないし、私たちがそれを面白いと決めることもできるが、勉強も面白いと決められるのではないかと思う

  • 見事な仕事だ
    「Database Internals」をブッククラブで読んでいて、今週がB-Treeを扱う第2章だったそうだ
    参考までに申し込みは締め切られているが、望むならDatabase Internalsを入手して、こちらの日程とノートに沿って「読み取り専用」で一緒に追うことはできる: https://eatonphil.com/2023-database-internals.html

  • 「二分探索木はディスクベースのストレージに向かない」という理由は、メモリ内ストレージにも当てはまる
    B-Tree のノードを 1 つ探索するほうが、二分木で同じ数のポインタをたどるより速い。もちろん実装の複雑さは増すが、C を使っているのでなければ、普通はツリーベースのマップを自前で実装することはないはず
    内部ノードにはより多くの項目を入れ、値はリーフにだけ保存する、といった変種も可能。マップではなく集合だけを作るのでなければ、という話だが。ここに隣接ノードへのリンクまで加えると、実質的にはスキップリストに近くなる

  • なぜよりによってここに Factorio コンテンツが出てきて、また 100 時間くらい吸い込まれたくなる衝動を起こさせるのか分からない。今年もすでに遊ぶべき良いゲームが多すぎる

    • 来年末ごろに大規模なバランス調整と Space Age 拡張パックが予定されているので、それまで待つのも悪くないかもしれない

  • これは全部スプリッターでもできるし、チェストやフィルターインサーターは不要そう。説明は良い

    • どうやるのか分からない
      単に出力を複数のラインに分けたいわけではない。チェストは、ここで 2 次元に配置された B-Tree の該当「ノード」に保存されたアイテムを表している
      動画を見る時間はなかったが、記事とスクリーンショットを見ると、インサーターに関連するロジックが付いていて、ツリーの「ソート済み」という性質を保つように、アイテムを適切な子ノードの経路へ送る構造になっている
      元記事のキー値の選び方を見ると、スプリッターで分けることも可能ではあるだろうが、記憶ではスプリッターはフィルターを 1 つしか受け取れないので、各分岐点ごとに複数個必要になる。その分岐点のアイテム数だけ必要ということだ。フィルターインサーターは複数のフィルターを許可するので、ここでは少し都合がよく、最初のスクリーンショットでも確認できる
      もちろん B-Tree 設計を丸ごと諦めて、n 個のスプリッターで n 個のチェストにソートすることもできるだろうが、それは面白くないし、元記事が意図したことでもなさそうだ
    • 各インサーターに複数のアイテムを割り当てている
      スプリッターのフィルターは 1 種類のアイテムだけを片側へ送り、残りをもう片側へ送る。しかしこの例は、複数の種類が片側へ行き、複数の種類がもう片側へ行く構造なので異なる
    • 複数のアイテムをソート・フィルタリングする必要がある。例えば最初のノードでは木材、石炭、石を左へ送り、金属を右へ送る必要があるが、スプリッターのフィルターはアイテム 1 つしかフィルタリングできない

  • Factorio がそんなに良いゲームなのか気になる。みんな良いと言うが、工場作りというテーマは少し退屈そうに見えるし、ゲームがあまりに反復的ではないかと心配になる

    • やってみる前は自分もかなり懐疑的で、同じ心配をしていた。ところが気づいたら 100 時間以上を費やしていた
    • 自分の知っている Factorio プレイヤーは全員、1,000 時間以上を注ぎ込んでいる

  • 本当に素晴らしいが、文章を書く人同士の話としては、文頭に大文字を使わないのはかなり気が散るように感じる

  • Factorio の回路システムで実装するのかと思っていた