ADADELTAの論文を読もうじぇ
タイトルの通りなのじぇ。
論文はここにあるのじぇ
http://www.matthewzeiler.com/pubs/googleTR2012/googleTR2012.pdf
第3.2章から何言っているのかわからなくなってしまったのじぇ.....
Unitってなんなのじぇ.....
まあ備忘録的にここにまとめて残しておくのじぇ。
~~ABSTRACT~~~
Adadeltaとは
勾配効果法の為の次元ごとの学習率調整方法
(ここで言う次元とはベクトルの要素数のことだと考えられる。例.(x,y,z):3次元)
(特徴)
ファーストオーダーインフォメーションしか用いない
(ファーストオーダーインフォメーションとは一回微分の結果のことだと考えられる)
何もなしのSGDを超える小さな計算時間
外乱に対する耐性
~~1 INTRODUCTION~~
SGDでは学習率ハイパーパラメータ(η)は手動で与えなければならなかった
(ADADELTA アプローチの利点)
手動で学習率を決める必要が無い
ハイパーパラメータ関係ない
次元ごとに学習率を分ける。
計算量が少ない
外乱に耐性がある
localまたは分散のある環境にも適応できる。(どういうこと?)
~~2 RELATED WORK~~
Newton methodではヘッセ行列の逆行列を使って計算をする。
しかしこれでは時間がかかりすぎるので
一回微分の結果を用いるか2回微分の値を予測するかする改良をする必要がある。
~~2.1 学習率焼きなまし~~
ローカルミニマムでは学習率を下げればよい学習率であるといえる。
極小値の周りで値は振動してしまうのでこれを防ぐために、一つの方法としては、
学習率が下がってくるに従ってパラメータの更新を遅くする方法もある。
しかし、その代わりに何epoch(epochとはなに???)が経過したかによって学習率を焼き鈍す方法が提案されている。
~~2.2 次元毎の一回微分Method~~
次元あたりに異なる学習率を用いる方法を紹介する
~~2.2.1 Momentum~~
Momentum Methodの主な考え方は
勾配が同じ方向を向いて変わらないdimensionには学習を加速させ、勾配の符号が変化し続けているところでは学習率を下げる。
これは前回のパラメーター更新の値を指数関数的に減衰させながら利用する事によって実装されている。
ρは前回のパラメーター更新の値の減衰をコントロールするための定数。
谷底が緩やかに傾いているような谷を想像すれば良い
谷底に沿うような方向には学習率を上げて、谷をまたぐ方向には学習率を下げることで谷をまたぐ方向の振動を和らげる。
~~2.2.3 ADAGRAD~~
この方法は一回微分の結果に頼っているが2回微分の結果と焼きなましの特性も持っている。
分母はこれまでの全次元ごとの学習率の勾配のL2ノルム
ηはすべての次元で共有される学習率
手動で調整しなければならないηは全次元共通ではあるけれども、それぞれの次元は自分の動的学習率を持っている。
学習率は勾配の大きさの逆数に依存するので大きな勾配は小さな学習率小さな勾配は大きな学習率を持つ。
最初の勾配が大きいものであれば残りの学習率も小さいものになってしまう
学習率はどんどん小さくなっていくので偶然0になって学習が停止してしまうことも起こりうる。
~~2.3 2回微分を用いたメゾッド~~
2回微分の情報はとても有益であるが計算に時間がかかるため
ヘッセ行列の対角成分の近似方法が提案された。
~~3 ADADELTA~~
ADAGRADの2つの欠点を改善させるためにADADELTAのアイディアをこの論文に発表する。
ADAGRADの欠点
(1)トレーニング中ずっと学習率が低下していってしまう
(2)学習率を手動調整しなければならない
~~3.1 idea1 蓄積に直近何回まで蓄積するかを設ける~~
ずっと勾配の2乗和を蓄積する代わりに、直近何回蓄積するかの窓を設ける。
これによって分母は無限まで大きくなることはない
ずっと誤差の2乗和を保存しておくのは効果的ではないので指数関数的減衰させていく。
~~3.2 idea2 ヘッセ行列の近似により、Unitを修正する~~
(Unitとは何なのか??)
パラメータの更新を考えるときunitsは調和されなければならない。
パラメータの変化はunitsの変化でもあるはずである
SGDやMomentumと言った方法ではunitsは勾配と結びついていた。
しかし、2回微分を用いる方法ではunitはパラメータの更新と関係がある????
(此処から先はよくわからない.......)
肉じゃが牛丼を食べるのじぇ!
某大御所コンピューター将棋開発者がこんなことをつぶやいていたのじぇ。
すき家の牛丼にファミマの肉じゃがぶっかけて、レンジでチンすると肉じゃが味のつゆだく風になってめちゃうまい。
— やねうら王 (@yaneuraou) 2016年7月15日
これはクックパッド、ランキング上位不可避ですわwww pic.twitter.com/2f2urhR8c9
ゆゆっ!?
おいしそうだよ~~!れいみゅも食べてみたいよ!
まりちゃもそう思うのじぇ!
早速買ってきて食べてみようじぇ!!!
まりちゃ。れいみゅ。あんまりファストフードばかり食べるのは都会派じゃないわ!
お野菜さんを使ったバランスの良いごはんさんもちゃんと食べないと!
まりちゃは若いからだいじょうぶなのじぇ~~
じゃあ早速買ってくるのじぇ!!!!
(30分後~~~)
ただいま~なのじぇ!買ってきたのじぇ!
ゆゆっ?すき家じゃなくって吉野家の牛丼なの?
すき家は家の近くになかったので諦めて吉野家なのじぇ!
しかも牛丼じゃなくて豚丼ね...
牛丼は豚丼よりも50円高かったのじぇ!
50円ぐらいケチらずに払いなさいよ^^;
まあたまにはだきょうっ!も必要なのじぇ!
早速料理するのじぇ~~♪
肉じゃがを上にかけてレンジでチンするだけだよ!
簡単だね!
完成なのじぇ!さあ早速食べようじぇ!!!
むーしゃむーしゃ...
・・・・あれ?そんなにおいしくないのじぇ?
確かにそんなにおいしくないね.....
これ肉じゃがをかけてないほうが美味しいのじぇ.......
吉野家の豚丼には肉じゃがは合わなかったみたいなのじぇ....
今度はちゃんとすき家の牛丼に肉じゃがかけて食べるのじぇ.....
~~今回のまとめ~~
吉野家の豚丼にはファミマの肉じゃがは合わなかった^^;
今度はちゃんとすき家の牛丼にファミマの肉じゃがかけて食べる
差し手生成部なのじぇ
ふうぅ~とりあえずやねうら王とAperyの差し手生成部を読んだのじぇ
お疲れさまね…..
ざっくりとした概略を文字で書くならこんな感じなのじぇ
やねうら王について
movepickerのmoves[600]が差し手配列 差し手生成関数は探索関数中のMovePicker mp(pos,ttMove);から呼び出される。 MovePicker(const Position& pos_,Move ttMove) の中で呼び出される template<MOVE_GEN_TYPE GenType> ExtMove* generateMoves(const Position& pos, ExtMove* mlist) 先手後手で呼び出す関数を分けるもの template<MOVE_GEN_TYPE GenType, bool All> ExtMove* generateMoves(const Position& pos, ExtMove* mlist,Square sq = SQ_NB) 指し手のタイプ別に分けるものの3種類あり template<MOVE_GEN_TYPE GenType,Color Us,bool All> ExtMove* generate_general(const Position& pos, ExtMove* mlist,Square recapSq=SQ_NB) 指し手の駒種別に差し手を生成するのは ~駒移動 struct GeneratePieceMovesでありこれには5しゅるいあり、 角飛車の移動 からの make_move_target 成れない手による移動 からの make_move_target 成れない手(王を除く) からのMAKE_MOVE_TARGET(target2); 歩の移動 からのmake_move or make_move_promote 桂馬香車銀の移動 からの make_move_target ここで差し手は生成される。 ~駒うち struct GenerateDropMovesの内部の (歩)FOREACH_BB(target2, sq, { mlist++->move = make_move_drop(PAWN,sq); }); (どこでも打てる)make_move_drop (香車桂馬)FOREACH_BB(target2, sq, { UNROLLER1({ mlist++->move = (Move)(drops[i] + sq); }); });
Apery twgについて
movepickerのMoveStack leagalmoves_[594]が差し手配列 探索関数の中のnextmove()でgonextphaseが呼ばれ goNextPhaseでフェーズにより分けられながら差し手が生成されている(!タイプ別差し手遅延生成!) その中で template <MoveType MT> MoveStack* generateMoves(MoveStack* moveStackList, const Position& pos)というのが呼ばれている (駒うちはgenerateMoves<Drop>(currMove(), pos());) その中でさらに色別で分けられ(template <MoveType MT, Color US, bool ALL = false>struct GenerateMoves ) その中で全駒種別に用意された(template <MoveType MT, PieceType PT, Color US, bool ALL> struct GeneratePieceMoves)の中の 成り makePromoteMove<MT>(Pawn, from, to, pos); 成らず makeNonPromoteMove<MT>(Pawn, from, to, pos); この関数の中の template <MoveType MT, PromoteMode PM> inline Move selectedMakeMove(const PieceType pt, const Square from, const Square to, const Position& pos) この関数内でようやく movetype別差し手生成が行われる 駒打ち generateMoves<Drop>(currMove(), pos())からの (色分け) template <MoveType MT> MoveStack* generateMoves(MoveStack* moveStackList, const Position& pos) からの (種類分け(drop固定)) template <Color US> struct GenerateMoves<Drop, US> (駒打ち) template <Color US> MoveStack* generateDropMoves(MoveStack* moveStackList, const Position& pos, const Bitboard& target)からの makeDropMove
やたらと複雑ね…
図にするとこうなるのじぇ
やねうら王
Apery
同じような名前の関数templateとそれに包まれた同じような関数templateが多すぎるのじぇ!
分かりにくいと思うけど我慢するのじぇ
多分この呼び出し構造だけでもわかれば読んでいくのも楽になるはずなのじぇ
間違ってるところがあれば指摘してほしいのじぇ
ちょっと複雑すぎるよ!なんでこんな似たような名前のtemplate関数ばっかりなの!?
似たような名前でわかりにくいのはまりちゃも同意なのじぇ。
これにはどういった最適化に関する意味があるのかはまりちゃには分からないのじぇ。コードが読みにくくなるだけだと思うのじぇ。
でもあのやねうら王もAperyもわざわざこんなことをするということは何か意味があると思っているのじぇ。
でもtemplateをたくさん使っているのはなぜだか分るのじぇ
多分過コーディングを防ぐためであると思うのじぇ
過コーディング??
なんかよくわからないけどあんまりコードが長くなりすぎると棋力が下がってしまうらしいのじぇ。
(平岡さんの2016年3月2日のツイート参照)
それとtemplateってどう関係があるのかしら?
ちょっとまりちゃもあんまりよくわかってないけど
やねうら王さんのコンピューター将棋ブログの
Stockfish完全解析のsearch 探索部の記事の
search.cppのtemplate
(勝手にリンクを張るのは怖いのじぇ)
多分ここの部分もそういう原理だと思うのじぇ
template<MOVE_GEN_TYPE GenType,Color Us,bool All>
ExtMove* generate_general()
にconst Bitboard targetってのがあるし…
ごめんなさいこの記事プログラミングあんまりよくわかってないときに書いた記事だから信用しないでください(;´・ω・)
templateについてはmerom686さんに昔聞いてみたことがあるのでここを読んでください(´・ω・`) ask.fm 条件分岐を減らせたり、データを読みとる必要がなくなったりして高速化できることがtemplateを使っている理由だと今では思っています
平岡さんの言っていた過コーディングについてはいまだに何のことなのかわかってないです(´・ω・`) 過コーディングはtemplateとは関係がないような気がしますね
ビットボードなのじぇ2
今回もbitboardについての記事を書いていくのじぇ
今回はbitboardの初期化編なのじぇ
なかなか難しかったのじぇ。
これのせいで今日の2限の授業はいつの間にか終わってたのじぇ
ちゃんと授業ききなさいよ...
まあいいのじぇ。
ここで一つ断っておくべきことがあるのじぇ
この初期化はかなり理解が難しくてこの記事の内容があっている保証さんはないのじぇ
あと自分でコードを読んでみて1点分からなかったところがあるので誰か教えて欲しいのじぇ
「なぜ飛車は無条件全域から王に王手をかけれるのか」
これは解決した。飛車は邪魔ゴマがいないとき盤面の任意の升に2回移動でいけるから、どこからでも王手をかけれる
ということなのじぇ。
詳しい人いればコメント欄にでもおねがいするのじぇ。
Bitboard::init()における初期化には簡単で読めばすぐわかるような内容と
読んでもすぐには分からないような内容があるのじぇ
ここではそのわかりにくい個所のみ解説していくつもりなのじぇ。
具体的には
4) 遠方利きのテーブルの初期化
7) 二歩用のテーブル初期化
9) 王手となる候補の駒のテーブル初期化
のことなのじぇ。もしかしたら他にも本質的に難しい個所はあるかもしれないけれど
まいちゃはそれすら気が付いていないのかもしれないのじぇ
まあとりあえず(4)の解説を始めるのじぇ正直(4)が一番鬼門なのじぇ
これを考え付いたAperyの平岡さんはすごい人なのじぇ
ここでは飛車と角の邪魔ゴマの位置を考慮した利きを算出しているのじぇ
ここではfor (Piece pc : {BISHOP, ROOK})というループ文で角の利きと飛車の利きを計算する部分のコードをひとつにまとめてるけどそれだと多少複雑でわかりにくくなってしまうのでここでは飛車についてのみ考えるのじぇ
飛車についてのみ考えた(4)の部分のコードはこうなるのじぇ
(まあコードにコメントもつけてるので解説なくてもわかる人はコードを見るだけでもわかるかもしれないのじぇ)
// 角と飛車の利きテーブルの初期化 // 使用されている箇所を見るとここですでに障害物の位置が考慮されている.... // 邪魔ゴマを考慮した大ゴマの利きを格納するテーブルのアドレス //RookEffect[495616+1] //495626=(1<<12)*49+(1<<14)*4+(1<<13)*28 Bitboard* effects = RookEffect; // sqの升に対してテーブルのどこを引くかのindex int* effectIndex = RookEffectIndex; //邪魔ゴマを無視した飛車の利きがきいてる部分が1になってるbitboard Bitboard* masks = RookEffectMask; int index = 0; //飛車の利きのある場所は先手後手に対して同じである for (auto sq : SQ) { effectIndex[sq] = index;//sqに飛車を置いた時の邪魔ゴマを考慮した周りへの利きは一次元配列のindex番目から始まる。 // sqの地点にpieceがあるときにその利きを得るのに関係する升を取得する masks[sq] = calcEffectMask(sq, pc);//ここでsqに駒を置いた時の周りへの利きのbitboardが出来上がる。 //p[0]とp[1]に被っているところはない ASSERT_LV3(!(masks[sq].p[0] & masks[sq].p[1])); // sqの利きはのある場所bit立っているのか const int bits = masks[sq].pop_count(); //ocuppied bitboardは利きを遮る邪魔ゴマの位置 //つまり利きのある場所の数をnとすると2^n乗だけ邪魔ゴマの位置としては通りがある const int num = 1 << bits; //iを1ずつnumまで増やしていくことですべての邪魔ゴマの通りを考えることができる for (int i = 0; i < num; ++i) { Bitboard occupied = indexToOccupied(i, bits, masks[sq]);//index(iのこと)からoccupied_bitboardを作る //利きのある場所における障害物の位置はnum(1 << bits)通りある //障害物の位置を考慮した利きをここで計算する。 //index どこに利きの原因となる駒があるかによるインデックス occupiedToindex 障害物の位置の組み合わせによるインデックス effects[index + occupiedToIndex(occupied & masks[sq], masks[sq])] = effectCalc(sq, occupied, pc); } index += num; } // 盤外(SQ_NB)に駒を配置したときに利きがZERO_BBとなるときのための処理 effectIndex[SQ_NB] = index;
// 飛車をsqにおいたときに発生する利き(邪魔ゴマは考慮しない) auto calcEffectMask = [](Square sq, Piece piece) { Bitboard result; ASSERT_LV3(piece == ROOK); result = RANK_BB[rank_of(sq)] ^ FILE_BB[file_of(sq)];//XOR sqの地点で利きは交わるがそこは関係ないのでXORでいい // 飛車が外周に居ない限り、その外周升は利きの計算には関係ない。 if (file_of(sq) != FILE_1) { result &= ~FILE1_BB; } if (file_of(sq) != FILE_9) { result &= ~FILE9_BB; } if (rank_of(sq) != RANK_1) { result &= ~RANK1_BB; } if (rank_of(sq) != RANK_9) { result &= ~RANK9_BB; } // sqの地点は関係ないのでクリアしておく。 result &= ~Bitboard(sq); return result; };
//indexの0と1の位置でどこに邪魔ゴマを置くか決めてresultのそのマスのbitを立てていくための関数 //indexのループは子の関数の外側にある auto indexToOccupied = [](const int index, const int bits, const Bitboard& mask_) { auto mask = mask_; auto result = ZERO_BB;//何も入っていないbitboard for (int i = 0; i < bits; ++i)//bitsは邪魔ゴマを考慮しない利き中の立っているbit数 { const Square sq = mask.pop();//邪魔ゴマを考慮しない利きから拾ってきた立っているbitの位置 if (index & (1 << i))//indexはどこに邪魔ゴマを置くかという情報を0と1で持っている result ^= sq;//障害物の位置としてresultに足す } return result; };
// Rookの障害物を考慮した利きの範囲を調べて bitboard で返すための関数。 // occupied 障害物があるマスが 1 の bitboard auto effectCalc = [](const Square square, const Bitboard& occupied, const Piece piece) { auto result = ZERO_BB; // 角の利きのrayと飛車の利きのray const SquareWithWall deltaArray[4] = { SQWW_U, SQWW_D, SQWW_R, SQWW_L }; for (auto delta : deltaArray){ // 壁に当たるまでsqを利き方向に伸ばしていく for (auto sq = to_sqww(square) + delta; is_ok(sq); sq += delta) { result ^= to_sq(sq); // まだ障害物に当っていないのでここまでは利きが到達している if (occupied & to_sq(sq)) // sqの地点に障害物があればこのrayは終了。 break; } } return result; };
ゆゆゆ...わからないところがたくさんあるよ...
最初のRookEffect[495616+1]っていうところからわからないよ...
3次元配列になってくれてたらまだわかるかもしれないけど一次元配列さんにされるとわからないよ....
じゃあまずそこから説明していくのじぇ
RookEffectっていうのはすべての飛車の位置に対するすべての邪魔ゴマの位置を考慮したひしゃのききが格納されている配列なのじぇ
まずはこの図を見てどこに飛車があればどれだけのマスに利きが生まれるのかを理解してほしいのじぇ
一番端のマスには飛車が一番端のマスに居ない限り利きを作らないということに注意してほしいのじぇ
ここでこの飛車の利きのある青色の升に駒をおいてみるとしようじぇ。
駒は全く置かなくてもいいし青い升すべてにおいてもいいのじぇ。
そうすると駒の置き方の総数は(そこに駒を置くかおかないか)^(駒を置けるマスの総数)のじぇ
つまり駒を置けるマスをn升とすると
2^n通りあるのじぇ。
これはbit演算を用いると
1<<nということなのじぇ
またこの図の場合を考えると
2進数で14桁ある整数(i)を用いて
1番下の桁に1一のマスに邪魔ゴマを置くかどうかの情報を格納する
2番下の桁に2一のマスに邪魔ゴマを置くかどうかの情報を格納する
3番下の桁に3一のマスに邪魔ゴマを置くかどうかの情報を格納する
....
とすると
2一と3一のマスに邪魔ゴマを置くという情報は
i=000000000000110
とあらわされるのじぇ。
ということはつまり
iの値を000000000000000から11111111111111になるまで1ずつ増やして行くと
すべての邪魔ゴマの配置を表現できるということなのじぇ
ということはすべての飛車の位置に対するすべての邪魔ゴマの位置を考慮したひしゃのききを格納するためには
(1<<12)49+(1<<14)4+(1<<13)*28=495626だけbitboardがひつようということになるのじぇ
ここに飛車が盤上にない時のことを格納するための場所をつけ足して+1しておけばいいのじぇ。
これでRookEffect[495616+1]はりかいできたはずなのじぇ。
ゆゆっ!これはすごいよ!
後はさっき解説した
iの値を000000000000000から11111111111111になるまで1ずつ増やして行くと
すべての邪魔ゴマの配置を表現できるということを利用して
邪魔ゴマの位置を格納したoccupied bitboardを作って
それをもとに邪魔ゴマの位置を考慮した飛び利きを格納していけばいいだけなのじぇ。
// sqの利きはのある場所bit立っているのか const int bits = masks[sq].pop_count(); //ocuppied bitboardは利きを遮る邪魔ゴマの位置 //つまり利きのある場所の数をnとすると2^n乗だけ邪魔ゴマの位置としては通りがある const int num = 1 << bits; //iを1ずつnumまで増やしていくことですべての邪魔ゴマの通りを考えることができる for (int i = 0; i < num; ++i) { Bitboard occupied = indexToOccupied(i, bits, masks[sq]);//index(iのこと)からoccupied_bitboardを作る //利きのある場所における障害物の位置はnum(1 << bits)通りある //障害物の位置を考慮した利きをここで計算する。 //index どこに利きの原因となる駒があるかによるインデックス occupiedToindex 障害物の位置の組み合わせによるインデックス effects[index + occupiedToIndex(occupied & masks[sq], masks[sq])] = effectCalc(sq, occupied, pc); } index += num;
2歩テーブルの初期化も内容は飛び利きの初期化と似たことをやっているのでここにコードだけはっておくのじぇ
//511=2^9-1//筋が9個あるうちのどこに歩があるかの組み合わせの数(ex 1筋に歩 3筋に歩などなど。。) for (int i = 0; i <= 0x1ff; ++i) { Bitboard b = ZERO_BB; for (int k = 0; k < 9; ++k) if ((i & (1 << k)) == 0)//iが 000001100であれば b |= FILE_BB[k];//bは3番目と4番目の筋のところに1が入ったbitboardになる。 //PAWN_DROP_MASK_BB[512] i番目の筋には歩を打てないときには1<<(9-i)に1が格納される。 //bit0..9筋に歩が打てないなら1, bit1..8筋に, …, bit8..1筋に歩が打てないなら1 PAWN_DROP_MASK_BB[i][BLACK] = b & rank1_n_bb(WHITE, RANK_8); // 2~9段目まででよい(どうせ1段目には歩は打てない) PAWN_DROP_MASK_BB[i][WHITE] = b & rank1_n_bb(BLACK, RANK_8); // 1~8段目まででよい }
平岡さんtwitterを見てる限りではわからなかったけれどすごい人なのね,,,
これを使えばrotated bitboardなんて必要ないし
AVX2以降に使えるPEXTを使えばmagic bitboardも必要なくなるのじぇ
本当にすごい人なのじぇ
~~追記~~
「なぜ大ゴマの利きは一番端の段、筋には伸びないのか」
「なぜ大ゴマの利きはp[0]とp[1]でAND演算をした時に重なる部分がないのか」
これは1~7筋目を格納しているbitboardのp[0]、8~9筋目を格納しているp[1]
の中に合計で飛び利きがあるマスが何マスあるかを求めるためにPEXTという命令を使うんだけれどそれを使える範囲が64bitだけであるので、
もし128bitすべてにたいして飛び利きのあるマスの数を調べようとすると2回pextを呼び出さなければいけなくなってしまい時間がかかってしまうので
何とか1回のPEXTで済むようしよう考えられた方法なのじぇ。
具体的な方法としてはp[1]とp[0]の利きの場所を絶対に被らないようにしてp[1]とp[0]のOR演算をして、利きの場所をどちらかにまとめようということなのじぇ
この場合を例にとって考えるのじぇ。
この図をp[0]に格納されているところ
p[1]に格納されているところに分けた結果がこうなのじぇ
そしてOR演算した結果がこれなのじぇ
これを見れば確かに利きの範囲はかぶってないことがわかるのじぇ
他の場合も考えてみればわかると思うけれど利きの範囲は絶対かぶらないのじぇ
これは大ゴマの利きを一番端の段、筋には伸ばさないことと、p[1]とp[0]を1~7筋目と8~9筋目に分けている2点のおかげなのじぇ
確かに利きが重なる部分はなくなったよ!でもよく考えてね!ふつう大ゴマの利きは端っこまで聞いてないとおかしいよ!
飛車が端っこのマスの駒をとれないような動きしかできなくなっちゃうよ!
大丈夫なのじぇ利きさんは最終的に邪魔ゴマの位置を考慮した一次元配列を作るときにちゃんと端っこのマスまできかせるようにしてあるのじぇ。
端まで利きをきかせないのは邪魔ゴマの位置として考えられる場合の数を考えるときだけなのじぇ
邪魔ゴマの位置を考えるとき邪魔ゴマが一番端のマスに居てても、
利きはその駒の上まで伸ばすことができるのでそれは別にそこに邪魔ゴマがないのと一緒なのじぇ
だから別にこの部分ではこれでいいのじぇ。
なるほど!とっても賢いんだよ!ゆっくりりかいしたよ!
それともう一つ
「なぜp[0]の63bit目を0にしておくひつようがあるのか」
についてまりちゃが考えた理由をここでいっておくのじぇ。もしかしたら間違ってるのかもしれないのじぇ
63bit目を空にしておくのはさっき述べたようにPextを一回で済ますためにbitboardをOR演算する必要があるためなのじぇ。
64bitの数え方は0~63であり、p[0]には7筋目まで格納されるので9かける7の0~62bitまでが盤として必要なのじぇ
つまり63ビット目はあまりであり、そこをpextで数えてしまわないように必ず0にしておくということだとまりちゃはかんがえているのじぇ。
この考え方が正しいことの理由付けはAll_BBの定義の仕方なのじぇ。
その部分のコードはこうなっているのじぇ
Bitboard ALL_BB = Bitboard(UINT64_C(0x7FFFFFFFFFFFFFFF), UINT64_C(0x3FFFF));
0x7FFFFFFFFFFFFFFFというのは63bitが立っている整数で64bit目は立っていないのじぇ
よって使わない部分のbitを0にしておくために63bit目は絶対立てないようにするのじぇ
次回はほかの部分の初期化について説明していくのじぇ
ビットボードさんなのじぇ
まいちゃ「ゆっくりしていくのじぇ
今日はコンピューター将棋で使われるビットボードさんについてなのじぇ
やねうら王のソースコードさんを見ながらべんきょうしていくのじぇ」
れいみゅ「ゆゆっ!?すごくむずかしそうだよ!」
まいちゃ「まいちゃじしんもそんなにビットボードさんを理解しているわけじゃないのじぇ
今リアルタイムで理解しながら記事を書いているのじぇ」
まいちゃ「今回は難しいことは考えずbitboardにはどんな種類があるのかを見ていくのじぇ
初期化や更新詳しい利用法はまたこんどなのじぇ」
まいちゃ「ビットボードさんはコンピューター将棋やコンピューターチェスで用いられる盤面を表すデータ構造なのじぇ
普通はban[9][9]やban[9*9]といった配列さんを使いたくなるところを64bit整数を二つまたは128bit整数を用意して0と1の組み合わせでそのマスに駒があるのかないのかを表現していくのじぇ」
ありす「でもすべてのデータを0か1で表現するのはすごくたいへんそうね。。。」
まいちゃ「ゆゆっ!まいちゃも昔は盤面のすべてのデータさんをbitboardであらわすのだろうと勘違いしてたのじぇ
でもすべてのデータをbitboardで持つわけではないのじぇ!」
「どういうこと?」
「positionクラスの Piece board[SQ_NB]をみるのじぇ
これは16bit整数型の配列なのじぇ!ここに「このマスにはどの種類の駒があるか」が格納されているのじぇ!
ここは配列型と変わらないのじぇ!
ちなみにAperyにもPosition構造体に
Piece piece_[SquareNum]というのがちゃんと用意されているのでやねうら王だけの仕様というわけではないと思うのじぇ! 」
「ちゃんと配列型のデータ構造も持っていたのね
なんだか恐怖心がうすらいだわ♪」
「難しく考えすぎず
利きを高速に作ったり、駒を移動させる場所移動させる前の場所を決めたり、王手の高速な判断のためのテーブルを用意しておくために
128bitという超ミニマムサイズでテーブルを作ることができるbitboardが使われると思っておけばOKだとと考えられるのじぇ!
」
「ちなみにboard[SQ_NB]は盤面の出力や、
Piece piece_on(Square sq) const { return board[sq]; }と関数で包まれて、
駒を置いた時の利きの計算のための駒の種類の取得や王手をかけた駒の種類の取得、hashの計算
指し手の合法性チェックやSEE(static exchange evaluation)等といった
sqにある駒の種類を取り出したいときにつかわれているのじぇ!
」
「簡単なbitboardのおさらいをしておくのじぇ
bitboard自体は
union { uint64_t p[2];//64bit型2つ __m128i m; //128bit型 };
で構成されているのじぇ
チェスだと盤面が88なので64bitで収まるけれど
将棋は99なので81bit整数なんてないので(2進数の関係)128bit整数を使うのじぇ
」
じゃあここからは今日の本題bitboardテーブルの種類について説明していくのじぇ
Position::occupied[COLOR] 先手か後手か、いずれかの駒がある場所が1であるBitboard(駒の種類は考えない) 駒をとらない移動を生成するときに移動先(target)の候補としてこれを反転させてもちいる 駒をとる手を生成するときに相手の駒がどこにいるのかの情報を与える 飛び利きの範囲を計算するときに障害物の位置として用いる Position::piece_bb[PIECE_TYPE_BITBOARD_NB][COLOR_NB]; 駒種別のその種類の駒が存在する升を表すBitboard これを用いて指し手のfromを生成する pos.pieces(Us, Pt) として使われる Bitboard FILE1_BB = Bitboard(UINT64_C(0x1ff) << (9 * 0), 0);//p[0]について Bitboard FILE2_BB = Bitboard(UINT64_C(0x1ff) << (9 * 1), 0); Bitboard FILE3_BB = Bitboard(UINT64_C(0x1ff) << (9 * 2), 0); Bitboard FILE4_BB = Bitboard(UINT64_C(0x1ff) << (9 * 3), 0); Bitboard FILE5_BB = Bitboard(UINT64_C(0x1ff) << (9 * 4), 0); Bitboard FILE6_BB = Bitboard(UINT64_C(0x1ff) << (9 * 5), 0); Bitboard FILE7_BB = Bitboard(UINT64_C(0x1ff) << (9 * 6), 0); Bitboard FILE8_BB = Bitboard(0, 0x1ff << (9 * 0));//p[1]について Bitboard FILE9_BB = Bitboard(0, 0x1ff << (9 * 1)); 筋を表すBitboard 0x1ff=511は9bitすべて1でありやねうら王は縦型bitboardであるのでこれで筋は表現出来る Bitboard RANK1_BB = Bitboard(UINT64_C(0x40201008040201) << 0, 0x201 << 0); Bitboard RANK2_BB = Bitboard(UINT64_C(0x40201008040201) << 1, 0x201 << 1); Bitboard RANK3_BB = Bitboard(UINT64_C(0x40201008040201) << 2, 0x201 << 2); Bitboard RANK4_BB = Bitboard(UINT64_C(0x40201008040201) << 3, 0x201 << 3); Bitboard RANK5_BB = Bitboard(UINT64_C(0x40201008040201) << 4, 0x201 << 4); Bitboard RANK6_BB = Bitboard(UINT64_C(0x40201008040201) << 5, 0x201 << 5); Bitboard RANK7_BB = Bitboard(UINT64_C(0x40201008040201) << 6, 0x201 << 6); Bitboard RANK8_BB = Bitboard(UINT64_C(0x40201008040201) << 7, 0x201 << 7); Bitboard RANK9_BB = Bitboard(UINT64_C(0x40201008040201) << 8, 0x201 << 8); 段を表すbitboard 0x201= 513 は1bit目1 10bit目1 0x40201008040201は2進数にすると 1000000001000000001000000001000000001000000001000000000 9おきに1が入っているので段を表すbitboardとして用いることができる Bitboard FILE_BB[FILE_NB] = { FILE1_BB,FILE2_BB,FILE3_BB,FILE4_BB,FILE5_BB,FILE6_BB,FILE7_BB,FILE8_BB,FILE9_BB }; Bitboard RANK_BB[RANK_NB] = { RANK1_BB,RANK2_BB,RANK3_BB,RANK4_BB,RANK5_BB,RANK6_BB,RANK7_BB,RANK8_BB,RANK9_BB }; 各筋、段を表現するBitboard配列をまとめたもの Bitboard StepEffectsBB[SQ_NB_PLUS1][COLOR_][16]; 近接駒の利きを格納している 16というのは近接駒の種類(敵8自分8) 事前に駒がどこにいるときに盤のどこに利きが生まれるのかのすべての組み合わせを格納しているテーブル CheckCandidateBB[sq][Pt][color] 相手王がsqに居るときcolor側の駒がどこに居れば相手に王手をかけることができるかのテーブル これによってすぐに王手鏡面かどうかを判断できる Bitboard::init()の(9)で初期化されている [81][8][2] ptが7までしかないがこれは同じ動きをする駒を一つにまとめているからである check_candidate_bb()として使われる。 generate_checks()で x = 直接王手となる候補 const Bitboard x = (pos.pieces(Us, PAWN) & check_candidate_bb(Us, PAWN , themKing)) | (pos.pieces(Us, LANCE) & check_candidate_bb(Us, LANCE, themKing)) | (pos.pieces(Us, KNIGHT) & check_candidate_bb(Us, KNIGHT, themKing)) | (pos.pieces(Us, SILVER) & check_candidate_bb(Us, SILVER, themKing)) | (pos.pieces(Us, GOLD) & check_candidate_bb(Us, GOLD, themKing)) | (pos.pieces(Us, BISHOP) & check_candidate_bb(Us, BISHOP, themKing)) | (pos.pieces(Us, ROOK) ) | // ROOK,DRAGONは無条件全域 //TODO なんで無条件全域? (pos.pieces(Us, HDK) & pos.pieces(Us, BISHOP) & check_candidate_bb(Us, ROOK, themKing)); // check_candidate_bbにはROOKと書いてるけど、HORSE //TODO どいうこと? として直接王手となる候補を求めるために使われる PAWN_DROP_MASK_BB[512][COLOR_NB]; // 歩が打てる筋を得るためのBitboard // bit0..9筋に歩が打てないなら1 , bit1..8筋に , … , bit8..1筋に歩が打てないなら1 というbit列をindexとして、歩の打てるBitboardを返すためのテーブル。 2歩判定に使われる InFrontBB[COLOR][RANK]; // color == BLACKのとき、RANK段目よりWHITE側(1からn-1段目)を表現するBitboard。 // color == WHITEのとき、RANK段目よりBLACK側(n+1から9段目)を表現するBitboard。 これを用いてc側の香の利き = 飛車の利き & InFrontBB[c][rank_of(sq)]とすることができる。 香車の利きに関して使われている これを利用して敵陣と自陣が1になっているBitboardを表現することが出きる。 extern Bitboard LineBB[SQ_NB_PLUS1][SQ_NB_PLUS1]; 2升を通過する直線を返すためのテーブル line_bb(Square sq1, Square sq2) { return LineBB[sq1][sq2]; }のようにして使われる 空き王手判断に使う BetweenBB[SQ_NB_PLUS1][SQ_NB_PLUS1]; 2升に挟まれている升を返すためのテーブル(その2升は含まない) bitboard::init()で全マスとの関係に関して値が入れられる。 between_bb()関数に包まれていて、この関数を呼び出されることで使われる 飛び駒に王手をされているときにその間に駒を打つ処理をするときに使われる more_than_one((between_bb(from, ksq) & occ))により 駒をfromに置いた時にfromからksq(王の位置)までの間にほかの駒が存在しないかどうかのチェックに使われる(occはほかの駒がいる位置) b = between_bb(ksq, pinners.pop()) & pieces();により ksqと大駒とで挟まれている駒を列挙しpinされているかどうかのチェックに使う 大体は飛びゴマの王手処理にために使われる また inline const Bitboard around24_bb(Square sq) { return check_candidate_bb(BLACK, HDK, sq); }として あるマスの24近傍を返すためにもつかわれる これはやねうら王の長い利きの更新のために使われる(別に使わなくてもよい)
「つかれたよ!あまあまさんがたべたいよ!」
「もうちょっとだけ続くのじぇ
がまんするのじぇ
ここからは利きが格納されたbitboardなのじぇ」
Bitboard StepEffectsBB[SQ_NB_PLUS1][COLOR_NB][PIECE_TYPE_BITBOARD_NB2]; // 近接駒の利き // 3番目の添字がPIECE_TYPE_BITBOARD_LANCE,PIECE_TYPE_BITBOARD_BISHOP,PIECE_TYPE_BITBOARD_ROOK // のときは、盤上の駒の状態を無視した(盤上に駒がないものとする)香・角・飛の利き。 // また、PIECE_TYPE_BITBOARD_QUEEN,PIECE_TYPE_BITBOARD_CROSS00,PIECE_TYPE_BITBOARD_CROSS45 // は、馬+龍,十字方向に1升,×字方向に1升となる。 // 王の利き inline Bitboard kingEffect(const Square sq) { return StepEffectsBB[sq][BLACK][PIECE_TYPE_BITBOARD_HDK]; } のようにして関数に包まれながら使われる。 使用法としては一般的に利きが使用される目的通りの使用法である 駒の移動先の候補targetをしぼるために使われたりもする おそらくStepとは 盤上の駒を考慮しない利きにつけられる記号である。 Bitboard LanceEffect[COLOR_NB][SQ_NB_PLUS1][128];//128とはなに? ANS。64*2 邪魔ゴマの位置 香車の利き (occupiedを考慮している) bitboard::init()の(5)で求められる // --- 角の利き extern Bitboard BishopEffect[20224+1]; extern Bitboard BishopEffectMask[SQ_NB_PLUS1]; extern int BishopEffectIndex[SQ_NB_PLUS1]; // --- 飛車の利き extern Bitboard RookEffect[495616+1]; extern Bitboard RookEffectMask[SQ_NB_PLUS1]; extern int RookEffectIndex[SQ_NB_PLUS1]; この二つはinit()の(4)で初期化される
次はinfo内なのじぇ
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~stateinfo内 // 現局面で手番側に対して王手をしている駒のbitboard。Position::do_move()で更新される。 Bitboard checkersBB; ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~checkinfo内 // 動かすと敵玉に対して空き王手になるかも知れない自駒の候補 // チェスの場合、駒がほとんどが大駒なのでこれらを動かすと必ず開き王手となる。 // 将棋の場合、そうとも限らないので移動方向について考えなければならない。 // ※ dcはdouble check(両王手)の意味。 Bitboard dcCandidates; // 自分側(手番側)の(敵駒によって)pinされている駒 Bitboard pinned; // 自駒の駒種Xによって敵玉が王手となる升のbitboard Bitboard checkSq[PIECE_WHITE]; // 敵王の位置 Square ksq;
最後に差し手生成部なのじぇ
x(直接王手),yとかは省いたのじぇ
~~~~~~~~~~~~~~~~~~~~~~~差し手生成 移動先の候補の場所が1になっているbiboard Bitboard target generate_general()内にある const Bitboard target = (GenType == NON_CAPTURES) ? pos.empties() : // 捕獲しない指し手 = 移動先の升は駒のない升 (GenType == CAPTURES) ? pos.pieces(~Us) : // 捕獲する指し手 = 移動先の升は敵駒のある升 (GenType == NON_CAPTURES_PRO_MINUS) ? pos.empties() : // 捕獲しない指し手 - 歩の成る指し手 = 移動先の升は駒のない升 - 敵陣(歩のときのみ) (GenType == CAPTURES_PRO_PLUS) ? pos.pieces(~Us) : // 捕獲 + 歩の成る指し手 = 移動先の升は敵駒のある升 + 敵陣(歩のときのみ) //TODO pieces(~US)だけでいいの?歩の成りは?ANS歩以外をここでは考えてる (GenType == NON_EVASIONS) ? ~pos.pieces(Us) : // すべて = 移動先の升は自駒のない升 (GenType == RECAPTURES) ? Bitboard(recapSq) : // リキャプチャー用の升(直前で相手の駒が移動したわけだからここには移動できるはず) ALL_BB; // error のように生成される auto target2 駒が移動できる場所 つまり利きのある場所 を格納して置くbitboard targetをしぼるために使われる auto target2 = Pt == LANCE ? lanceEffect(Us, from, occ) : Pt == KNIGHT ? knightEffect(Us, from) : Pt == SILVER ? silverEffect(Us, from) : ALL_BB; // error target2 &= target;//上の条件でtargetを絞る
「結構おおいんだね!」
「この分章では説明が長かったのでおおく見えるけど種類としてはそこまで多くはないのじぇ
ここで紹介したbitboardの種類だけをリストアップすると
occupied
piece_bb
SquareBB
FILE
RANK
StepEffectsBB
PieceEffect
ALL_BB
ZERO_BB
CheckCandidateBB
PAWN_DROP_MASK_BB
InFrontBB
LINEBB
BetweenBB
checkersBB
dcCandidates
pinned
checkSq
Ksq
target
target2
見落としはあるかもしれないしあまり重要でないものは省いたけどこのくらいなのじぇ」
「ゆゆっ!?れいみゅからしたら3つ以上はたくさんなんだよ!ゆっくり理解してね!」
(...)
「次回はこれらのビットボードがどのように初期化されるかbitboard::init()の中を見ていくのじぇ
楽しみにするのじぇ!」
半導体工学 2016-5-20 状態密度とキャリア濃度
まりちゃ「ゆっくりしていくのじぇ
まだ描きかけの記事なので後からしゅうせいさんをくわえていくのじぇ」
まりちゃ「今日の半導体工学のふくしゅうなのじぇ
状態密度とキャリア濃度ってテーマだったのじぇ」
ありす「初めて書く記事なのに第6回目の授業内容なのね...」
まいちゃ「忘れないうちにやっておくのじぇ」
まいちゃ「閃亜鉛構造のΓ点付近のばんどこうぞうはこうなってるのじぇ
Γ点とは逆格子空間における原点のことなのじぇ」
まいちゃ「今回は問題を単純化するために2バンドモデルを考えるのじぇ
これは価電子帯はP型波動関数だから自由度が3あり、重い正孔バンド軽い正孔バンド、スプリットオフバンドの3っつのバンドがあるのを一つにして簡略化しているのじぇ
伝導体はs型波動関数で自由度が1なのでそのままなのじぇ
ちなみにここで出てきたs、pっていうのはs、p軌道のそれと同じ意味なのじぇ」
れいみゅ「ゆゆっ!?どうして価電子帯はp型で、伝導体はsなの??」
まいちゃ「まいちゃにもよくわからないのじぇ
ちなみに真空中の電子の静止質量よりも閃亜鉛構造内の電子の有効質量の方が小さくなるのも謎なのじぇ
まあここではその話題はおいておくのじぇ」
まいちゃ「価電子帯のエネルギー関数と伝導体のエネルギー関数はこうなるのじぇ」
伝導帯
\begin{align}
\Ec(k)=Ec+ h2 k2/2m_{e}
\tag{1}
\label{eq:}
\end{align}
\[
Ec(k)=Ec+ h2 k2 /2 me
\]
価電子帯
\[
Ev(k)=Ev+ h2 k2 /2 mh
\]
ありす「バンドギャップエネルギーは\[Eg=Ev-Ec\]ね!」
まいちゃ「グラフにするとこんな感じなのぜ」
まいちゃ「まずは状態数についてしらべるのじぇ
状態数Nはkについての関数で3次元波数空間の(kx,ky,kz)の組の数なのじぇ
ここでまずは最小波数空間体積について考えるのじぇ
一辺がLの立方体のとある軸に進む波の波長の最大値はLになることは理解できると思うのじぇ
波数kは2π/λであらわされるので波長が大きいほど波数は小さくなるのじぇ
ここでは最大の波長はLであるとしているので波長がLの時波数は最小の値k=2π/Lをとるのじぇ
ここでさっき言った最小波数空間体積は一辺がk=2π/Lであるk空間内の立方体の体積なのじぇ
これは分かりやすくいうなれば、一つの状態が座れるサイズの映画館のシートなのじぇ
最終的に
状態数N(k)は(波数空間内における半径kの球の体積)÷(最小波数空間体積)*2になるのじぇ
最後の2は電子がスピン縮退を持つことからくるのじぇ
体積を最小の体積で割るとその(kx,ky,kz)の組の数が出てくるというのは納得できると思うんだじぇ
映画館の床の広さをを映画を見るときに座る座席の大きさで割ると座席を何席おけるかわかるという意味なのじぇ
」
ありす「これを計算すれば状態数N(k)はでるわね!」
まりちゃ「ここでまいちゃが求めておきたいのは状態密度D(E)なのじぇ
状態密度D(E)は”単位体積当たりのあるエネルギーEにおいて存在することが可能な正孔、電子の個数の密度”のことなのじぇ
これは状態数をEで微分すればいいのじぇ
ちょっと疑問に思うかもしれないけど
\begin{align} \int D(E)dE=Nv \tag{1} \label{eq:} \end{align}
であるからD(E)が”あるエネルギーEにおいて存在することが可能な正孔、電子の個数の密度”ということは納得してもらえると思うんだじぇ 」
れいみゅ「D(E)のグラフはこんな感じだよ!」
まりちゃ「
ここでようやく電子と正孔の濃度について議論できるのじぇ
電子正孔濃度n(E),P(E)は状態密度D(E)とフェルミ分布関数の積であらわされるのじぇ。
分かりにくいけどまあ状態密度が映画館の全座席で
フェルミ分布関数が映画を見に来た客だと思ってくれればいいんじゃないかだじぇ?
電子の濃度は映画館の全座席の関数とお客の数の関数であらわされ、
全座席が0ならばいくら客が映画を見ようとしても座れないので見れないつまり濃度はゼロで
逆に座席がいっぱいあってもみようとする人がいないつまらん映画なら濃度はゼロだじぇ
ちなみにフェルミ分布関数はシグモイド関数を逆にしたような形をしているのじぇ
これで電子と正孔の濃度についてのグラフがもとまるのじぇ
」
はてなブログ使い方テスト
#include <iostream> std::cout<<"Hello world"<<std::endl;
まいちゃ「ゆっくりするのじぇ」
れいみゅ「ここでは昔授業で習ったような数学物理を復習していくつもりだよ!」
\[ {e}^{i\pi} + 1 = 0 \]
\[y={x}^{2}+{b}{x}+{c}\]
\begin{align} \int_V \nabla\cdot AdV=\int_S A\cdot n dS \tag{1} \label{eq:gauss} \end{align}
ありす「markdown記法と数式用のMathJaxをつかっていくつもりよ!」