きふわらべの中の人がコンピュータ将棋入門者向けにいい記事を書いている。かくいう私も彼の記事は以前からよく読んでいて結構ためになる。
合法手生成をライブラリ依存して作ると楽だけど,本職のプログラマは自分で書きたいのだろう。私も自作のものがある。
基本ルーチンとして
1.各駒の動かし方
2.味方の駒があるところには行けない
3.長い効きがある駒でも駒を飛び越えることはできない(桂馬を除く)
これが基本.
それに加えて
4.行き場のない駒を作ってはならない
これは歩,香車,桂馬の3枚にのみ適用される.動けないところに打つ行為と敵陣で動けない状態になる不成は禁止されている.
次は王手である.
もっとも簡単な表現をすると
5.王手を放置する行為をしてはいけない
6.自玉が王手となる着手をしてはいけない(自殺手)
これらはまとめると「着手後に自玉に王手がかかってる状態を作ってはならない」となる.
私も最初はこの定義で作成していた.実際に動かした後の局面を生成した方がコードは短くなる.(但し遅い)
7.打ち歩詰め
歩を打って敵玉を詰めることは反則である.大概実装が面倒なので実際に打った時に負け(評価値マイナス∞)の判定にしてる.正確には歩を打った直後の合法手が無いと表現する.
8.千日手
千日手は同一局面が4度繰り返す行為であるが,そのとき連続王手であれば王手側が負けになる.連続王手でなければ引き分け.(プロ棋戦では指し直し)
これは実装が面倒なのでうちでは実は未実装である.同一局面判定をすればいいのだがエレガントな実装はZobrist Hashを使うらしいってのでそのうち実装するかもしれない.着手後の局面図が必要なのでこれも動かした後の局面が必要になる.
まぁ,だいたい以上が差し手生成なんだけど,打ち歩詰めと千日手は指し手生成で非合法手も入ったままにして動かした後で判定するのが主流である.もちろん,そうでもないソフトもあるかも.
で,高速化の際にはどうしているかというと.
1.駒の動かし方と2.味方の駒の配置をBitboardという配列をあらかじめ生成して論理演算で生成するのが速いようだ.3.長い効きについても同様に上手に扱う手法がある.
王手については別に専用ルーチンを持つ方が強いソフトができる.特に王手回避手は別に作成することを強く勧める.これらは探索を非常に優位に進めることができる.
王手回避手については以下の4択である
1.王が逃げる
2.王手をかけている駒を取る(王で取る場合も)
3.合い駒を打つ
4.盤面上の駒で合い駒をする(移動合い)
両王手(王手をかけている駒が複数)のときは1.しか成立しないので比較的簡単である.
王手の駒を王で取るケースを1に含める方がアルゴリズム上簡単な場合もあり,その際は2.王以外の駒で取ると定義する.
あまり考えずに作成すると重複生成されたり不足したりすることもあるのでデバッグ注意の案件である.また,究極には速度が要求されるので無駄なループや分岐を作らないように気を配る必要がある.興味がある人は一度遊んでみるといい課題かと思う.
自信がない人は,将棋の前に五目並べやオセロから入るといいと思う.