56将棋でPerft
はい。約10か月ぶりのブログ更新です。
競技プログラミング(AtCoder)をしたり、ランニングしたりしてたらこんなに時間が経ってしまいました。
最近はAperyを56将棋エンジンに改造すべく、ぼちぼちソースコードをいじっていました。
で、指し手生成はできるようになったので、合法手生成がきちんとできているかチェックしました。
コンピュータチェス(将棋)では、Perftという方法でテストするのが一般的みたいなのでやってみました。
将棋でPerftしてみたまとめのまとめ | やねうら王 公式サイト
一言でいうと、「すべての合法手を生成して局面を進めたとき、n手後に現れる局面数を求める」テストです。(わたしの理解が正しければ)
本当は複数の人でテストして、結果が一致するか確かめたほうが良いのですが、
とりあえず今回はAperyベースとBonanzaベース(プチボナ)とでテストしました。
以下がその結果です。
平手初期局面
sfen rskgb/ppppp/5/5/PPPPP/BGKSR b -
depth: 1 5
depth: 2 25
depth: 3 198
depth: 4 1538
depth: 5 15301
depth: 6 149264
depth: 7 1685699
いろいろな指し手が現れるように適当に作った局面
(Bonanza 56shogi 指し手生成 - 56将棋開発ブログのときに使ったやつ)
sfen 2kgB/1pp2/1s1P1/1B2p/r1PS1/3K1 b RG3P2p
depth: 1 63
depth: 2 1621
depth: 3 75088
depth: 4 1797781
depth: 5 71016894
depth: 6 1767336536
depth: 7 62269369719
2つの局面ともに、depth7までの局面数がBonanzaベースとAperyベースとで一致しました。
よかったですね。
【追記】
depth 6まで一致しました。shogi686microに書き足してやりました。
— merom686 (@merom686) 2018年3月13日
ブログ更新からわずか数時間。天才かよ。(感謝)
今後はAperyの改造をぼちぼち進めつつ、だいぶ放置しているAndroidアプリのほうもやっていきたいです。
それでは。
56将棋のAndroidアプリの開発をはじめました
56将棋のAndroidアプリの開発をはじめました。
開発環境はAndroid Studioでやってます。
Java自体ほぼ初めてなので大変ですが、自分にとって新しいことばかりで楽しいです。
とりあえず56将棋の盤面を表示させることができました。
ブラウザでの開発でもそうでしたが、やっぱり最初は将棋盤と駒の画像がきちんと並んで表示されるだけでも嬉しいものですね。
この画像はNexus5のエミュレータですが、FreetelのReiというスマートフォンを持っているので実機でもデバッグしています。
このエミュレータだとなぜか「将棋」という字が簡体字で表示されてしまっていて、大丈夫なのか心配しています。(実機だと問題ないのですが)
以下のサイトがとても参考になったのでリンクしておきます。
Android用リバーシゲームの作り方
Android開発日記 - 干支将棋
Androidアプリ開発の本やWebサイトで良いものがあったらコメントで教えていただけると助かります。(買うことも考えてます)(気が向いたらですが)
こんな感じでぼちぼち開発を進めていけたらと思っています。
それでは。
プチボナ 56shogi ver 2.0を公開しました
タイトルの通り、プチボナ 56shogi ver 2.0を公開しました。
リンク先のページからダウンロードできます。
将棋GUI「プチ将棋」の思考エンジンとして登録することで、対局ができます。
ver 1.0では手調整だった評価関数ですが、ver 2.0では自己対戦棋譜から学習させて評価関数を作成しました。
最初は駒割りのみの評価関数同士を自己対戦させた棋譜から学習させて、
以降はできた評価関数同士をまた自己対戦→学習という手順を繰り返しました。
(こちらのページに詳しく書いたので興味のある方はどうぞ。)
自己対戦→学習の繰り返しは数回で棋力が上昇しなくなってしまいました。
56将棋は本将棋と比べて盤面が狭く、決まった形が何度も現れやすいためかもしれません。
ver 1.0に対する勝率は7割弱くらいです。
自分の棋力(将棋倶楽部24中級くらい)ではまともに指したら勝てない強さになりました。
勝てなくて悔しいので、序盤だけいろいろな指し手を検討させたりしています。
ver 2.0は、「56将棋は先手有利」と主張しているような評価値を返すことが多く、
わたしはムキになって後手も戦える変化を探しています。
ちょっとでも反省させられると嬉しいですし、一応自分が考えた初期配置なので、
56将棋はそんなに浅くないということがわかると安心します。
今後としては、Aperyかやねうら王を56将棋で動作するように改変したいと思っています。
それでは。
名称変更
更新停止したと思われてもしょうがないほど更新しませんでしたが、生きています。
最近はプチボナ 56shogiで自己対戦棋譜からの学習を繰り返していました。
少しずつ強くなったので、近いうちにプチボナ 56shogi ver 2.0 として公開したいと思っています。
さて、5×6マスのミニ将棋に「ごーろく将棋」という名前をつけていたのですが、
「56将棋」というシンプルな名前に変更しました。
ブログタイトルも変更し、ブラウザで対局できるページも「56将棋 ブラウザ版」に変更しました。
このミニ将棋を考えたときは、ひらがな表記のほうが初心者が馴染みやすいと思っていたのですが、
最近は初心者から有段者まで幅広く触れてほしいという気持ちのほうが強くなったということがあり、変更することにしました。
また、これまでブラウザ版のページにはルール説明がなかった(別ページへのリンクを貼っていた)のですが、
新たに書き加えました。(ルール説明)
将棋のルールを厳密にわかりやすく説明することが、これほど大変だとは思っておらず、時間がかかってしまいました。
何か間違い、不明な点などあればコメントしていただけると嬉しいです。
次の更新は、プチボナ 56shogi ver 2.0 の公開になると思います。たぶん。
それでは。
進捗いろいろ
せめて数ヶ月に1回くらいは開発状況を書いておくかな、という気分になったので更新してみます。
最近取り組んでいるのは大きくわけて2つ、
・ごーろく将棋 56shogi ブラウザ版への機能追加
・プチボナ 56shogiの機械学習
です。
ごーろく将棋 56shogi ブラウザ版には、これからいろいろな機能を追加していく予定です。
とりあえず現時点で形になっているのは以下の2つです。
・局面編集
駒を好きなところに動かして局面をつくることができる機能をつくりました。
デバッグなどでつかう局面をつくるのが捗るので、正直に言うと自分用の意味が強いです。
こういうものはコンピュータ将棋におけるインフラみたいなものだと思うのですが、
56shogi の解に近づくという目標を達成するため、
あるいは、もう少しごーろく将棋が普及するといいな、というささやかな希望が実現するためには、
そういったインフラを少しずつでも整えていく必要があるのだな、と実感しています。
(どうでもいいことですが、コンピュータ将棋に関係する文脈では "56shogi"、
本将棋への導入、普及、教育といった文脈では"ごーろく将棋"あるいは"ごーろく将棋 56shogi"というふうに、わたしは勝手に呼び分けています)
・練習問題
COMとの対局だけでなく、ごーろく将棋や本将棋の棋力が向上するような練習問題が毎日アップされるページをつくっています。
開発言語はphpとMySQLで、ドットインストールをみて勉強しました。
練習問題の内容としては、ある局面において、浮き駒(味方の駒に支えられていない駒)をすべてクリックすると正解、というものです。
毎日数問ずつアップされるようにするのと、解くまでにかかった時間を最後に表示するようにしたら公開しようかなと思っています。
ほかにも、ある局面での駒割りを計算する問題や、あるマスで駒交換したときの駒割りを答える問題を出題するページもつくる予定です。
プチボナ 56shogi の開発の方も、ゆっくりではありますが進めています。
・機械学習
去年公開したプチボナ 56shogi は、指し手生成と探索部分はほぼBonanzaそのままで、56shogiで動くようにしたというものだったのですが、
評価関数はわたしが手調整で値を決めたものでした。(というほど調整もしていないのですが)
より棋力を向上するため、機械学習による評価関数のパラメータ調整に挑戦してみよう、ということでBonanzaのコードを読んでいます。
「コンピュータ将棋の進歩6 プロ棋士に並ぶ」という本にある解説が非常に参考になっています。
(というか解説文がないと、それぞれの関数のざっくりとした役割すら全くわからないレベルです…)
とりあえず学習部分のコードすべてに目を通したら、駒得のみの評価関数同士で自己対戦させた棋譜から学習させてみる予定でいます。
学習について勉強しはじめる前は、56shogiは本将棋に比べて駒の組み合わせの数が少ないので、学習にかかる時間が少なくて済むんじゃないかと思っていました。
しかし、パラメータを調節するステップよりも、探索してPV(最善応手系列≒読み筋)を求める処理のほうが時間がかかるらしいので、
うーん考えが甘かったかな、と思い直しています。
(本将棋より早く学習が進むのは間違いないと思うのですが)
まあやってみないとわからないので早く動かしてみたいですね。
それでは。
Bonanza ver 6.0 のsearchr()とb_gen_checks()について
気圧が下がってプログラミングのやる気がでないので、ブログ更新してみます。(ひどい理由)
以前から気になっていたのですが、Bonanzaのコードに不可解な部分があるので書いておきます。
まず、searchr.cのsearchr関数の、historyの値によって非PVノードの探索深さを調節する部分なのですが、
//Bonanza ver 6.0 searchr.c 620行目から //searchr() else { int depth_reduced = 0; new_depth = depth + extension; /* reductions */ if ( 2*PLY_INC <= new_depth && ! ptree->nsuc_check[ply] && ! UToCap(MOVE_CURR) && ! ( I2IsPromote(MOVE_CURR) && I2PieceMove(MOVE_CURR) != silver ) ) { unsigned int key = phash( MOVE_CURR, turn ); unsigned int good = ptree->hist_good[key] + 1; unsigned int triedx8 = ( ptree->hist_tried[key] + 2 ) * 8U; if ( good *160U < triedx8 ) { depth_reduced = PLY_INC * 3/2; } else if ( good * 50U < triedx8 ) { depth_reduced = PLY_INC * 2/2; } else if ( good * 19U < triedx8 ) { depth_reduced = PLY_INC * 1/2; } depth_reduced = PLY_INC; /* ????????? */ new_depth -= depth_reduced; } //以下略 }
となっていて、?マークのコメントを入れた行の処理で、直前の条件分岐が無意味になっているようにみえます。
(探索深さがhistoryの値に関係なく、同じになってしまうはず)
あとは、genchk.cのb_gen_checks関数に、持ち駒の飛車を打って王手する手を生成する処理があるのですが、
ここでは3手詰みルーチンの中合い問題でつかうために、玉との距離によって指し手にフラグを付加しています。
(MOVE_CHK_CLEARとMOVE_CHK_SET)
実際のコードはこうなっています。
//Bonanza ver 6.0 genchk.c 172行目から //b_gen_checks() if ( IsHandRook(HAND_B) ) { unsigned int move; int file, dist, min_dist; //敵玉が盤の右端か左端にいるならmin_dist = 2,そうでないなら3 if ( (int)aifile[sq_wk] == file1 || (int)aifile[sq_wk] == file9 ) { min_dist = 2; } else { min_dist = 3; } //to += nfileなので、敵玉の↓方向への飛打 for ( to = sq_wk+nfile, dist = 1; to < nsquare && BOARD[to] == empty; to += nfile, dist += 1 ) { move = To2Move(to) | Drop2Move(rook); if ( dist == 1 ) { move |= MOVE_CHK_CLEAR; } else if ( dist > min_dist ) { move |= MOVE_CHK_SET; } *pmove++ = move; } //to -= 1なので、敵玉の←方向 for ( file = (int)aifile[sq_wk]-1, to = sq_wk-1, dist = 1; file >= file1 && BOARD[to] == empty; file -= 1, to -= 1, dist += 1 ) { move = To2Move(to) | Drop2Move(rook); if ( dist == 1 ) { move |= MOVE_CHK_CLEAR; } else if ( dist > min_dist ) { move |= MOVE_CHK_SET; } *pmove++ = move; } //敵玉が盤の上端か下端にいるならmin_dist = 2,そうでないなら3 if ( sq_wk < A8 || I2 < sq_wk ) { min_dist = 2; } else { min_dist = 3; } //to += 1なので、敵玉の→方向 for ( file = (int)aifile[sq_wk]+1, to = sq_wk+1, dist = 1; file <= file9 && BOARD[to] == empty; file += 1, to += 1, dist += 1 ) { move = To2Move(to) | Drop2Move(rook); if ( dist == 1 ) { move |= MOVE_CHK_CLEAR; } else if ( dist > min_dist ) { move |= MOVE_CHK_SET; } *pmove++ = move; } //to -= nfileなので、敵玉の↑方向 for ( to = sq_wk-nfile, dist = 1; to >= 0 && BOARD[to] == empty; to -= nfile, dist += 1 ) { move = To2Move(to) | Drop2Move(rook); if ( (int)airank[to] == rank3 ) { move |= MOVE_CHK_CLEAR; } if ( dist == 1 ) { move |= MOVE_CHK_CLEAR; } else if ( dist > min_dist ) { move |= MOVE_CHK_SET; } *pmove++ = move; } }
玉が端にいるかどうかで、どの距離まで中合いを考えるかが違ってくるようなのですが、
コメントを付加したループの順番がおかしいようにみえます。
正しくは、
敵玉が盤の右端か左端にいるならmin_dist = 2,そうでないなら3
↑方向のループ
↓方向のループ
敵玉が盤の上端か下端にいるならmin_dist = 2,そうでないなら3
→方向のループ
←方向のループ
という順番であり、実際に後手番用のw_gen_checks()ではそうなっています。
以前にBonanzaのページに載っているメールアドレスにご連絡したことがあるのですが、
お忙しいようでお返事をいただけませんでした。
開発者の保木邦仁様の連絡先も知らないですし、ブログに書くことにしました。
コンピュータ将棋関係者の方がみていらっしゃるなら、なにかコメントしていただければと思います。
それでは。
ごーろく将棋 56shogi の実況動画
ごーろく将棋 56shogi ブラウザ版の実況動画を投稿してくれた方がいるのでご紹介します。
角 vs 飛車の動画で有名な、将棋の実況動画を投稿されているプロパンゴリラさんです。
COMのレベルは迷わずレベル5(JavaScript版プチボナ)を選択され、先手がプロパンゴリラさん。
1局目からプチボナは強襲します。
ごーろく将棋 56shogiを指したことのある人の中でも、知っている人は知っている角捨ての筋です。
似た局面でも現れるので、(別の方ですが)ツイートを紹介します。
この辺で俺の知ってる56shogiじゃないと悟った。 pic.twitter.com/LJodjyrDRC
— merom686 (@merom686) 2015, 5月 8
狙いは▲同金に△5四歩で次に金取り+と金づくり、避けても△5五歩成で、と金ができて角が助からない形です。
いきなりプチボナが力を見せたか、と思いきや、▲同金と進んだ局面で、プチボナは△5四歩と突かずに△2四歩ととります。
これはなぜなのか。
動画内のコメントにもありましたが、角を切って▲同金の局面から△5四歩▲2三歩△5五歩成と進むと以下の局面になりますが、▲2二角打から以下後手玉が詰んでしまいます。
ということにプチボナは角を切ってから気づき、慌てて△2四歩と指したということだと思います。
しかしそれでは角を捨てた損が残ってしまい、局面はプロパンゴリラさん大優勢になりました。
その後、千日手の筋が現れ、千日手判定されるか試してみたいということで千日手の手順に。(実装しといてよかったです)
2局目はプチボナが得意の終盤力をみせて勝利しました。
ここでの△2五角合(逆王手)が印象的でした。
3局目は序盤からプロパンゴリラさんが駒得して優勢を築き、プチボナはいいところなくプロパンゴリラさんの圧勝でした。
奥のプチボナの形はあまり良くないと思うのですが、評価関数の問題なのか、たまにこうなってしまいます。
終始、指していて本当に楽しそうに実況していただいて、何度もリピートして観てしまいました。
これからもっとたくさんの人に指していただけると嬉しいです。
それでは。