月別アーカイブ: 2015年6月

コマンドラインでアンドロイド開発>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万個の値を高速かつ正確に計算するにはどうしたらいいのか?ってことである。

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();

どうぶつしょうぎ>ひよこだけの場合

temp

通常の「どうぶつしょうぎ」では田中らによって後手必勝であることが求められているが、上図のように、ライオンとひよこだけの局面から双方が最善を尽くした場合は、先手必勝 or 後手必勝 or 引き分け のどれなのであろうか?

プログラムのチェックもかねて探索してみたところ、上図は先手必勝だった。

必勝手順の初手はライオンを斜め上に上がる手だった。ひよこをとっても良さそうだが、同ライオンとなった局面は後で出てくるが、先手必敗になる。どうやらライオンは相手陣地に近い方が有利なようだ。

H:0 Z:0 K:0
 . *L  .
 . *H  .
 .  H  L
 .  .  .
H:0 Z:0 K:0

ライオンが斜めにあがると、次はひよこをただで取られてしまうので、後手はひよこを取るよりない。
後手もライオンが斜めに上がると、先手ライオンに進まれてしまい、トライを阻止できなくなる。
なので、後手はひよこをとり、先手はライオンで取り返す。
この状態が最初に言及した局面と同じで、ライオンがひとつ進んだ方が勝ちの局面だ。

H:1 Z:0 K:0
 . *L  .
 .  .  .
 .  L  .
 .  .  .
H:1 Z:0 K:0

ここで先手からライオンの頭にひよこを打たれると、後手ライオンが逃げ、先手ライオンがトライできるので、後手はライオンの頭にひよこを打つ一手。先手は横に逃げる。

H:0 Z:0 K:0
 . *L  .
 . *H  .
 .  .  L
 .  .  .
H:1 Z:0 K:0

後手のひよこが移動すると取られるし、後手ライオンが左に移動すると先手にトライされるので、後手ライオンが右による一手。

H:0 Z:0 K:0
.  . *L
. *H  .
.  .  L
.  .  .
H:1 Z:0 K:0

ここで先手が相手ライオン頭にひよこを打つと、ライオンに逃げられてしまい、あとが続かない。
正解は、下図のようにひよこを垂らす手。

H:0 Z:0 K:0
 .  . *L
 H *H  .
 .  .  L
 .  .  .
H:0 Z:0 K:0

放置しておくとニワトリを作られるので、後手は左に寄る一手。

H:0 Z:0 K:0
 . *L  .
 H *H  .
 .  .  L
 .  .  .
H:0 Z:0 K:0

先手ひよこはただ取られるだけに見えるが、成って相手ライオンを左に寄せるのが好手だ。

H:0 Z:0 K:0
 N *L  .
 . *H  .
 .  .  L
 .  .  .
H:0 Z:0 K:0

後手は取るしかない。

H:1 Z:0 K:0
*L  .  .
 . *H  .
 .  .  L
 .  .  .
H:0 Z:0 K:0

で、先手ライオンがひとつ前に進むと、後手は先手のトライを防ぐ手が無い。

H:1 Z:0 K:0
*L  .  .
 . *H  L
 .  .  .
 .  .  .
H:0 Z:0 K:0

というわけで、ひよこをたらして成り捨てるのが絶妙手で、13手で先手の必勝というわけだ。

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

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

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