山田将棋について

全体像

    極めてクラシカルな構造・アルゴリズムとなっています。

データ構造

    配列による盤駒表現、駒背番号制、利き数、
    飛び利き方向ビットの OR 値、
    利いている駒背番号ビットの OR 値 (64bit 変数の活用)、
    囲いへ誘導するための落とし穴表、
    玉位置からの距離に応じた評価値を納めた表、
    pinned と cover の概念、置換表、
    8 近傍利き位置を納めた表、8 近傍合法移動先を納めた表、
    など

アルゴリズム

    αβ探索、反復深化、局面が静かでない場合の探索延長、
    手調整した仮評価による手のオーダリングと前向き枝狩り、
    null move pruning、late move reduction、
    killer move heuristic、pass move、
    YSS 式指し手の反復生成、Crafty 方式の並列探索、
    反復深化による詰め将棋ルーチン
    root ノードでの簡易必死検出、
    leaf ノード付近での簡易一手詰み検出(今回新規導入)、
    予測読み(今回強化予定)、
    など

評価関数

    駒割、玉の安全度、囲い、盤上の利き、駒への当たり、大駒の働き、
    そっぽ、金駒へのひもなどの、手調整した評価値の線形和

未採用

    多重反復深化、影の利き、SEE、持ち駒の優劣表現、
    bitboard、実現確率探索、評価関数評価値の学習、など

特徴

    他の実装であまり事例を聞かない
    「8 近傍合法移動先を納めた表」について説明します。
    
    ここでの「8 近傍移動」は駒による遮りを考慮する必要のない移動、
    という意味であり、桂の移動を含みます。
    
    移動先とは、移動先絶対位置と、成・不成の情報です。
    
    例えば、
    ・▲1三桂を与えると、2一桂成、の 1 つ
    ・▲1一角を与えると、2二角成、の 1 つ
    ・▲1二銀を与えると、1一銀不成、1一銀成、2一銀不成、2一銀成、
      2三銀不成、2三銀成、の 6 つ
    が得られます。
    
    この表の値は、8 近傍移動における、
    ・駒種毎の相対利き位置表を引いての、移動先絶対位置の算出
    ・盤内であるか
    ・成れるか、成れないか、成らなければならないか
    ・「飛角歩は成れるときは成りのみ」という山田将棋の割り切り
    を事前に処理・判定したものとなっているため、
    プログラム動作中にこれらの処理・判定が不要となります。
    
    合法手生成速度で効果を確認しています。
    が、現在この表は大きく疎な実装となっていて、
    cache locality の観点で、課題があります。