Hatena::ブログ(Diary)

ひよこ将棋、はじめました。


  ひよこ将棋関連の実行ファイルは → ここ
やねうら王公式

2014-11-21

やねうら王の定跡生成コマンド

02:46 | やねうら王の定跡生成コマンドを含むブックマーク やねうら王の定跡生成コマンドのブックマークコメント

昨日公開した駒得のみの評価関数にしたやねうら王*1の定跡編集コマンドを公開します。

  • 定跡の生成コマンド

makebook depth 14 record -1

records.sfenから定跡を自動生成する。
あと、records1.sfen , records2.sfen , ..を配置してあると、そちらもrecords.sfenに連結されているものとみなして読み込む。

depth : そのときの探索深さ。default = 14。この深さで探索して -500以上ならば定跡に登録。
moves : 定跡化する最大手数。default = 32。
record : 使う棋譜の数。-1ならすべて
eval : この評価値以上ならば定跡に登録。default = -10000。
// defaultではすべて登録するが、-200以下になる指し手は採用しないのでこれはこれで構わない。
init : 定跡DB初期化してから読み込む
skip : 棋譜のうち、最初の指定数の局だけ読み飛ばす。

makebook skip 100
なら101局目から開始。
skipmoves : 定跡の最初のN手をskipする。

makebook skipmoves 4
なら初手から数えて4手skipする。

mergebook
"shogi_book.db3"と"shogi_book2.db3"とを前者にマージする。
後者は前者を別のPCで定跡を生成してリネームしたものとする。
同じ局面の同じ指し手では探索depthが深いほうを採用する。

// depthが前者に登録されている局面のほうが深い場合skipする。
// このとき'.'を表示する。
// また、深いdepthだったので指し手をoverwriteしたなら'*'、
// その指し手が新規挿入なら'+'を表示する。


特別に以下の指し手はあまりにひどいので定跡DBにhitしたときに評価値を-10000しています。(ソースコードより抜粋)

auto gamePly = game.Searches.RootPos.game_ply();
vector<Move> removes;
switch (gamePly)
{
case 0 : // 先手の初手

// 検討モードで動かすことも考えてhashもチェックしたほうがいいか。
// てか検討モードでgamePly == 0を渡してくる将棋所がおかしいんだよな..
// gamePly = 0のときだけ局面のhash値もチェックすべきか…。
if (key == 650845876563499746ULL)
{
removes.push_back(make_move(SQ_59, SQ_68)); // 68玉
removes.push_back(make_move(SQ_39, SQ_48)); // 48銀
removes.push_back(make_move(SQ_49, SQ_58)); // 58金右
}
break;

case 1: // 後手の初手

// いかなる局面でも62銀と42玉は最善手ではないと思う。
removes.push_back(make_move(SQ_71, SQ_62)); // 62銀
removes.push_back(make_move(SQ_51, SQ_42)); // 42玉
break;
}

将棋所でPVの表示

seldepth
→ : 自ら定跡の局面で思考した指し手
← : 現在の対局で採用された指し手


例) 定跡学習させたい棋譜をrecords.sfenに用意して、やねうら王をダブルクリックして実行してコマンドラインから
makebook init moves 32 depth 24
と入力すれば、探索深さ24まで探索して、各対局棋譜の初手から32手目までを定跡として学習します。(initは定跡DBを開始前に初期化する指定)


参考記事)
コンピューター将棋の定跡をデザインする
http://d.hatena.ne.jp/yaneurao/20141114#p1

2014-11-20

駒得のみの評価関数にしたやねうら王 V3.37を公開しました

05:28 | 駒得のみの評価関数にしたやねうら王 V3.37を公開しましたを含むブックマーク 駒得のみの評価関数にしたやねうら王 V3.37を公開しましたのブックマークコメント

以前のひよこ将棋が最新の将棋所ではthread = 1でないと動かないという苦情を受けて、いつか修正したものを公開してやる!!と思っていたのですが、やっと落ち着いたので、やねうら王の最新版(おもてなし定跡あり)の評価関数を駒得のみに変更したものを公開します。

ファイルはこのブログのヘッダーにある「ひよこ将棋関連の実行ファイルは → ここ 」のところに置いておきます。将棋所の思考エンジンとして使えます。

定跡についてはまだ生成過程ですので、今回の電王戦バージョンとは異なります。

レーティングはおそらく最新PCではR2000程度ではないかと思います。(わざと序盤で定跡を外したりしない限りは)

公開されている駒得のみの評価関数将棋ソフトとして史上最強でしょう。
まあ、駒得のみなのでじわじわ押していけばアマ初段ぐらいの人でも勝てると思いますが。

対局した感想などもらえると嬉しいです。


思考エンジン設定などについてはこちらをどうぞ。
http://d.hatena.ne.jp/yaneurao/20141120#p1


やねうら王の定跡編集コマンドの仕様を公開しました。
http://d.hatena.ne.jp/hiyokoshogi/20141121/1416505613

2012-10-27

Parallelaその後

15:35 | Parallelaその後を含むブックマーク Parallelaその後のブックマークコメント


並列プロセッサーであるParallelaは、Kickstarterで資金を集めていたようなのですが、その期日が16時間後に迫ってきました。

http://www.kickstarter.com/projects/adapteva/parallella-a-supercomputer-for-everyone


昨日の時点では予定額である$750,000に$100,000ほど満たなかったのですが、ようやく$750,000を超えたので$99払う人は16コア版が来年の5月ごろに届くことが確定的になりました。


f:id:hiyokoshogi:20121027153205p:image


しかしもうひとつの設定額である$3Mには満たないので64コア版は今回はリリースされないのだと思います。これについては、もう2,3年待たないといけないのかも知れません。


コンピューター将棋にParallelaのようなNUMA(Non-Uniform Memory Access)型のプロセッサーが適合するかどうか考えてみましょう。


NUMA型というのは、よくあるモデルとしてはタイル状にCPUを配置して、隣合うCPU(上下左右)同士をつないでやるというものです。


この上下左右の接続は比較的低い遅延で接続されていますが、それでも64個接続の場合で左上から右下へは下に7回、右に7回で14回のバケツリレーが必要なので14サイクル分の遅延はあります。結果データを回収するときも左上で回収するならば同様に14サイクルの遅延があります。往復で28サイクルです。CPU数が64個ではなく256個(16×16個)ですと往復60サイクルです。


いくらなんでも小さいタスクを投げて結果を回収するだけで60サイクルもかかるのは厳しいものがあります。また256個もCPUが接続されていますとデータを投げるだけで256回も投げないといけないのではメインのCPUに負担がかかりすぎます。


そこで、普通はメインのCPUの負担を減らすためにすべてのCPUに対してデータを投げる(ブロードキャストする)ための特殊な命令を用意します。左上のプロセッサーから伝達していくとして、このデータを受け取ると右側と下側に接続されているCPUにも同じデータを伝達するものとします。(Parallelaにそのような命令があるのかどうかは知りませんが。)


次に、タスク内容を左上のCPUからブロードキャストするのであれば、結果データの回収を右下のCPUからしたいのは言うまでもないことで、(計算は左上のCPUから終わるのでそれを右下に向かって伝達して右下で回収するほうが時間のロスが少ない)、NUMA型では上下左右のCPUと接続するだけではなく、リング状に接続することもよくあります。IntelのMany CoreであるKnights Cornerがこのようなリング状の接続をしていると言われています。(来年ぐらいには発売されるのでしょうか…)


コンピューター将棋に限って言えば、与えられるタスクはすべてのCPUにおいて同一だとして、例えば指し手生成であれば前回局面からの差分(次の1手の指し手情報)をブロードキャストして、そしてそれぞれのCPUが自分に割り振られた指し手を生成するという仕組みを取ります。そう考えますとブロードキャストは頻発するのでブロードキャストは少しでも速いほうが良く、本当にバケツリレーで伝達していいのかという問題はありそうです。


データの回収も、例えばそれぞれのCPUが局面の部分的な評価値を計算して結果を右下のCPUに伝達するのであればその伝達するときに足し算もして欲しい気はします。すなわち、CPU間で情報を伝達するときに足し算マークがついていれば、左のCPUから来た情報と上のCPUから来た情報を足し算したものを次のCPUに伝達するというような仕組みです。


そう考えますと、コンピューター将棋にとって望ましいのは64コア版のParallelaではなく、FPGAでNUMA型の汎用プロセッサーを実装するほうがいいのではないかとも思えます。少なくとも局面の評価値を計算するだけでしたら乗算・割算はもとより引き算も不要ですので、汎用プロセッサーと言えども命令数はかなり少なくて済みますから、Z80が1200LE(LE = Logic Element)程度で収まることを考えますと、一つのCPUはそれ以下のLE数で収まることは間違いなく、300K LEぐらいの製品でも256CPUは可能なのではないでしょうか。


FPGAでNUMA型の汎用プロセッサーを実装する利点としまして、一度論理合成をしてしまえばそのあとはその汎用プロセッサー用の命令でプログラムを書いていけばいいので以降は論理合成をする必要はなく、また、その汎用プロセッサー用のエミュレーターを実装すれば効率的にデバッグが出来るようになるということです。


FPGAのほうは、いまであればVirtex-7あたりが良いと思うのですが、300K LE規模の評価ボードで$3500程度。1M LE規模の評価ボードはおそらくその3倍ぐらいのお値段です。コンピューター将棋の探索部もまるごとFPGA化しようと思いますと、FPGA上に汎用CPUを実装してその汎用CPU用に実装するのであればそれ自体は難しいことではないのですが、Intelの最新のプロセッサーに比べて1/4程度の速度にすることすら難しいのが実状で、なかなか厳しいものがあります。


局面の評価値の計算だけFPGAでやらせるようなソリューションもありだとは思うのですが、PCIe、もしくはHyperTransportで接続したとしてもCPUFPGA間での往復だけで0.5ms程度かかるらしく*1、他の部分の時間がすべてゼロで済んでも2Mnpsしか出ません。実際はゼロでは済まないので500Knpsすら厳しいと思います。


このような場合、CPU側は並列探索して、FPGA側からの結果を待たずにどんどん局面を投げてlatencyを隠匿させるのが普通ですが*2、仮にFPGA上では局面の評価を1秒に20M回ぐらい出来ていたとしても、1Mnps程度の実効速度すら出るのかどうか…。



Parallelaにもっとローカルメモリーがあれば普通にそれぞれのCPUに探索を割り振って並列探索をさせたほうが良さそうですが、そんなにローカルメモリーはありません。IntelのKnights Cornerの場合、それが出来そうですが、1GHz程度とアナウンスされていますので√N程度の実効しか出ないとすれば、50CPUでも…。計算したくありませんね。並列探索の効率は√Nほど悪くないと思うのですが、それでも1GHzでは萎えますね。


ただ、FPGA上に汎用CPUを作る場合、ASICに比べると動作周波数は低いはずで、500MHz程度ですら出るかどうかわからず、さらに厳しいです。



結局のところ、凄く時間のかかる局面評価だけをFPGAに投げて、メインCPUとのやりとりにかかるlatencyを隠匿するためにメインのCPU側では並列探索(100並列ぐらい?)を行なうのがいいような気はするのですが、そうしますとメインCPU側から渡す局面図が前回からの差分で済みませんから…いやはや考えたくもないですね。


ヘテロジニアス型のマルチコアでの並列コンピューティングはコンピューター将棋にはあまり向いてないのでしょうね。少なくとも普通のハイエンドCPUと同等のnpsで同等の処理が出来るということだけを目標としたとしても非常に厳しいものがありそうです。

2012-10-19

泥沼流コンピューター将棋

00:29 | 泥沼流コンピューター将棋を含むブックマーク 泥沼流コンピューター将棋のブックマークコメント

米長先生の将棋は昔、「泥沼流」と呼ばれていたことがあります。


厚みを重視し、劣勢になると自陣に駒を打ち付け複雑にして逆転を狙う棋風からそう呼ばれていたようなのですが、局面を複雑化したり、定跡を外したりするのはコンピューターのみならず、人間相手でも有効です。


特に近年、どうやってコンピューター将棋が人間相手に手加減をするかという部分に注目が集まっており、私は「泥沼流」コンピューター将棋を作れないかと考えておりました。


そこで、見かたを変えまして「前例のないような局面」に誘導することを思いつきました。


「前例のない」というのをどう定義するかですが、盤面全体と比較してしまいますと定跡から外れた時点で「前例のない」局面ということになってしまい、これでは意味をなしません。


Bonanzaであれば3駒相対で評価しますが、これらのパラメーターに対して学習棋譜にその特徴が出現した回数もカウントしておきます。これが少ないものには加点します。さすがに評価値がマイナスのものに加点してプラスにするのは気持ちわるいので、評価値がプラスのものにのみ加点します。


例えば次のような計算式はどうでしょう。


評価値 = c1 × 元の評価値 / log(出現回数 + c2)
c1,c2は適当な係数。棋譜の量などで調整する。


こうしておけば出現回数が多いほど評価値が減少します。


実戦ではあまり現れない形を好んで指すようになり、それでもそこまで悪くはない形(少なくとも元の評価値はプラスなので)を目指すはずです。


米長先生の「泥沼流」とはまた違うかも知れませんが、人間の棋譜ではあまり見られない形が出てくるこのようなコンピューター将棋というのもまた面白いのではないでしょうか。

2012-10-11

Parallellaによるコンピューター将棋の開発

12:55 | Parallellaによるコンピューター将棋の開発を含むブックマーク Parallellaによるコンピューター将棋の開発のブックマークコメント

Parallellaという16/64コアの並列コンピューティング向けのプラットフォームが発表(発売)されました。16コア版が$99、64コア版は$199(予定)で手に入るようです。


Adapteva公式
http://www.adapteva.com/


RISCチップでそれぞれのコアは1GHz程度で動作しているようです。OpenCLプログラムをすることも出来ます。ただOpenCLですと並列化に向かないような処理をさせる場合には最大限の能力は発揮できないでしょう。アーキテクチャマニュアルを見る限り、もう少し細かい並列化も可能のように思えます。


ちなみに、128×128の行列の掛け算は16コア版で2ms以下で終わるそうです。つまり128×128×128回(=2^(7*3)=2M回)の掛け算と足し算が2ms以下ということで1秒間に1G回以上の掛け算と足し算が出来るということですね。アドレッシングに数命令かかり、ループ変数のインクリメント、ループの終了判定〜ジャンプにも2,3命令かかることを考慮しますと、そこそこ速いのではないでしょうか。


アーキテクチャマニュアルを見る限り、コア間はeMesh(TM)で接続されているそうです。ぱっと見た感じ、コアごとに(x,y)のような二次元座標みたいな番地が振ってあって、バケツリレーで運ぶように見えますが、よくわかりません。メモリアクセスがもっとボトルネックになるのかと思ったら、行列の掛け算の例から察するに、結構の性能が出るんだなーというのが正直なところです。


まあ、16コア版でもIntelハイエンドCPUの1コアの3倍ぐらいの処理が出来るでしょうから、64コア版ですと、10倍ぐらいの処理はできるのではないでしょうか。コンピューター将棋の並列探索の効率が√N程度だと仮定しますと、シングルコアの10倍の速度で探索が出来るならばそれは100コア相当という計算になり、なかなか夢が広がりますね。


それでまあこのParallellaのようにコア間の通信コストが極めて小さい場合、実質的にシングルスレッドで高速に探索させることが可能だと思うのですが、そのためには評価関数は時間がかかるものであればあるほど得だというのはあります。


たとえば、BonanzaとGPS将棋の評価関数ではBonanzaのほうが3倍ぐらい評価関数は軽いですが(正確に比較したことはありません)、その分たくさん探索できるので、総合的な棋力としてはGPS将棋と互角ぐらいに落ち着きます。


つまり、これがほぼ互角だとしますと、評価関数を重くしてその代わりに探索速度を低下させてもBonanza、GPS将棋と互角ぐらいになる評価関数も設計できるはずです。こうして評価関数をどんどん時間のかかるものにしていこうと考えます。


そうして行きますと計算に非常に時間がかかる(だけど精度は良い)評価関数が出来上がるわけですが、このように重い評価関数のほうが、Parallellaのようなコア間の通信コストが極めて小さいプラットフォームでは評価関数の計算をする部分を並列化したときの並列化効率が良いことになります。


そもそも評価関数以外の部分、たとえば指し手生成を並列化すると言いましてもそんなにたいした並列化はできません。むしろ、Parallellaの場合、動作クロックが低い分、普通のIntelCPUと比較して速くなるかどうかすら微妙です。ゆえに評価関数のところで速度を稼がねばというのはあります。


ともかく、64コア版が$199で手に入るのですから、これが1台のハイエンドPCより少しでも速く探索できるのであれば、この64コア版でクラスターを組むのはありなのではないでしょうか。$199ならば普通のハイエンドPCより断然安いでしょうから。


個人的には、ParallellaにARMのA9ではなく、iPhone5に載っているものか、その倍ぐらいの性能のものがメインのCPUとして載っていれば、そのプロセッサに探索のメイン処理を任せられるのになぁというのはあります。評価関数の計算だけ並列してやらせようというアイデアですね。


まあともかく、並列コンピューティングがなかなか面白い状況になってきたのではないでしょうか。