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

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

スポンサーサイト

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

つ、遂にAIの基本完成

 つ、遂に将棋の基本AIが完成しましたヽ(●´ε`●)ノ 本日までに追加した機能としては、以下の2つです。

①王手を判定する
②合法手を生成する


 ①の王手を判定するについては、『王の座標に移動できる敵駒があるか?』という考えのもと、そのままコーディングした。王(玉)の座標についてはこの盤面の仕様で、盤面は駒のポインタ配列でできていて、それぞれの駒がどの座標にいるかという情報を持っているので、盤面を初期化するときにこの変数のポインタを保存してあるので、ポインタを参照することで座標は簡単に知ることができます。まぁ分かりにくいと思うので↓を参照。。。

//駒構造体
typedef struct KOMA{
char kind;//種類
char xy;//座標
bool nari;//成り状態
char owner;//所有者
}KOMA;

//盤面クラス
class BOARD{
private:
KOMA *table[121];//駒のポインタテーブル
KOMA koma[121];//上下左右に厚さ1の壁を設けている
char *ou_xy[2];//王の玉の駒構造体の座標へのポインタ



(省略)
};


言葉では説明が難しかったので簡単なソースを付けてみましたが言いたいことが分かってもらえたでしょうか?王は盤面から排除されることがないので、最初にこのようにポインタとしておくと、移動しても簡単に王の座標を知ることができるのです。これにより、この王の座標に移動できる相手の駒を探すことにより王手かどうかを判断することができます。


 次に②合法手を生成するについては、まず合法手とは、ルールに従って移動できる手及び置ける手です。また、王手がかかっている場合は王手を回避することのできる手が合法な手です。
 王手がかかっていない場合は、お得意関数ポインタ配列を使って『A座標の駒はB座標に移動できる』『K駒をB座標に置くことができる』というものを全てリストアップする関数が既に用意してあるので、そのリストを連結するだけです。
 王手がかかっている場合については、王手がかかっていない場合についてその中で『その手を打った次の手で相手に王が取られないか?』について判断し、王手がかかっていない場合が回避できた場合なのでそれをリストに追加していくだけです。

 この辺については、まだまだ改善する必要があると思うがこの2つの関数により、探索の中で合法手が存在しない場合は『詰み』と判断できるようになったので、

ようやく一応のAI完成

となった。




次回予告:詰め将棋の基礎
に入れたらイイな~頑張ります。。。



↓現在2つのランキングに参加しています↓
現在18位
現在2位
スポンサーサイト

将棋の現状

 将棋の更新を最近していなかったので現時点の進行状況の報告ということで・・・。今のところ、猿になるかコンピュータになるかが決まるAI部分に着工しており、AIの基礎の部分はリバーシの時に使っていたPVS探索アルゴリズムを採用し、ハッシュ(置換表)を使って将棋特有の大量重複する枝をバッサバッサ刈っています。

 AIの指標として重要な探索速度は今のところ評価関数が駒特だけということもあると思いますが、AIを前提に考えたデータ構造で最初から設計したおかげで約2500K・node/secというWZebraもビックリの恐ろしい数値を記録することができました。

 データ構造としては関数ポインタ配列をかなり多用した構造になっており、移動できるかのチェック成ることができるかのチェック移動手の生成等全てをこれで行っています。

 今後の予定としては、基本的な探索速度の上昇を目指しMoveOrdering(αβにおける探索順の並び替え?)、その他詰み詰めろ必死王手の手の生成王手回避の手の生成等の終盤に関わる部分から作っていこうと思っています。それが完成すると、中盤及び評価関数、定石に入っていく予定です。探索方法も単純なPVSではまずいと思うのでそれは追々・・・・。


次回予告:終盤のアルゴリズム



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

おかげさまで現在プログラミング部門のランキング2位を死守しておりますm(。_。;))m

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

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

 将棋の盤面において、『王』等を動かして、前回の位置に戻したりしていると、無限に同じ手を繰り返すような場合が考えられる。また、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

打ち歩詰め&Undo機能


今度こそ
ルール完成


 前回の更新で完成していなかった『打ち歩詰め』が完成しました。打ち歩詰めチェックの手順としては、手持ちの歩で相手に王手をかけた場合その歩を王以外の駒で取ることができれば打ち歩詰めではないので置くことができます。王以外の駒で取ることができない場合、王が逃げる場所があれば>打ち歩詰めではない逃げ場所がなければ最終的に打ち歩詰めとうい判定になります。

 実際に打ち歩詰めを行ったときの実行画面を以下の図20に示します。



図20:打ち歩詰めの実行画面


 実際にあらゆるパターンで打ち歩詰めのチェックをしたわけではありませんが、一応完成ということで(汗


 あと今回の更新で新たに追加したUndo機能については、毎回駒を移動したり打ったりした情報をSASHITE構造体にまとめスタックにプッシュしていき、undo関数が呼び出されたときにスタックの情報をポップし元に戻す方法をとっています。←図21参照



図21:Undo機能


 今まで実行画面を見せてきましたがこの実行画面についてのコマンド入力方法の説明が抜けていました(人・∀・)


というわけで突然
コマンド入力方法の説明


・「○手 > 」 とプロンプトが表示されている場合はカンマ形式で『77,76』という風に入力します。この意味としては、座標7七の駒を座標7六に移動するという入力になっています。

・手持ちの駒を打つ場合は『0,76』という風な感じに入力します。大体分かるかと思いますが、手持ちの場合は最初の値を0にし、次の値にどこに打つかを入力します。また、最初の値を0にした場合、「1:角 2:飛 3:香 4:歩 5:桂 6:銀 7:金 > 」という感じのプロンプトが表示され、どの駒を置くかを聞かれます。該当する番号を入力するだけです。

・Undoについては入力を「0,0」とするとUndoされます。



次回予告:置換表を実装



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

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

ルール完成!?

ルール完成!!!?


 一応現在のところ前回の予告通りの『持ち駒の利用』『成る』、の他に『二歩』と『打ち歩詰め』のルールを実装することができました。しかし、王を取る(詰む)と終了というルールをまだ実装していないので、それだけ実装すれば基本完成かな??(イヤ勘違いしてました・・まだ打ち歩詰め完全に完成してません↓↓↓)

 あと現在CUIで実現しているため、成った状態を表現する方法に悩んだ・・・。『歩』は『』でいいが、『香』『桂』『銀』はどのようにすれば良いものか(´・ω・汗)ゞ まぁCUIは今のうちだけなので自分にだけ分かればイイや~と思い、『香』は『』、『桂』は『』、『銀』は『』という風にこじ付けに近いがこのように表現している。。。



図19:ルール一応完成


 また、2歩のチェックには先手、後手にそれぞれ2歩フラグ用の配列を用意しフラグが立っている場合は手持ちから置く事ができない。そして、歩を取った場合、成った場合にはフラグを下ろして歩が置けるようにしている。



次回予告:置換表を実装



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

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

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