stepney141 / dagaz-v2 Goto Github PK

現状

• Player, Zoneなどにおいて「ユーザーが入力する文字列 *Name」と「内部的に利用される数値 *ID」を二重に使っている
  • Name[] のインデックスから ID を生成する仕組み
• これは高速化を狙って全てをArrayで管理しようとしていたため
• しかしコードに不要な複雑さが生まれるので、この二重管理体制をやめたい

現状

• 合法手生成はv1よりも多少速くはなったが、まだまだ足りない
• 少ない工数で高速化できたらとても嬉しい
• v1は配列操作にTypedArrayを使って高速化を図っていたので、TypedArrayの導入で具体的にどの程度違いが出るのかを計測したい

現状

• ゲームのルールは TDesign クラスのただ一つのインスタンスによって管理される
  • 事実上のシングルトンパターン
  • dagaz v1 では2回以上インスタンス化していないかをグローバル変数で管理する仕組みになっており、名実ともにシングルトンだった
  • v2 ではグローバル変数自体を消したので厳密なシングルトンパターンではなくなったが、唯一の TDesign インスタンスが全てを管理すること自体は一緒
• 起動するとまず TDesign クラスをインスタンス化する
• ゲームのルール記述を読み込む時には TDesign インスタンスのメソッドを使う

懸念事項

• TDesign クラスの仕事があまりにも多すぎるのではないか
• 「クラスのメソッドでゲームルールの表現を動的に構築」「ゲームルールの表現の取得」についての機能が混在している

やること

• 機能を分割する
• クラスを使わずに書けないか考える

設計**

オリジナル

1. Dagaz is "a cross-platform solution that could be run anywhere, even on a smartphone."
2. Dagaz is "to make every user able to have full access to the open-source code of a program while it runs, so users could figure it out and develop their own games in the same way as they can in Zillions of Games, but more easily."

自分

• ドメイン知識に依存した最適化を用いてはならない
• できる限り広いレンジのゲーム類を取り扱えなくてはならない
• AlphaZeroやMuZeroのような「タスクを解く」ことに特化したシステムではなく、ZoGのような「エンドユーザーに使ってもらう」システムを目指す

前提

まず、改修すべき視点を分ける

1. 合法手生成器
2. ゲームルール記述部分
3. View部分
4. コードベース自体のメタ的改変 (ex. TypeScriptへの移行、Rustへの移植とwasm化)

目標

• Dagazをいわばコアライブラリとして扱い、別に書いた探索部・評価関数からDagazを呼び出して使う (libshogiに近い扱いで、Dagazはゲームの状態管理に徹する)→「Dagaz-Core」「Dagaz-AI」などのようにして大まかな単位のモジュールにするべきかもしれない
• Dagazに中将棋のルールを読み込ませ、中将棋AIを作る
• 詰め中将棋ソルバーを作る
• Dagazで小さいゲーム (ex. 3三将棋, ミニチェス) のルールを記述し、ゲームを解く

改修すべき点

合法手生成器

• invariantのシステムは遅すぎる→根本的な方式変更が必要
• 「ゲームルールをどうパースするか」によって動作方式が左右されるので、ゲームルール記述部分と同時に書き換える必要あり
• トランスポジションテーブルの実装: 現行のzobrist.jsでは不十分

ゲームルール記述部分

• 言語内DSLによるゲームルール記述システムの整備
• Ludiiを参考にしたルールの定式化→論文を読む

メタ的改変

• Rustへの移行とwasm化
• TypeScriptの導入

• 盤面における「場所・マス目・交点」などの位置を表す語彙を、position から location または cell にする
• 理由：「局面」を意味するチェス用語 "position" と衝突する

小目標

• 探索アルゴリズムの理解
• 統計的手法(機械学習含む)の理解

中目標

• 中将棋AIの完成
• 詰め中将棋ソルバーの完成, 未解決の詰め中将棋の求解
• GGPとしてのDagazの完成

大目標

• 大局将棋をソフトと指したい
• Dagazを使って定量的な文化進化論的将棋史の研究
• Dagazを用いたフェアリー詰将棋ソルバー

対象になりそうなもの

• Zobrist Hash (zobrist.ts)
• (もし導入するのなら) BitBoard

なぜ必要か

• JavaScript のビット演算子は数値を32ビット整数に変換し、それを超える範囲は切り捨てられる [1][2][3]
• このため、正しいハッシュ値を求めることが出来ない場合がある [3][4]
• Zobrist hash における解決策の例
  • 複数個のハッシュ値を組み合わせて使う [3]
  • TypedArray を使うという解決策 [4]

関連情報

• [1] https://developer.mozilla.org/ja/docs/Web/JavaScript/Reference/Operators/Bitwise_AND
• [2] https://qiita.com/uhyo/items/f9abb94bcc0374d7ed23#javascript%E3%81%AB%E3%81%8A%E3%81%91%E3%82%8B%E6%95%B0%E5%80%A4%E6%BC%94%E7%AE%97
• [3] https://www.chessprogramming.org/Zobrist_Hashing#Lack_a_True_Integer_Type
• [4] https://stackoverflow.com/questions/24813487/implementing-zobrist-hashing-in-javascript

現状

• チェス系ゲームにおいて、自殺手の判定は地味にコストがかかる
• チェスや将棋では「自殺手を含む擬似的な合法手」を生成する仕組みを用意し、「(千日手を考慮しない)本当の合法手」と使い分けることによって計算量を削減している

懸念

• どんな行為が自殺手となるかはゲームごとに千差万別なので、任意のゲームについてpseudo legal moveの判定ロジックを分けるのは難しいかもしれない

参考

• https://www.chessprogramming.org/Pseudo-Legal_Move
• https://yaneuraou.yaneu.com/2016/02/28/pseudo-legal%e3%81%ae%e5%88%a4%e5%ae%9a%e3%81%8c%e3%83%9e%e3%82%b8%e3%81%a7%e9%9b%a3%e3%81%97%e3%81%84%e4%bb%b6/
• https://peterellisjones.com/posts/generating-legal-chess-moves-efficiently/

各種ボードゲームエンジンの実装を参照してDagazの参考にしたい

将棋ソフト(やねうら王)

• 指し手をenumおよび構造体として表現(参照)
  • やねうら王では基本的にclassを使わず、代わりに構造体や「enumでデータを表し、グローバルで定義したメソッドで操作する」という手法を使う(参照)
  • 最適化のためらしい。stockfishの影響？(参照)
  • ある意味において関数型チックな書き方と言えるかもしれない(?)
• 合法手生成器は「構造体テンプレート」として実装
  • 中では types.h で定義された constexpr Move make_move() （駒の移動元座標・移動先座標をもとに新しい指し手を作って返す関数）を参照して指し手を生成している
• 指し手をいくつかの種類に分類し、それぞれについて指し手の生成ロジックを細かく分けている
• ドメイン知識依存の最適化が非常に多いことが特徴的

new-model-kernel

• 指し手をclass（オブジェクト）として表現
• 指し手リストを「指し手オブジェクトの配列」として表現
• 合法手生成器は「局面オブジェクトのクラスメソッド」として実装
  • TMoveContext オブジェクトで言語内DSLモドキを作り、これを使ってゲームのルールを記述・実行する
    • ZRFを TMoveContext オブジェクトで抽象化しているという感じの実装
  • 実行すると TMoveContext オブジェクトの中で新しく指し手オブジェクトの雛形が作られ、言語内DSLのルール記述に沿って指し手が少しずつ書き換えられていく
  • DSLの実行が完了した時点で次局面への指し手オブジェクトの生成が完了する
  • このプロセスを各種の駒について実行し、出来上がった指し手オブジェクトを、局面オブジェクトがメンバ変数として持っている指し手リストの中に順次突っ込んでいく
  • 局面オブジェクトの盤面更新メソッドに指し手オブジェクトを与えると、局面オブジェクトの持っている盤面データを書き換えて新しい局面に更新してくれる

Ludii

current status

• 元からあったQUnitによるユニットテストを流用
• ぶっちゃけ使いにくい
  • HTMLファイルを作らないといけない
  • CLI実行がしにくい、CIがつらい
  • 参考: https://krymtkts.github.io/posts/2019-03-21_want-to-run-qunit-in-cli

roadmap

high priority

• jest辺りに移行する
• CIを整備 (ref: #5)

low priority

• zrf-based-kernelのテストのjest化
• new-model-kernelのテストのjest化

現状

• Dagazでは、v1/v2ともにプレイヤー間のターン順序を明示的に設定・変更する機能を設けていない
• boardgame.ioでは、ターン順序を柔軟に設定できる機構が備わっている

懸念点

• このシステムは、boardgame.ioにおけるターン制周りの柔軟な機能あってのものなのではないか

参考

• https://boardgame.io/documentation/#/turn-order

Why Rust?

• JavaScript is too slow to develop a strong AI

Why not Rust?

• "The WebAssembly technology, in turn, was not suitable for me, for some other reasons. My goal was to make every user able to have full access to the open-source code of a program while it runs, so users could figure it out and develop their own games in the same way as they can in Zillions of Games, but more easily."

Why TS?

• To get support from type annotations for efficient development

アイデアの概要

• コンピュータ将棋ソフトウェアの場合、ドメイン知識の活用によって最適化を図っている
  • 駒や着手の種類について処理を共通化しない（判定などでオーバーヘッドが発生するため）
  • 駒の種類や着手の性質ごとに少しずつ違う処理を用意して、無駄のない最小の処理に留める
• v2でもこれを模倣し、駒種ごとにコードを動的生成できたら速くなるのでは？

参考

• http://labs.yaneu.com/20090905/

• ゲームのルールを簡便に記述する機能が整っていない。extensionシステムもDagazの内部構造を熟知していなければ書くことができず、利便性は低い
  • boardgame.ioを参考に、宣言的なゲームデザインの記述を目指す
    • 特にPhase/Stage/Eventの各概念は、ゲームデザインの抽象化を考える上で大きな指針になる
    • bgioのコンセプトは「純粋関数を使って宣言的にゲームのルールを記述し、Reduxでゲームの状態を管理する」こと。Dagazでそのまま真似ることは難しいが、エッセンスは取り込んでいきたい
  • ゲームデザインの概念をもっと細かく分割して、ゲームのルールを書きやすくする
• extensionシステムは遅くて非効率。より書きやすくパフォーマンス面で効率のいいプラグインシステムを模索したい
• underscore.jsを始めとして、ES5時代の読みにくく書きにくいコードが多い
  • グローバルスコープに名前空間オブジェクトを作り、そこをアダプターにしてIIFEで書かれた各モジュールが接続されている
    • ES Modulesで書き換える
  • underscoreは可能な限り排除。ES2015以降の構文を積極的に導入して可読性を上げる
  • TypeScriptへの移行はまだ無理。現時点での優先順位はかなり低い
    • JSDocで型を付ける方が先
• 状態管理がまともにされていない
  • 多数のメンバを内包したclassたちが互いに絡み合い、グローバル名前空間の上で副作用のワルツを踊っている
  • (関数型|宣言的)プログラミングのエッセンスを導入し、参照透過性の導入と副作用の局所化に務める
    • パフォーマンス面は課題のひとつ
  • とりあえず、OOPと関数型を両立させているというScalaから何かヒントを得たい
• ControllerとViewが巨大かつカオス
  • C<-->V 間が密結合（VとCが実質的に同化している）
    • V, CはReactなどのFWに対応できる設計ではなく、完全にDagazのMVCだけでドメインロジックからフロントエンドまでの全てが完結している
  • ModelとViewをちゃんと分割したい。関心の分離を徹底する
    • ぶっちゃけフロントエンドのデザインパターンがよく分かっていない... 改修に移る前にデザインパターンに対する直感を生やす必要がある
    • boardgame.ioは「盤面状態の生成と管理」にReduxを使っているが、Dagazでは少なくともModel部分はVanilla JSで書きたい...
    • 幸いにしてModel部分は割と独立している（ViewがModelにべったり張り付いている形）なので、Model部分のラッパークラスを作ってViewから参照させる形が良さそう
• View部分をもっと汎用的にしたい
  • 現在は駒と盤の画像を読み込んだ上でゲームデザインと一緒に描画座標を指定、canvasで描画を行っている
  • しかしHTML/CSSを使った盤駒も読み込めるようにしたい
  • Reactなど現代的なFWで使いやすくすることは大前提
  • 要するに読み込んだ画像を元に操作可能な盤面を表示できればそれでいいんだから、canvasにこだわらずともDOMとして表現してもいい。逆に言えば、それができないならばcanvasでなければならないかもしれない
  • いずれにしろcanvas周りは外部ライブラリ使いたい
• バージョンの振り方を固定化する
  • github.ioの方はバージョン振ってあるけどDagaz本体には振られてない
• Z2Jはレガシーだが、既存のDSLを変換できるという点で大きなメリットがある
  • pros: 過去の資産を流用できる・他システムとの互換性を持つこと自体がDagazの強みになりうる
  • cons: めちゃめちゃ遅い・可読性低い・ZRF (ZoG) の仕様上の制約やバグをそのまま Dagaz に埋め込むことになり、これをカバーするのは辛い
  • 変換機構をもっとマシなものにする必要はあるが、「何らかのDSLからJSへのトランスパイル」自体はオプションのひとつとして残してもいいのではないか
    • ZRF自体が欠陥のカタマリなのでやるなら他のやつ（Ludii GDLが第一候補）
    • 作るとしたら peg.js (peggy.js) とかのパーサジェネレータを使うのが良さげ

現状

• v1からv2への最も大きな変更点として、ゲームルールの記述方法を「Z2JでZRFから自動生成されたJSコードと拡張機能の組」から「JSの内部DSL」にすることが挙げられる
• しかし、現在の TMoveContext classは機能が少なく、様々なゲームを表現するには機能が不十分
• 関連: #3

背景

Dagaz では開発初期から Underscore.js を使用していた（lodash に乗り換えていないのが、らしいと言えばらしい）。
これには関数型プログラミングの実践という目的に加え、IE11 のシェアが大きかった当時は ECMAScript の新機能の導入には慎重にならざるを得なかった事情もあった。
しかし時は経ち、今や Underscore の多くのメソッドは ECMAScript の機能として取り込まれていたり、簡易的に自作できたりする。そもそも、今や派生プロジェクトの lodash の方がずっと便利かつ高速だったりする。
こういったわけで、理想的には Underscore.js を全て排除したい。

元々のソースで使われていたメソッド

• _.each()
• _.groupBy()
• _.keys()
• _.map()
• _.max()
• _.range()
• _.indexOf()
• _.isArray()
• _.isUndefined()

懸念

• range は素直に実装するととても遅くなる。探索中・指し手生成中によく呼び出されるのでここが遅くては困る
• groupBy は素直に実装するとやたら長ったらしくなる。ただし一度しか呼び出されないので、多少遅くてもそんなに問題はない

解決策

• range をそもそも使わない設計に変える
• (range が最も呼び出されるのは盤上の全 location に対して全探索をするときなので、piece list の導入によって解決できそう)

ゲームの分類

• 人数
  • 2人が基本 (3人以上も当然ありうる)
  • プレイヤーの存在しない0人ゲームも存在する (ex. ライフゲーム)
  • パズルやクイズは1人ゲーム (ex. ソリティア)
• 利得の合計
  • ゼロ和 or 非ゼロ和
• 有限 or 無限
  • 有限なら、ゲームが終了するために満たすべき条件が与えられている
  • 無限ゲームの実装は現実的に難しい（やるとしたら一時停止ボタンを付けるとかが必要）
• 確定 or 非確定
  • ゲームの進行が確定的ではない (≒ランダム性が存在しない or する)
  • 着手が (局面, プレイヤーの選択) => 局面 という純粋関数ではないものとも解釈できる？
• 完全情報 or 不完全情報
  • ゲームの局面状態や他プレイヤーの行動など、全ての情報がプレイヤーに開示されている or いない

ボードゲームフレームワークは、以上のように表現される各要素を再現・実装できなくてはならない

ゲームの定式化

ゲーム木としての解釈

• 各盤面：ノード
• 着手：エッジ
• ※同時手番ゲームはどうやって表現する？

ゲーム情報学的な解釈

• ゲームにおける対象を表現するためのデータ構造と、対象を変化させるためのアルゴリズムの複合体とみなす
• データ構造：ゲームの状態(state) := 局面(position)
  • 局面 := 特定時刻におけるゲームの状態を過不足なく表現する情報の構造
  • どんな情報を「局面」として管理すべきかはゲームによって様々
  • 盤面の駒/石の配置、 手番、持ち駒、アゲハマ、etc...
  • 厳密には、開始からの局面の履歴もゲームの進行に必要である(千日手やコウの判定に必要)ため、特定時刻の局面だけで全てが説明できるわけではない
• アルゴリズム：各種手続きを組み合わせる
  • 合法な着手の列挙：(現在局面) => (可能な着手の集合)
  • 着手の合法性の判定：(現在局面, 着手) => (合法 or 非合法)
  • 勝ち負けの判定：(現在局面) => (勝ち or 負け or 未決着)
  • 次局面の生成：(現在局面, 着手) => (次局面)
  • 前局面の生成：(現在局面, 着手) => (前局面)
    • 実装によっては不要
    • 巨大なゲームの場合：一回の着手による局面の変化は微小→局面をthe single source of truthとして着手の度に書き換えていく方が効率的（前局面を求める手続きによって元に戻す）

Dagaz v1における解釈

• 盤面状態をdesignとboardに分ける
  • design：クライアント（ユーザー）が記述した情報をもとに生成・管理される、ゲームの情報
    • まずdesignクラスをインスタンス化し、メソッドを叩いてゲームの情報を設定する
    • designに含まれる情報：
      • 盤上の移動方向・マス目の位置
      • プレイヤーの情報（名前、移動方向の回転対称性）
      • move modes
      • 盤上の特殊エリア
      • 駒の名前・価値・動き
      • 盤面の初期状態
      • プレイヤーの着手順番
      • ゲームの挙動に関するオプション
    • designのメソッド
      • 新しい駒インスタンスの生成
      • マス目情報をIDから文字列に変換
  • board：ある時点におけるゲームの盤面状態
• API
  • games.model.getDesign() で design を初期化
  • design.getInitBoard() で board を初期化
  • board.generate() で board.moves: Array を生成
  • board.apply(move) で新しい board を生成

boardgame.ioにおける解釈

• 盤面状態をGとctxに分ける
  • G：クライアント（ユーザー）が記述する局面状態
    • TypeScript実装ではany型→局面状態はどんな形式にして扱ってもいい
    • チュートリアルのティクタクトーのように、マルバツの情報を持つマス目の配列としてもいいし、チェスならSGFやFENの文字列で盤面を表現してもいい
    • Gを変更するのがmove（着手）
  • ctx：フレームワークの中で生成・管理されるゲームのメタ情報
    • TypeScript実装ではちゃんと型が決まっている（ユーザーが好き勝手に形式を決めるようなものではない）
    • ユーザーはctxを書き換えることができないが、ctxを参照することはできる
    • ctxに含まれる情報：プレイヤー人数、現在が何ターン目か、現在の手番プレイヤー、プレイする順番、ゲーム終了後の勝敗結果、etc...
    • ctxを変更するのがevent
  • 盤面状態をGとctxのふたつに分けることにより、 ユーザーが考えるべきことを削減している
• 着手：move: G => G：現在局面から次局面への写像（純粋関数）
  • immer.jsを使っているため、return GをせずGを直接書き換える形でmoveを記述することも可能（内部でよしなに変換してくれる）
  • ただし、ひとつのmoveの中で、return GとGの変更とを同時に行うことはできない
• ゲームのルール記述
  • ゲーム名(必須)
  • ゲームの初期状態生成(必須)：setup: (ctx, setupData) => G
    • ctxを参照することで、例えばプレイヤー数などの情報によって初期状態が変化する場合に対応する
  • moveの定義(必須)
    • 着手の名称
    • move: (G, ctx, ...args) => G：現在局面から次局面への写像（純粋関数）
    • 着手をやり直し可能か
    • クライアントから実行可能か
    • 何手目でも実行可能か
    • プレイヤーが把握できる盤面情報の制限：playerView: (G, ctx, playerID) => G
  • turnの定義
    • turnの名前
    • turnの順番
    • turnの最初に実行する処理：onBegin: (G, ctx) => G
    • turnの最後に実行する処理：onEnd: (G, ctx) => G
    • turnの終了条件(これがtrueになったら現turnを抜ける)：endIf: (G, ctx) => true
    • moveの最後に実行する処理：onMove: (G, ctx) => G
    • 一回のturnの中で実行できるmoveの数の下限：minMoves: number
    • 一回のturnの中で実行できるmoveの数の上限：maxMoves: number
    • そのturnにおいて着手できるプレイヤー？
    • stageの定義
      • stageの名前
      • そのstageにおいて有効なmoveの定義
      • このstageの終了後、次に実行されるstageの名前：next: 'nextStageName'
  • phaseの定義
    • phaseの名前
    • phaseの最初に実行する処理：onBegin: (G, ctx) => G
    • phaseの最後に実行する処理：onEnd: (G, ctx) => G
    • phaseの終了条件(これがtrueになったら現phaseを抜ける)：endIf: (G, ctx) => true
    • このphaseの中だけで有効なmoveの定義
    • このphaseの中だけで有効なturnの定義
    • ゲーム開始時にこのphaseから始めるか否か
    • このphaseの終了後、次に実行されるphaseの名前：next: 'nextPhaseName' | (G, ctx) => 'nextPhaseName'
  • プレイヤーの最小人数
  • プレイヤーの最大人数
  • ゲームの終了条件：endIf: (G, ctx) => obj
    • この返り値は ctx.gameover から参照可能
  • ゲーム終了時に実行する処理：onEnd: (G, ctx) => G
  • ゲーム内の全てのmoveをやり直し不可能にするか
  • マルチプレイ時に状態の差分のみをJSONで送受信するか否か

Stockfish系の将棋ソフト類における解釈

• e.g. やねうら王
• 盤面状態をPositionクラスとBitboard構造体で持っている
  • Position: ゲーム進行全般に関する状態を管理
    • 一度しか作られず、盤面を進めたり戻したりする際は部分的にのみ更新する
    • 内部的にBitboardを呼び出す
  • Bitboard: 局面の状態のみを管理

Ludiiにおける解釈

• the "ludemic" approch

所見

• こうして考えてみると、ZRFのアプローチはあまりにも命令的だったのではないか
• DagazはZRFを出発点にしたことによって、ZRFの弱点をそのまま受け継いでしまった
• boardgame.ioにおける宣言的なゲーム記述の優位性
  • 汎用的であるがゆえに少々とっつきにくくはある
  • でも定式化がめっちゃスマート
• boardgame.ioはルール記述・Viewの実装にほぼ制約がないが、プログラミングの知識がないと使えない
  • 自由であるからこそ自分でプログラミングしなければならない部分が多い
  • 「ターン制」という概念に焦点を当てた抽象化
  • 「ターン」「フェーズ」「ステージ」という『ゲームの構造』に則ってゲームの状態遷移を記述する枠組みを提供し、ゲームの詳細なルールの記述はプログラマに任せる
  • ターン制という『ゲームの構造』に乗っかることによって、プログラマがゲームを実装しやすくなる
  • あくまでも『フレームワーク』であり、プログラマの開発を支援するためのもの
  • bgioが提供するのは、ゲームの全体的な流れをターン制（状態遷移）という普遍的な骨組みの上にドメイン知識を肉付けして得られるシステムとして記述する仕組みであり、ルールの記述は完全にプログラマの自由（流体力学で言うところのオイラー型）
  • 状態遷移に主眼を置いていることから、ゲームの表現力は「石」「駒」「カード」など使う道具によって左右されないし、人狼のようなそもそも道具を使わないゲームにも対応できる
• ZRF/Ludiiなど、既存のGGPエンジン/GDL文法は、ゲームの全体的な流れを各ゲームのルール（ドメイン知識）という流動的な要素の集合として記述する**であり、提供するのはルールを記述する仕組みである
  • ターン制という「構造」は、各ゲームの「石」「駒」「カード」といった要素の織り成すダイナミクスの中に捨象される
  • ZRFは「ひとつひとつの駒の挙動」に注目してルールを記述させる（流体力学で言うところのラグランジュ型）
  • 「構造」に焦点を当てていない分、bgioのある種極端なほどの汎用性には欠ける
• Ludiiはルール記述・Viewにある程度の制約があるが、プログラミングの知識がなくても使える
  • ZRFなど既存のGame Description Languagesもこの路線
    • GDL自体、どこかで記述の制約がどうしても生まれてしまう概念であるといえる
    • Class Grammarの仕組みはこの制約を最小化するためのもの
  • プログラマの開発を支援するというよりも、ゲームデザイナーの制作を支援するもの

参考文献

• ゲーム計算メカニズム : 将棋囲碁オセロチェスのプログラムはどう動く(コロナ社, 2010)
• https://speakerdeck.com/qsona/game-model

背景

• 現在の Dagaz の盤面構造は Mailbox パターンを採用している
• しかし、Mailbox パターンはパフォーマンス面での問題が見られる[1]
• Mailbox パターンと PieceList 機構[2]の併用で大きく高速化できたという報告がある[3]

参考

• [1] https://www.chessprogramming.org/Mailbox
• [2] https://www.chessprogramming.org/Piece-Lists
• [3] http://talkchess.com/forum3/viewtopic.php?f=7&t=76773#p885878

概要

• コマンドひとつで手軽にちゃんとしたベンチマーク結果を知れるようにしたい
  • boardgame.io が benchmark.js を使ったベンチマークスクリプトを整備している
• perft スクリプトは整備済みだが、一度実行するだけで結構な時間がかかるし、やっていることは統合テストに近い
• もっと単体テストに近い、細かい粒度でのパフォーマンスを計測したい

現状

• benny は導入済み
• benchmark.js は機能こそ十分だがメンテが止まっており、TypeScript 対応も微妙らしい
  • bdgm.io も rollup で src をバンドルしてから babel-node で TS を JS にして動かしている
  • どうせ知りたいのは JS にした時のパフォーマンスなのだから別にベンチマークライブラリ自体が TS 対応している必要はない、という考え方もできる

currently available

• chess
• russian draughts
• international draughts
• english draughts

required to support

• othello (reversi)
• Go (19x19)
• mancala
• imperfect games (e.g. Dark Chess)
• randomized games (e.g. chess960)
• simultaneous games (e.g. Apocalypse)
• games that a player sets up the initial position as they like (e.g. sittuyin)
• games that a player can modify the board topology (e.g. Magyar Dama, Platform Chess)

games in AG20 article

ref: https://www.abstractgames.org/dagaz.html

• Rithmomachia
• Russian Checker
• Frisian Checker
• Atari Go (ja: ポン抜き囲碁)
• Oware
• Russian Column Checker (Bashni)
• Renju
• Morabaraba
• Dark Chess (Kriegspiel)
• Yonin Shogi (ja: 四人将棋)
• Dark Yonin Shogi (ja: 暗闇四人将棋)
• Gala
• Surakarta
• The Royal Game of Ur

現状

• 1つの盤面状態は、1つの TBoard オブジェクトで表される
• つまり新しい盤面状態に遷移するたびに、新しく TBoard のインスタンスが生成される

懸念

• 新しくインスタンスを生成する方式は無駄？
  • 「ある程度以上の複雑さを持つゲームでは一度の状態遷移時の変化量は部分的になるので、毎回新規に状態を生成するのは無駄」みたいな話がある
  • ※オセロとか囲碁とかはどうなんだ？
• ナイーブに局面の全列挙をする場合、探索深さ n に対して到達局面の総数は n^2 から n^3 程度のオーダーで増加していく
  • 当然、TBoard が作られる回数もそのオーダーで増えることになる
• そもそも、データを操作するためのメソッドを状態に含めるのは余計な計算量とメモリ領域を費やすのでは？

するべきこと

• 以下の実装を比較する
  1. 現行方式
  2. TBoard をクラスではなくオブジェクトリテラルで表現する方式
  3. 現行方式をインクリメンタル更新にしたもの（＝クラスを使う）
  4. TBoard をオブジェクトリテラルで表現し、インクリメンタル更新にしたもの（＝関数で状態を操作する）