羊の人工知能研究 ~将棋AI開発の日々~

将棋、リバーシのAIプログラミングを中心にその開発過程及び記録を頑張って更新していきます。

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

置換表の実装とハッシュの基礎

 今回は将棋では必須とも言える置換表についての更新です。

 将棋の盤面において、『王』等を動かして、前回の位置に戻したりしていると、無限に同じ手を繰り返すような場合が考えられる。また、AIを考えるときに、今までに探索した盤面が出てくると無駄な処理になってしまう。そこで、置換表という方法を使い一度探索した盤面は置換表に登録しておき、今後その盤面が出てきた場合は前回探索したときに評価を返す仕組みを作ります。

 置換表にはハッシュという方法を使用し実現します。ハッシュには様々な種類が存在しますが、今回はチェインハッシュによる置換表の説明をします。←図23参照



図23:チェインハッシュの構造


 ここで、ハッシュ法というのは、探索に用いられるデータ構造の一つで、特徴としては、データの個数によらずに挿入、探索、削除の操作を実質的にO(1)つまり一定時間で行える優れています。原理としては、キー値を、データが格納される位置(配列の添え字の値)に直接関連付けてしまうというものです。ハッシュの簡単な例を次に示します。

 大きさ11のハッシュ表でキー値は格納する値を11で割った余りとします。そこに例えば7、23、68を格納すると次の図24のようになります。



図24:ハッシュの構造


 上のように格納する値7,23,68をそれぞれ11で割った余りはそれぞれ、7、2、1となりそれぞれその場所に格納される。そうすると探索する際に、例えば23が格納されているか調べてみる。キー値はデータを11で割った余りなので、ハッシュ番号1をを参照する。すると23が格納されていることがわかる。

 しかしココで、34を格納する場合キー値は1になるので23とキー値が重複してしまいデータが上書きされてしまう。これを衝突という。そこで先ほど紹介したチェインハッシュというデータ構造を使う。チェインハッシュは連結リストをハッシュの大き分だけ使ったような構造で、衝突が発生した場合リストの最後尾にデータを追加するような構造になっている。探索する場合は、キー値を計算しポインタでつながれたデータを順番に探索していくような手順になります。


 将棋の話に戻しますが、この置換表を将棋に実装する場合、キー値のとしては盤面の駒の位置と持ち駒からなるべく衝突が起こらないような計算方法(計算時間のかからない単純なもの)を考える必要がある。

 この置換表の実装が完了するとようやくAIのほうに取り掛かることができる。しかし、この置換表で手を抜くと強いAIは期待できないので実装は慎重に行いたい。



次回予告:探索による思考



↓現在2つのランキングに参加しています↓

クリックしたら投票されるみたいなので、明るい一票をお願いします(m。_。)m
スポンサーサイト

コメントの投稿

URL
コメント
パスワード
秘密
管理者にだけ表示を許可する

トラックバック

トラックバックURLはこちら
http://hitsujiai.blog48.fc2.com/tb.php/15-5ead1799
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。