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

【cocos2d-x v3】 RadioButton の使い方

RadioButton クラスは v3.8 で追加された比較的新しいクラスだ。

  • RadioButtonGroup オブジェクトを生成し、子ノードとしてシーンに追加
  • 選択肢の分だけ、RadioButton を生成し、RadioButtonGroup オブジェクトに 追加し、シーンへも子ノードとして追加する
  • RadioButton オブジェクトにイベントリスナーを指定する
// Create a radio button group
auto radioButtonGroup = RadioButtonGroup::create();
this->addChild(radioButtonGroup);

// Create the radio buttons
for(・・・) {
        RadioButton* radioButton = RadioButton::create("cocosui/radio_button_off.png", "cocosui/radio_button_on.png");
        float posX = startPosX + BUTTON_WIDTH * i;
        radioButton->setPosition(Vec2(posX, winSize.height / 2.0f + 70));
        radioButton->setScale(1.2f);
        radioButton->addEventListener(CC_CALLBACK_2(LabelToggleTypeTest::onChangedRadioButtonSelect, this));
        radioButton->setTag(i);
        radioButtonGroup->addRadioButton(radioButton);
        this->addChild(radioButton);
}

【自分用メモ】とうぶつしょうぎ > 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だ。

【自分用メモ】どうぶつしょうぎ 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万個の値を高速かつ正確に計算するにはどうしたらいいのか?ってことである。

cocos2d-x v3 > httpRequest GET

#include "network/HttpClient.h"
USING_NS_CC;
  cocos2d::network::HttpRequest* request = new cocos2d::network::HttpRequest();
  request->setUrl("http://vivi.dyndns.org/test/index.html?from=cocos2d-x");
  //	GET
  request->setRequestType(cocos2d::network::HttpRequest::Type::GET);
  request->setResponseCallback( [this](network::HttpClient* sender, network::HttpResponse* response) {
  	auto data = response->getResponseData();
  	auto sz = data->size();
  });
  request->setTag("GET test1");
  cocos2d::network::HttpClient::getInstance()->send(request);
  request->release();

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

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

「後退解析」とは、評価が確定した局面から順に順に局面の評価を確定していく処理だ。
評価とは 勝ち・負け・引き分けのいずれかだ。
最初は全ての局面の評価を不明(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百万以上でも解を発見できない