カテゴリー別アーカイブ: C/C++

どうぶつしょうぎ>後退解析

全局面の生成ができたので、次は「後退解析」で、全局面の解析を行なう。

「後退解析」とは、評価が確定した局面から順に順に局面の評価を確定していく処理だ。
評価とは 勝ち・負け・引き分けのいずれかだ。
最初は全ての局面の評価を不明(UNKNOWN)にしておき、ある局面について、その子局面を生成し、
・子局面のどれかひとつが勝ちであれば、勝ち
・子局面の全てが負けであれば、負け
という処理を行い、局面の評価が変化しなくなるまで繰り返せばよい。
このとき、問題になるのはどの局面を調べるか?ということだ。
全局面数がそう多くなければ、全局面について処理を行なっても速度的に問題はないが、局面数が膨大な場合はちょっと遠慮したくなる。
どうぶつしょうぎの場合は末端局面を覗いても約100M局面もあるので、かなり膨大だ。
どうしよう?

どうぶつしょうぎ>全局面生成

「どうぶつしょうぎ」の完全解析 を参考にして、まずは(末端局面を除く)全局面の生成を行ってみた。
アルゴリズムは単純で、以下のようなものだ。

初期局面をハッシュに入れる
初期局面をオープンリストに入れる
while( オープンリストが空でない間 ) {
  オープンリストから局面をひとつ取り出す
  全ての可能着手をリストアップ
  for(全ての着手について) {
    着手を実行
    if( 末端局面でなければ ) {
      初期局面をハッシュに入れる
      初期局面をオープンリストに入れる
    }
  }
}

前掲論文によれば、末端局面を除く全局面数は 99,485,568 で、末端局面を含めると 246,803,167 ということなので、全局面を保持するハッシュテーブルはかなり巨大になってしまう。
最初は std::unordered_map を使用していたのだが、130メガ局面を生成したあたりでおいらのマシンの物理メモリ容量の 12GB を消費してしまい、そのせいか win7 x64 OS がハングアップしてしまった。orz
std::unordered_map はおそらくオープンハッシュでリンクのためにメモリを消費するので、メモリ効率があまりよくない。
1局面は64bit = 8バイトで表現できるので、ハッシュのキー部分だけを考えれば、256M * 8 = 約2GBあれば足りるはずだ。
全局面数があらかじめわかっていれば、クローズドハッシュを自分で作った方がよいので、自作することにした。
衝突確率を下げるために倍の容量を確保したとしても 4GB で事足りる。末端局面を含めないとすれば、その半分の 2GB で充分なはずだ。
のだが、なんと VC++ は x64 モードでも固定配列では 31bit を超えることができない。
なので、new を使ってメモリを動的に確保するようにしたのだが、それも何故かうまくいかず露頭に迷ってしまった。
が、これはおいらの設定ミスで、ソリューションに新しいプロジェクトを追加し、そこでテストプログラムを書いていたのだが、追加したプロジェクトが x64 モードではなく x86 モードでビルドされていたというオチであった。

で、なんとか末端局面を含まない全局面をリストアップできたのだが、局面数が 96,814,709 で、前掲論文の結果とだいたいあっているのだが、ピッタリ一致していない。
まだ、何かバグがあるのかもしれない。

どうぶつしょうぎ>ハフマン的符号化

出現頻度の高い情報を短いビットで表す符号化をハフマン符号化と言う。

どうぶつしょうぎの場合、空欄である確率が高いので、以下のように符号化することが出来る。

0 空欄
100x ゾウ
101x キリン
110x ライオン
1110x ひよこ
1111x にわとり

※ x は先手コマなら0、後手コマなら1

持ち駒も0である確率が高いので、以下のように符号化する。

0 0
10 1
11 2

初期局面は、4*6 + 5*2 + 4 + 6 = 44bit で表現できる。
盤面のコマが持ち駒になると、盤面では 3 または 4bit 減り、持ち駒は 0 または 1 ビット増えるので、
差し引き 3~4bit 減ることになる。
したがって 44bit あれば、持ち駒も合わせた局面の状態を表現できることになる。

どうぶつしょうぎメモ

どうぶつしょうぎの盤面は 3 * 4 = 12 マス。
コマの種類は5種類なので、1マスの状態数は 5 * 2 + 1 = 11種類だ。
(2倍するのは先手・後手があるから。+1 してるのは空欄)
なので、これを符号化するには 4bit あれば足りる。
盤面全体では 4 * 12 = 48bit になる。
持ち駒の種類は3種類で、最高2個なので、3 * 2 * 2 = 12bit
したがって、48 + 12 = 60bit で符号化できることになる。

Quwel メモ

Quwel  プログラムに関するメモ

  • 1マスを char で表し、8×8 配列を用意するとよい
  • 1次元配列にし、周囲に番人を置くとよい。9×10 = 90バイトの1次元配列となる
  • 単純な反復深化でも、ツリーの幅が狭い問題であれば解くことができる。
    • リラックス Level 100 は、幅が狭く、最短手数は10手だが、探索ノード数約6000で解を発見できる
    • リラックス Level 99 は、幅が広く、最短手数は10手だが、7百万以上でも解を発見できない

 

cocos2d-x v3 > シングルタッチイベントリスナー

cocos2d-x v3 のシングルタッチイベントリスナーのテンプレーと

    // タッチイベントリスナー
    auto touchListener = EventListenerTouchOneByOne::create();
    touchListener->onTouchBegan = [this](Touch* touch, Event *){
    	return true;
    };
    touchListener->onTouchMoved = [this](Touch* touch, Event *){
    };
    touchListener->onTouchEnded = [this](Touch* touch, Event *){
    };
    this->getEventDispatcher()->addEventListenerWithSceneGraphPriority(touchListener, this);

数独データ構造

数独用データ構造の自分用メモ

単純には、char cell[81]; とし、各セルの値を 0~9 で保持すればよい。
が、このようなデータ構造では確定しているセルを探す処理が非効率になる。

一案としては、数値を 0b000000001, 0b000000010, … 0b100000000 で 1~9 を表すことにし、
short cell[81]; でセルの数字を、short candidates[81]; で候補数字をビットパターンで表す方法がある。
こうしておけばビット演算で、確定しているセルを探す処理が効率的になる。

もう一つの方法としては、1つの数字が候補として生きているかどうかを1つのビットボードで表す方法がある。
1つのビットボードを ushort * 9 で表すとすれば、全部の候補は ushort * 9 * 9 なので 182バイトとなる。

ビット演算>ビットマップ 転置

下図のように、8×8ビットマップ画像を転置(行・列入れ替え)する関数 uint64 taransose(uint64 bits) はどう書いたらいいだろうか?

........
.*......
.*......
.*......
.*****..
.*....*.
.*....*.
.*****..

↓ 転置

........
.*******
....*..*
....*..*
....*..*
....*..*
.....**.
........

もし、8×8画像をビットマップを使わず bool pixel[8][8]; で表現していた場合、転置処理は以下のように書ける。

void reverseHorizontal(bool pixel[8][8])
{
    for(int y = 0; y < 7; ++y) {
         for(int x = y + 1; x < 8; ++x) {
            std::swap(pixel[y][x], [x][y]);
        }
    }
}

2重ループで、swap演算を28回行う必要がある。

これをビット演算で行うと、以下のように記述できる。

uint64 transpose(uint64 bits)
{
    //  右上4x4と左下4x4を転置
    uint64 t = ((bits >> 28) ^ bits) & 0x00000000f0f0f0f0;
    t |= t << 28;
    bits ^= t;
    //  4x4 の中の、右上2x2と左下2x2を転置
    t = ((bits >> 14) ^ bits) & 0x0000cccc0000cccc;;
    t |= t << 14;
    bits ^= t;
    //  2x2 の中の、右上と左下を転置
    t = ((bits >> 7) ^ bits) & 0x00aa00aa00aa00aa;;
    t |= t << 7;
    bits ^= t;
    return bits;
}

これも、分割統治法を使い、4x4, 2x2, 1x1 サイズの矩形を右上、左下で入れ替えるとOKだ。
ちょっとむずかしいかもしれないが、ご理解いただけたであろうか?

ビット演算>ビットマップ 上下反転

下図のように、8×8ビットマップ画像を上下反転する関数 uint64 reverseVertical(uint64 bits) はどう書いたらいいだろうか?

........
.*......
.*......
.*......
.*****..
.*....*.
.*....*.
.*****..

↓ 上下反転

.*****..
.*....*.
.*....*.
.*****..
.*......
.*......
.*......
........

もし、8×8画像をビットマップを使わず bool pixel[8][8]; で表現していた場合、上下反転処理は以下のように書ける。

void reverseHorizontal(bool pixel[8][8])
{
    for(int y = 0; y < 4; ++y) {
         for(int x = 0; x < 8; ++x) {
            std::swap(pixel[y][x], [7-y][x]);
        }
    }
}

2重ループで、swap演算を32回行う必要がある。

これをビット演算で行うと、以下のように記述できる。

uint64 reverseVertical(uint64 bits)
{
    uint64 t = ((bits >> 32) ^ bits) & 0x00000000ffffffff;;
    t |= t << 32;
    bits ^= t;     // 上4行と下4行を交換
    t = ((bits >> 16) ^ bits) & 0x0000ffff0000ffff;
    t |= t << 16;
    bits ^= t;     // 2行ごとの交換
    t = ((bits >> 8) ^ bits) & 0x00ff00ff00ff00ff;
    t |= t << 8;
    bits ^= t;     // 1行ごとの交換
    return bits;
}

1行内のビット順序は変化しない。
分割統治法により、4,2,1行ごとに反転処理を行っている。
単純にループで処理すると6*4=24回の論理演算処理が必要だが、
分割統治法によりトータルの論理演算回数が6*3 = 18回に減少している。

ご理解いただけるであろうか?

ビット演算>ビットマップ 左右反転

下図のように、8×8ビットマップ画像を反転する関数 uint64 reverseHorizontal(uint64 bits) はどう書いたらいいだろうか?

........
.*......
.*......
.*......
.*****..
.*....*.
.*....*.
.*****..

↓ 左右反転

........
......*.
......*.
......*.
..*****.
.*....*.
.*....*.
..*****.

もし、8×8画像をビットマップを使わず bool pixel[8][8]; で表現していた場合、左右反転処理は以下のように書ける。

void reverseHorizontal(bool pixel[8][8])
{
    for(int y = 0; y < 8; ++y) {
         for(int x = 0; x < 4; ++x) {
            std::swap(pixel[y][x], [y][7-x]);
        }
    }
}

2重ループで、swap演算を32回行う必要がある。

これをビット演算で行うと、以下のように記述できる。

uint64 reverseHorizontal(uint64 bits)
{
    uint64 t = ((bits >> 4) ^ bits) & 0x0f0f0f0f0f0f0f0f;
    t |= t << 4;     bits ^= t;     // 4ビットごとの交換     t = ((bits >> 2) ^ bits) & 0x3333333333333333;
    t |= t << 2;     bits ^= t;     // 2ビットごとの交換     t = ((bits >> 1) ^ bits) & 0x5555555555555555;
    t |= t << 1;
    bits ^= t;     // 1ビットごとの交換
    return bits;
}

8ビットごとにビット順序を逆にしているのだが、8バイトを並行に処理している。
また、分割統治法により、4,2,1ビットごとに反転処理を行っている。
トータルの論理演算回数は6*3 = 18回だ。

ご理解いただけるであろうか?
反転処理は xor(排他的論理和)を用いたビットの交換 で説明したテクニックを使っている。
よくわからなかった人は復習してきて欲しい。

演習問題:

  1. 上記コードをビルド・実行し、正しく反転されていることを確認しなさい
  2. “d” を左右反転し表示するコードを書きなさい
  3. 左右ではなく上下反転するコードを書きなさい(解答例は次稿)