サクサク読めて、アプリ限定の機能も多数!
トップへ戻る
GPT-4o
ls3600.hatenadiary.org
■ Bonanzaが用いているbitboardの定数配列の意味【後編】 前回記事 : Bonanzaが用いているbitboardの定数配列の意味【前編】 http://d.hatena.ne.jp/LS3600/20091102 の続き。 今回は、残りのbitboardの定数配列の意味を解説する。 これによりBonanzaのソースコードにある暗号めいたbitboardのビット演算関係の動作の大半が理解できるようになる。 ■ abb_mask,abb_mask_rl90,abb_mask_rl45,abb_mask_rr45 まず、ini.cのini_tablesの残りabb_mask,abb_mask_rl90,abb_mask_rl45,abb_mask_rr45の意味から解説する。 変数名のabbのaはarray、bbはbitboardの略。rl90はrotation(回転) left
Bonanzaで1ヶ月+α*1と保木さんに教えてもらいましたが、当時のPCでBonanzaは1コア当たり250knpsぐらいしか出ませんでした。いまのPCでいまどきの作り(Stockfish風の探索部)であれば、1Mnpsぐらい出ます。 ということは探索速度は4倍になっていることになります。また、コア数も当時はXeonで4コア×dual = 8コアでしたが、いまはAWSなどでは16コア環境を使うことは容易です。ということは、ボナメソでやっても4倍×2倍 = 8倍早く収束するわけで1から学習させても4,5日+αがあれば収束することになります。 ここに相対KPP/KPAなどによる次元下げを併用した場合、さらに短い時間で収束することが予想されます。AWAKEの例でPC 6コア×1台+4コア×2台の3台構成で3日という話がありました。だいたい上記の計算と辻褄が合うように思います。 これくらい短かい
NDFがやったKPPの次元下げ KPP = 絶対KPP + 絶対PP + 相対KPP + 相対PP を綺麗にプログラムするための方法について考えてみます。このような次元下げは、KPPを与えるとそれに対応する絶対KPP、絶対PP、相対KPP、相対PPの配列のindexを返すものとして設計すると綺麗に書けます。 すなわち、 int* make_kpp(Square king , BonaPiece p1 , BonaPiece p2); のように設計することです。この返し値をpとすると、 learn_kpp [ p[0] ] が絶対KPP learn_kpp [ p[1] ] が絶対PP learn_kpp [ p[2] ] が相対KPP learn_kpp [ p[3] ] が相対PP p[4] = INT_MAX(終端) のようになります。 もう少し一般化すると、KPPを4個に分解するとは
知っての通り、Bonanza6では、手駒の価値は駒割の値 + KPのP=手駒としての値の合計値となる。(実際にはKPPの一つ目のPと二つ目のPが等しいときのKPと、 KKPのP=手駒のほうとがあるが、細かい話は割愛する) さて、駒割の値というのは、盤上の駒と手駒をひっくるめて、歩 = 100点のように点数化してある。 KPのP=手駒というのは、「先手の持ち駒の歩が0枚」「先手の持ち駒の歩が1枚」「先手の持ち駒の歩が2枚」のような状態を一つの駒(P)とみなしてある。 1枚目の歩だけ価値が100点よりは少し高く120点の価値があるとしよう。そうすると「先手の持ち駒の歩が1枚」のKP値には20点がつくことになる。 2枚目の歩は逆に80点の価値しかないとしよう。そうすると「先手の持ち駒の歩が2枚」の価値は-20点がつくことになる。 以下、同様であるのだが、歩を10枚以上持っているような局面はなかな
(前の記事の続き) 次に、別のやり方として、先手が歩を3枚持っているときに「先手の1枚目の歩」「先手の2枚目の歩」「先手の3枚目の歩」のような駒があるとみなす三駒関係の設計の仕方があります。 このようにすると、盤上にない駒は手駒にあるわけで、玉以外の38駒がどこかにはあります。例えば金は盤上の53にあったとして、それが取られて相手の手駒の3枚目の金になったら、この金は、「盤上の53金」という背番号から、「相手の手駒の3枚目の金」という背番号に変わります。 このように考えると、38駒がどこに行ったのか必ず追跡することが出来ます。このため、駒をmake_listで直列化したときに必ず38要素の配列が出来ます。こうなっているほうがmake_listの差分計算化がしやすいので、こちらのほうが優れている意味があります。この方法は、去年のPonanzaが採用していました。(いまも採用しているかは知りま
電王トーナメントのアピール文書、「やる予定」「やる予定だけど効果かどうかはわからん」みたいな書き方をしているものもたくさんありますが、ソフトがアピール文通りになっていないからと言って罰則があるわけではないのでそれを見越してやねうら王は適当ぶっこいてるんだろうと邪推している人もおられるかも知れません。 今年はどうなるかはわかりませんが、しかし、去年は私は書いている通りのことはすべてやりました。 そのなかでも一つ説明を書いていなかった、去年の電王トーナメントのときの「やね裏評価関数」について、そろそろオープンにしてもいいかと思い、これについてざっと技術的な説明をします。 Bonanzaの三駒関係では盤上の駒だけでなく、手駒もひとつの駒とみなします。「歩が3枚」「香が0枚」「桂が4枚」というような駒が存在しているものとみなします。なので、KPP(玉と2駒)のときに、「先手88の玉」×「後手の歩が
知っている人は知っているかと思いますが、Haswellになってから、Bit Manipulation Instructions Sets (BMI sets)という命令セットが使えるようになりました。 http://en.wikipedia.org/wiki/Bit_Manipulation_Instruction_Sets#BMI2_.28Bit_Manipulation_Instruction_Set_2.29 SIMD用ではないので汎用レジスタ(64bit)に対してしか使えませんが、面白い命令がいくつかあります。 例えば、PEXTというParallel bits extract命令。これはなかなか使えます。 例えば、60bit目,30bit目,12bit目を1にしたbit maskを用意したとします。このmaskを指定してPEXTを使うと、入力レジスタの60bit目と30bit目と1
■ Rotated Bitboardsは本当に高速なのか? rotateをやろうと思うと、90度、45度x2で、3つのbitboardをmakeMoveで更新しないといけない unmakeMoveも同様。一つのbitboardは3個の32bitのint変数に演算を行うことになる。 これはけっこうばかにならないコスト。(駒を動かすと3x3x2=18回の演算がいる) rotated bitboardは本当に速いのか?(小宮日記) http://d.hatena.ne.jp/mkomiya/20090222 Rotated Bitboardで高速化されるかどうかは興味深いところですね。 #define AttackFile(i) (abb_file_attacks[i] \ [((ptree->posi.occupied_rl90.p[aslide[i].irl90]) \ >> aslide[
■ Bonanza4の評価関数はどのようなものか【fv.bin編】 前回、Bonanzaの駒割の評価部を説明した。 残るは、「3駒相対」の部分であるが、この3駒は、 ・2玉 + 駒 ・1つの玉 + 2駒 の二つの組み合わせがある。 Bonanzaでは、このどちらも評価している。 ここでは前者をKing-King-Pieceを略してKKP、後者をKing-Piece-Pieceを略してKPPと呼ぶことにする。 実際、Bonanzaのソース上に、kkpという配列があり、この評価のための値が格納されている。これは、data.cにて宣言されている。 // 評価値計算用テーブル short pc_on_sq[nsquare][pos_n]; short kkp[nsquare][nsquare][kkp_end];pc_on_sqのほうは、KKPではなく、KPPのほうを評価するためのテーブルである。
Core i7のL2は小さすぎる。Core 2シリーズでは4MB前後あったL2が、次のようになっている。 L2:256KB×4 L3:8MB L2がコアごとに256KBしかないので、コンピュータ将棋で使うような利きを求めるためのlook upテーブルすらL2には載るかどうか怪しい。Magic BitboardsなんかまずL2に載らないだろう。 コンピュータ将棋用として使うならNehalem(Core i7/Xeon 5500系)は要注意である。正直、Nehalemはコンピュータ将棋向きではないと思う。 来年5月の大会(世界コンピュータ将棋選手権)用なら、Core i9が来年3,4月ごろに発売されるらしいので、これのXeon版(6コア×Dual = 12コア)しか大会上位に残るつもりなら選択肢がないのだが、こちらも L2 : 256KBx6 L3 : 12MB という噂だ。L2は非共有で、L
Bonanzaでは駒を表現する型はs8(singed char)になっています。 さて、問題です。私のように設計した場合、 -(int)UToCap(move) に相当する部分はどう書けるでしょうか?なるべく速いコードを求みます! http://d.hatena.ne.jp/LS3600/20111001 私が書いたコードは、次のコードでした。 ( ( Cap(move) + (piece_enemy - 1) ) & piece_enemy) | Cap(move) Cap(move) > 0のときに(piece_enemy - 1)を足せば、piece_enemyのbitが1になるので、Cap(move) > 0のときだけpiece_enemyのbitをもらってこれるなぁというコードです。 これが最速かどうかはよくわかりませんが、そこそこ優秀なコードではないでしょうか。 駒をu8(un
Bonanzaの3駒関係ですが、このパラメーターを棋譜から学習させたこと、すなわちボナメソがコンピューター将棋のブレークスルーであるように言われていますが、まあ、実際にもBonanzaに関してはその通りなのですが、私は、それより3駒関係という評価関数というシンプルながらそこそこ有効に機能する評価関数を設計したこと自体が偉大なる発明だと思っています。 3駒関係でそこそこ強いということが証明されているわけですから、あとはどうやってこのパラメーターを学習させるのかという話になります。 fv.binのパラメーターを隈無く観察すれば、3駒関係で(大きな)評価点がつくポイントというのは、実はいくつかの法則があることに気づきます。 その法則を分類するとだいたい10個ぐらいの評価因子から成ることがわかります。 その10個の評価因子からfv.binを再構成して、fv.binとの二乗誤差が最小になるようにしま
■ Bonanzaの指し手表現は何故優れていると言えるのか 指し手生成祭り開催 http://d.hatena.ne.jp/LS3600/20091110 指し手生成に関して、「私の将棋ライブラリ」で2.15M/sec、Bonanzaが1.1M/sec、misakiが私の方法を取り入れて300K/sec→600K/secになりました。C#で書かれているBlunderはまあ仕方ないとしても、C/C++でなおかつbitboardを使っているmisakiの指し手生成自体は(私に言わせれば)遅すぎます。 それで何故遅いのかというと、ここに書かれているように、misakiはれさぴょんのコードを引きずっているからだと思います。 http://d.hatena.ne.jp/mkomiya/20091110/1257785583 typedef struct { uchar from; uchar to;
CSAファイルの読み込み部分の解説が終わったのでCSAファイルの書き出しについて解説していこうと思うのですが、その前に、in_CSA_headerの引数で渡しているflagの意味を書いておきます。これは書き出しのときも共通です。 enum { flag_time = b0001, // CSAファイル読み込み時に、考慮時間を // sec_w_total(先手側の考慮時間) // sec_b_total(後手側の考慮時間) // に反映させる。 flag_history = b0010, // make_move_rootという、対局盤面(探索のときの開始局面)を次の局面にする関数があり、 // そのなかでmake_moveを呼び出すのだが、そのときにこのフラグが立っていると // out_CSAを呼び出して指し手をファイルに書きだしていく。 flag_rep = b0100, // 千日
盤面が同じでhandが違う、という場合は書くべきかどうか微妙な気はしますが、そうしたいならばif条件は&&ではなくて||ですよね。 (中略) まあここを変えてもそうドラスティックに強さ変わるわけではないとは思いますが、「盤面異なるが持ち駒は同じ」局面群に対してはpreferしか使わないことになるので、そこそこ発生するような気はします。 バグ?(A級リーグ指し手1号) http://aleag.cocolog-nifty.com/blog/2010/02/post-5656.html そうですね。私もその部分はバグかな?と思います。 該当部分、私がコメントを追記したソースを以下に掲載します。解析の初期段階に書いたコメントなので間違っているところがあるかも知れませんが、まあ何かの参考にはなるかと。 word1 name bits shifts depth 8 56 ← 探索深さ(hash_st
将棋では連続王手の千日手は王手をしている側が負けです。だからと言って連続王手のループを見つけた時点で攻め方の負けと判断したのではGHI問題を引き起します。 さて、いま、定跡を自動構築することを考えます。ここで言う定跡とはプロ棋士の棋譜の何手目までという話ではなく、与えられた局面を通常探索で探索した結果をそのまま定跡として書きだすわけです。 これを定跡と呼ぶにはいささか精度の問題があるかも知れませんが、それでも事前に10分でも20分でもその局面についてじっくり考えられるわけですから、その結果をファイルに書きだしておけば、コンピューター側が実戦でその局面に遭遇したときにノータイム(1手1秒)で指せるわけで、これの効果がないと唱える人は居ないでしょう。(プロ棋士の棋譜から構築する定跡DBは別途持っているものとします。) ところが、このように局面の情報を書きだすときに経路(そこまでの手順)に依存す
■ Bonanzaを改良するすべての人のために Bonanzaを少し改良して、Bonanzaよりわずかに強いものを作るのはそう難しいことではない。 しかし、例えば利きを追加して、それに従い評価関数を利きを利用するものに書き換えようとした場合、二つの問題に直面する。 1. Bonanzaメソッドでどのように学習させるべきか? 実際、Bonanzaがどの棋譜からどうやって学習させたのか詳細は知られていない。Bonanzaに付属のfv.bin(学習データ)と同等の性能をもつ評価関数パラメータの学習に成功した人は、現時点では一人もいないと言われている。 fv.binと同等のデータを学習するのに1ヶ月以上かかるとも言われており、ハードルも高い。 これについては別途詳しい記事を書く予定なのでご期待いただきたい。 2. 本家Bonanzaのバイナリはどのようにコンパイルされたものか? 少しBonanza
■ Bonanzaの定跡データベースはどういう構造になっているのか? 指し手生成について一通り解説が終わったので、その他の部分を順番に解説していく。 解説していくとは言うものの、私自身そんなに時間がとれるわけではないので、Bonanzaのソースにコメントを大量に追記した私のソース上のコメントをその解説代わりとしたい。 ■ 定跡ファイルの構造 Opening Book Data Structure: Index BookData 定跡データ構造は、 Index BookDataで構成される。 Index: IndexEntry.. (NUM_SECTION times) Indexは、IndexEntryがNUM_SECTION回ある。 IndexEntry: SectionPointer SectionSize IndexEntryは、SectionPointerとSectionSizeか
■ Bonanzaの指し手生成は40%以上の高速化ができる Bonanzaの評価関数はどのようなものか?【KKP編】 http://d.hatena.ne.jp/LS3600/20090928 のほうで保木さんからコメントを頂戴した。 > 先頭でbitwise ORをとって空なら抜けるように Bonanza のソースファイルでもそうなっていると思います。 "while( BBToU(bb) )" の行です。 大きな違いはビットを 0 にセットする時、32ビットのシフ トを使用しているところではないでしょうか。 Bonanza では "Xor( sq, bb )" マクロを使い、32x3 ビット のテーブル参照しています。 LS3600 さんの方法がよさそうなので、将来参考にするかも しれません。私はbitboardをiterateするのに、foreach_bitboardなるマクロを使用し
どちらも強いプログラムなのに、未知の局面への対応力に差が生じるのは不思議ですね。 http://d.hatena.ne.jp/yaneurao/20140208#c1392482608 棋譜からの学習は、いわゆる「機械学習」の考えを用いていますが、この機械学習にはL1正則化だとかL2正則化だとかがあります。簡単に言ってしまえば、出現しなかった評価項目はゼロするという縛りみたいなものです。この縛りを入れないと、出現頻度が低かった因子(評価項目)に対して棋譜との一致率を上げるためにどこまでも大きな値がつく(発散する)ことがありえます。これを回避したいというのがL1/L2正則化を行う主な動機です。 ところが、このような正則化をしますと、棋譜に現れなかった因子はすべてゼロになってしまいます。Bonanzaで入玉の評価が著しく下手なのも、入玉棋譜が足りていないため、おかしな値しかついていない(もしく
■ posi_t構造体 Bonanzaでは局面を表現する構造体posi_tはshogi.hで定義されている。 構造体のそれぞれのメンバ変数がどういう意味を持つかについては、それが使われているところを見るのが一番手っ取り早く、具体的には、指し手生成(makemove.c)のソースを見るのが一番早い。 それぞれの変数が何を意味するか、補足用のコメントを追加しつつ引用すると次のようになっている。 // 局面 typedef struct { // 局面のhash値 uint64_t hash_key; // --- 各駒のbitboard // b_ はblack(先手) , w_ はwhile(後手) // 先手/後手の駒の有無(駒があれば1) // このmaskには王も含まれる。 bitboard_t b_occupied, w_occupied; // ↑の駒の存在する位置を示すビットマッ
■ npsの意味するところ コンピュータ将棋ソフトによって「nps」(nodes per second)という用語が意味するところはまちまちである。 Bonanza(バージョンは4.1.2で検証)の場合、npsの意味するところは、評価関数を呼び出した回数ではない。 それではnpsは何を意味するもので、npsのうち何%が評価関数を実際に評価する回数なのかを調べていく。 まず、evaluate(評価関数)の実行に要している時間は、プロファイラで調べたところ、CPU時間の70%程度だった。ひとことで言えば結構消費している。 しかし、evaluateは単にstandpatを返すだけのこともあるので、実際に局面の評価を行なった回数とは異なる。 そこで、 1) 探索したnode数 2) 1)のうち、evaluateを呼び出した回数 3) 2)のうち、実際に局面の評価を行なった回数 は、それぞれ別個に考
USIに文句を言うだけ言う http://d.hatena.ne.jp/merom686/20111217 まあ、USIプロトコルがいろいろアレであることは、いまさら言うまでもないことなのですが、なぜこんなプロトコルがコンピューター将棋の標準になっているかと言うと、将棋所という素晴らしいUIが採用したからに他なりません。 その将棋所の作者はコンピューター将棋を自らは作っておらず、何が必要かあまりよくわかっていないのだと私は理解しています。 まず、将棋所のサンプルについているLesserKaiのソースもかなりでたらめなコードです。例えば、将棋所のサンプルのLesserKaiのソースで、時間をparseしているコードは次の部分です。 void USIUtil::ParseAllTimes(const char *buf, int SorE) { string goStr = buf; if (
昨日の記事で、x64用にコンパイルしなおすメリットを書きましたが、通常は以下のようなデメリットのほうがそれらを上回ります。 ポインタ、関数アドレスなどがすべて64bit幅になるので、プログラムのサイズが増えます。その結果、L1/L2/L3 cacheに収まらなくなることがあります。プログラムのサイズだけではなく、ポインタなどを含む構造体のサイズも膨らみます。あと4byteではなく8byteでalignした場合などは、配列のデータサイズも著しく膨張します。これまたL1/L2/L3 cacheに収まらなくなる原因になります。 構造体サイズが増えた結果、アドレッシングがしきれなくてシフトや掛け算が必要になることがあります。 mov ebx , [ebp + eax * 8 + 123]; x86でよく見かけるアドレッシングですが、x86でも、倍率は、1,2,4,8のままです。何故AMDが命令拡張
棋譜からの学習について保木さんにメールで直接教えていただきました 保木さんのご厚意により、メールで質問して構わないということでしたので、私は厚かましくもメールで根掘り葉掘り質問させていただきました。 保木さんに教えていただいた情報のうち、保木さんが公開して良いとおっしゃられた部分に関してはこのブログにて公開させてもらいます。 今回はBonanzaで学習に使用した棋譜についてのことです。以下は保木さんから私へのメールです。 学習に使用したプロ棋士の棋譜 45833 局です。入玉模様の棋譜は1000局以 下だと思います。入玉の局面を Bonanza は殆ど評価することが出来ません。 昔はアマチュアの棋譜で入玉模様のサンプルを増やしていたのですが、最近は しておりません。しかし、将来また使用するかもしれません。用いた Xeon は Harpertown 程度のものだったと思います。 学習の過程で
■ Bonanzaの評価関数はどのようなものか?【KPP編】 駒割、KKPに続いて、今回はKPPを見ていく。 以上でBonanzaの評価関数はすべて終了。 ■ KKP KPPには、プロファイラによるとCPU時間の70%を要している。make_listは5%なので、これと併せると実に全体の75%を占めることがわかる。KKPはevaluate.cのevaluate関数で行なわれている。 score = 0; nlist = make_list( ptree, &score, list0, list1 ); sq_bk = SQ_BKING; sq_wk = Inv( SQ_WKING ); sum = 0; for ( i = 0; i < nlist; i++ ) { k0 = list0[i]; k1 = list1[i]; for ( j = 0; j <= i; j++ ) { l0
GPWSで発表された田中哲郎先生の「入玉指向の将棋プログラムの作成」について思うところがありまして、以下にだらだらと書いておきます。なお、本論文は以下のURLから読めるようです。 https://ipsj.ixsq.nii.ac.jp/ej/?action=pages_view_main&active_action=repository_view_main_item_detail&item_id=78250&item_no=1&page_id=13&block_id=8 元の論文のアイデアは、「王の入玉に関する機動性(?)を評価して評価関数に加点しよう」というものでして、玉は左上・真上・右上にのみ進めて、相手の利きおよび自駒がある場所には移動できず、入玉できる経路があるかどうかを調べるというものです。 入玉に関して、入玉を阻止している駒で評価するのではなく玉の入玉経路の有無を評価関数に反映
私は、いまやコンピュータ将棋のトレンドである「棋譜からの学習」を使わずになんとかならないかと考えています。それは、もうそろそろプロにも迫る勢いであるコンピュータ将棋にとってプロの棋譜にそんなに価値はないだろうと思うからです。 私の考えている方法は大きくわけて2つあります。 1) うまく将棋というゲームをモデル化すれば、パラメータは計算でなんとかして算出できるのではないか? 2) 棋譜からの学習ではなく、自己対戦をしながら、(たとえば)探索深さ20手での最善手を教示信号として自動学習できないか。 2) は、保木さんに相談したところ、次のようにアドバイスをいただきました。 オセロの Logistello も中盤の学習でこのような方法を用いています。しかし、チェス系 ではこのような方法ではうまくいかないようです。15手程度の探索結果を教師データと して、1手探索結果を最適にするように学習する等し
■ はじめに Bonanzaの指し手生成/合法手判定は結構ややこしく、ややこしい原因は将棋用語にいくつかの用語が不足しているからなのですが、ここではその不足している用語を新たに定義しながら、自分自身のためのメモを書き残しておきます。 自分用のメモですので文章は著しく読みにくいと思います。(すみません。) ■ 王手がかかっているか、いないのかで分類する まず、将棋には 1) 自玉(手番側)に王手がかかっている局面 2) 自玉(手番側)に王手がかかっていない局面 の2つがあり、あらゆる局面はこの2つに分類できます。 ちなみに、 3) 敵玉(非手番側)に王手がかかっている局面 4) 敵玉(非手番側)に王手がかかっていない局面 のような分類は不可能で、3)は手番側がその敵玉を取れるはずで、すなわち、敵は直前の王手を無視して回避する手を指さなかったということなのでその直前の指し手が非合法手であると言
次のページ
このページを最初にブックマークしてみませんか?
『Bonanzaソース完全解析ブログ』の新着エントリーを見る
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く