カテゴリー別アーカイブ: プログラミング

【自分用メモ】とうぶつしょうぎ > KKM テーブル

次にKKM(※ M は持ち駒を表す)
KKP 同様に、KK 分の場合の数は 6*7 = 42。

持ち駒は6種類で、値は 0~2 なので、short KKM[6][7][6*3]; で充分。
が、よく考えると、持ち駒の歩が無いのと持ち駒の角が無いのを重複して評価する必要は無いので、
持ち駒数が 1, 2 の場合のみテーブル化し、持ち駒数0 は KK だけで共通化するとよい。

short KK[6][7];
short KKM[6][7][6*2];

要素数は 42*(12+1) = 546 となる。

【自分用メモ】とうぶつしょうぎ > KKP テーブル

先手玉位置を k1, 後手玉位置を k2, 玉以外の盤上の駒タイプ・位置の識別番号を p とするとき、
short KKP[12][12][12*8]; を作っておけば、KKP[k1][k2][p] で評価値を計算できる。
要素数は 12*12*12*8 = 13,824 だ。
先手玉位置が盤面の右側にある場合は左右反転すれば、先手玉位置の場合の数は 8 に減る。
さらに、評価関数は先手番で呼ばれるため、先手玉が相手陣地に入っている場合は既に終局となっていて、
評価関数が呼ばれることは無い。したがって、先手玉位置の場合の数は 6 にな。
同様に、後手玉位置も9に減る。
先手・後手玉が隣接している場合、相手玉を取って終局となるので、これも評価関数で評価する必要は無い。
ただし、テーブルとしては最大数を用意しておく必要があるので、後手玉位置の場合の数は7になる。
玉以外の盤上の駒については、双方の玉位置には配置できないので、その分場合の数が減り、10*8 = 80 となる。

よって、KKP 配列は short KKP[6][7][80]; と宣言でき、要素数は 3,360 となる。
最初の要素数の約3分の1だ。

コマンドラインでアンドロイド開発>android コマンド

Eclipse は重くて使いたくないので、cocos2d-x のアンドロイド版をビルドするときは、
cocos compile -p android -m release
って、何も理解せずやってるおいらだけど、ライブラリを追加しようとかすると、仕組みを理解していないが故に、どうしていいのかさっぱりわからず、いつも困惑しています。

で、人に聞いたり、調べてみるとどうやら アンドロイドSDK に android コマンドってのが含まれていて、それを使うとプロジェクトを作ったり、プロジェクトを修正してり出来そうなことがわかりました。

android コマンドは SDK位置/tools に含まれているので、そこにパスを通せば使えるようになります。
パスを通したら、コンソールで android -h と入力し、以下のようにヘルプが出たら、利用可能です。

C:\Users\ntsuda>android -h

       Usage:
       android [global options] action [action options]
       Global options:
  -h --help       : Help on a specific command.
  -v --verbose    : Verbose mode, shows errors, warnings and all messages.
     --clear-cache: Clear the SDK Manager repository manifest cache.
  -s --silent     : Silent mode, shows errors only.
  (以下略)

【自分用メモ】どうぶつしょうぎ KKP KPP 評価関数

盤面が12箇所しかないので、本将棋に比べるとテーブルはかなり小さくなる

KKP

対称形を排除するため先手玉位置を左または中央列のみとする。右列にあった場合は左右反転を行なう。
これで、場合の数が8に減少する。
後手玉位置は先手局位置以外の11箇所なので、場合の数は 8*11 = 88 となる。
盤上の玉以外の駒をPとすると、位置は10箇所、駒の種類はと金を含めて8なので、
KKPの場合の数はトータルで 88 * 10*8 = 7,040 となる。
KK が両方共中央にある場合は、P を左に寄せることが出来る。もう少し場合の数が減る。

KKM

持ち駒はMで表すことにする。
持ち駒の種類は6。それぞれ [0, 2] の3つの状態があるので、場合の数は 6*3 = 18。
よって、KKM の場合の数はトータルで 88 * 18 = 1,584 となる。

これはかなり少ない数なので、KKMM を採用するのもありかもしれない。
場合の数は 88 * 18 * 5*3 = 23,760

KPP

KKP と同じく、玉の位置は左によせる。ただし、先手玉と後手玉があるので、場合の数は 8*2 = 16 だ。
P は8種類で位置は11または10なので、場合の数は 8*11 = 88, 8*10 = 80 で、
トータルの場合の数は 16*88*80 = 112,640 となる。

KPM

持ち駒の場合の数は 6*3 = 18 なので、
KPM の場合の数は 16*88*18 = 25,344 だ。

KMM

KMM の場合の数は 16*18*15 = 4,320 だ。

場合の数をすべて合計すると、

7,040 + 1,584 + 23,760 + 112,640 + 4,320 = 149,344

となる。評価値を2バイトで保持すれば充分なので、約300Kバイトで事足りることになる。

これらの線形和を計算すれば、かなり正確な評価関数になるように思われるのだが、どうだろうか?

んで、問題は約15万個の値を高速かつ正確に計算するにはどうしたらいいのか?ってことである。

自分用メモ:マッチ棒パズル ソルバー

  • 2本移動の場合、必ず2本移動しなくてはいけない
  • ので、反復深化の浅い探索は不要
  • ただし、既に移動済みの場合は、手数リミットを減らして反復深化を行う
  • 余計な移動を行っている場合があるので、手数リミット以上も探索する
  • ただし、処理時間を食うので、3手までを上限とする?

箱入り娘に関するメモ

temp

  • 図1 は標準的な「箱入り娘」の初期状態だ。
  • マス目の数は 4×5 = 20
  • 各ピースの種別を8ビットで表せば、合計20byteとなる
  • 各ピースを32bit ビットボードで表せば、4*10 = 40 byte となる
  • 状態をハッシュ化するには、左上から順にピース番号を並べるとよい
    • (空欄を含めた)11桁のタイプ列で充分
    • 3bit * 11 = 33bit , または 5^11 = 4.88 * 10^7

 

QScrollArea 派生クラスを直接描画する方法

スクロール可能なウィジェットを実装するには QScrollArea を使用するとよい。
通常は、中身のウィジェットを生成し、setWidget() すれば、自動的にスクロールしてくれるようになる。

ただし、ウィジェットが ScrollArea に比べてかなり大きいと、クリッピングを自前で行わないと描画処理に不必要に時間を食う場合がある。だが、中身のウィジェットが親が持つスクロール情報を参照するのはあまり好ましくない。
で、ひとつの解決方法として、QScrollArea の派生クラスを作り、その中で直接描画する、という方法がある。

実はそのようなコードを以前にも書いたことがあるのだが、いざ書こうとすると、その具体的な方法をすっかり忘れていたし、ぐぐってもなかなか目的とする情報に行き着かなかったので、ここにメモしておく。

描画

描画は void paintEvent(QPaintEvent *); で行う。
ポイントは、自分自身に対して描画するのではなく、viewport() に対して描画するという点だ。

void ScrollWidget::paintEvent(QPaintEvent *)
{
  QPainter painter(viewport());
  painter に対して描画;
}

 スクロールバー情報の設定

setWidget() せず、自前で描画する場合は、スクロール範囲などを自前で設定しなくてはいけない。
そのための関数を用意しておき、resize() イベントが発生した場合は、それをコールする。

void ScrollWidget::resizeEvent(QResizeEvent *event)
{
  QScrollArea::resizeEvent(event);
  updateScrollInfo();
}
void ScrollWidget::updateScrollInfo()
{
  QScrollBar *hScrollBar = horizontalScrollBar();
  hScrollBar->setMinimum(0);
  hScrollBar->setMaximum(qMax(0, WIDTH - vprct.width()));
  hScrollBar->setPageStep(vprct.width());
  hScrollBar->setSingleStep(10);
  .....
}

 スクロール位置を考慮した描画

スクロール位置を考慮した描画を行うには、描画ハンドラ内で、horizontalScrollBar()->value(); にてスクロール位置を取得し、それを考慮した描画を行うとよい。

具体的には座標を上記値でそのつど補正するか、以下のように座標原点を移動するようにする。

void ScrollWidget::paintEvent(QPaintEvent *)
{
  int hpos = horizontalScrollBar()->value();
  QPainter painter(viewport());
  QTransform tf;
  tf.translate(-hpos, 0);		//	原点移動
  painter.setTransform(tf);
  .....
}

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

下図のように、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. 左右ではなく上下反転するコードを書きなさい(解答例は次稿)