開発日誌/2007-07-26より転載,加筆・修正.

プレイヤが喋れる情報量

  • プレイヤが喋れる文字は全部で74種類.
  • プレイヤが一度に喋れる文字数は10.
  • よって,一度に喋れる最大の情報量は74進数で10桁分,すなわち74の10乗.
文字数(74^n)最大情報量
74^174
74^25476
74^3405224
74^429986576
74^52219006624
74^6164206490176
74^712151280273024
74^8899194740203776
74^966540410775079424
74^104923990397355877376

10文字をフルに使うと,4,923,990,397,355,877,376. 四百九十二京 三千九百九十兆 三千九百七十三億 五千五百八十七万 七千三百七十六. この数値は,63ビットで表現可能(次節参照).

2^n - 1

2^n - 1 で74進数を追いかけたテーブル.

n2^n - 174進数文字列との対応
11
23
37
415
531
663< 74^1
7127> 74^1
8255
9511
101023
112047
124095< 74^2
138191> 74^2
1416383
1532767
1665535
17131071
18262143< 74^3
19524287> 74^3
201048575
212097151
224194303
238388607
2416777215< 74^4
2533554431> 74^4
2667108863
27134217727
28268435455
29536870911
301073741823
312147483647< 74^5
324294967295> 74^5
338589934591
3417179869183
3534359738367
3668719476735
37137438953471< 74^6
38274877906943> 74^6
39549755813887
401099511627775
412199023255551
424398046511103
438796093022207< 74^7
4417592186044415> 74^7
4535184372088831
4670368744177663
47140737488355327
48281474976710655
49562949953421311< 74^8
501125899906842623> 74^8
512251799813685247
524503599627370495
539007199254740991
5418014398509481983
5536028797018963967< 74^9
5672057594037927935> 74^9
57144115188075855871
58288230376151711743
59576460752303423487
601152921504606846975
612305843009213693951
624611686018427387903< 74^10
*63*9223372036854775807> 74^10 -- ここで10文字をオーバー
6418446744073709551615

よって,63bitあれば 73^10の値を表現可能.逆に言うと,62bit分までの情報量であれば,何も小細工すること無く10文字以内で表現可能である.

74進数と2進数の対応表

文字数最大情報量許容bit数(情報量)
1746 (63)
2547612 (4095)
340522418 (262143)
42998657624 (16777215)
5221900662431 (2147483647)
616420649017637 (137438953471)
71215128027302443 (8796093022207)
889919474020377649 (562949953421311)
96654041077507942455 (36028797018963967)
10492399039735587737662 (4611686018427387903)

もう一つの方法

2進数のビット単位で区切るのではなく,単純に値の範囲の最大値をかけていく方法を使うと,より高い圧縮率を実現できる場合がある. 例えば,4文字に圧縮する場合,74進数では最大 29986576 の情報量を含めることができるが,2真数に置き換えると 24ビット =16777216 となってしまい, (29986576 - 16777216)分の情報を損している.

また,例えば,背番号の情報として1から11の整数を含める場合,2進数では4ビット消費する. ここで行われる操作は val <<= 4 というビットシフトで,16の情報量を消費してしまい,無駄が生じる. しかし,ここで val *= 11 としてしまえば,消費する情報量はあくまで11となる. 復号するには,11で割って更に11の剰余を求めるだけである.

以上より,桁を事前にきっちり見積もっておけば74進数の数値の範囲分を最大限に利用できるため,2進数のビットで区切るよりも効率良く情報を圧縮できる.

圧縮方法

ボールの位置+速度

ある程度の精度を残しつつ,位置と速度を圧縮することを考える. フィールドのサイズが105m x 68m,物体の最大スピードが2.7m であることを前提とする.

  • 位置,速度ともに精度を0.1mとすると,
    X座標の値域は[0,1050]で11 bit必要,
    Y座標の値域は[0,680]で10 bit必要,
    速度X,Yの値域は[0,54]でそれぞれ6 bit必要.
    よって,合計で33 bit = 6文字.
  • 位置の精度を0.2m,速度の精度を0.1mとすると,
    X座標の値域は[0,525]で10 bit必要,
    Y座標の値域は[0,340]で9 bit必要,
    速度X,Yの値域は[0,54]でそれぞれ6 bit必要.
    よって,合計で31 bit = 5文字.
  • 位置の精度を0.5m,速度の精度を0.1mとすると,
    X座標の値域は[0,210]で8 bit必要,
    Y座標の値域は[0,136]で8 bit必要,
    速度X,Yの値域は[0,54]でそれぞれ6 bit必要.
    よって,合計で28 bit = 5文字.
  • 位置の精度を0.5m,速度の精度を0.2mとすると,
    X座標の値域は[0,210]で8 bit必要,
    Y座標の値域は[0,136]で8 bit必要,
    速度X,Yの値域は[0,27]でそれぞれ5 bit必要.
    よって,合計で26 bit = 5文字.

以上より,位置+速度を5文字に圧縮するのがもっとも効率が良いだろう. 最終的に,各情報の割り当てbit数と精度は以下のようになる.

情報値域bit数 (10進数での範囲)精度
位置座標X成分[-52.5,52.5]10bit([0,1023])105.0/1023.0 (≒0.102639296)
位置座標Y成分[-34.0,34.0]9bit ([0,511])68.0/511.0 (≒0.133072407)
速度成分XY[-2.7,2.7]6bit ([0,63])5.4/63.0 (≒0.085714286)

合計31bitで5文字.

速度を極座標で表現する場合については未検討.直感的には,直交座標で表現しておいた方が無難な気がする.

背番号+位置座標

4文字で表現する.

背番号 4ビット, 位置情報 19ビット = 合計23ビット

位置の精度はボールの場合と同一. しかし,本来,4文字あれば24ビット分の情報を詰め込めるので,1ビット分の無駄が生じている. 検討の余地あり.

位置座標

3文字で表現する.

X座標 9ビット, Y座標9ビット = 合計18ビット

X座標の精度 104.0/511.0 ≒ 0.203522505, Y座標の精度 68.0/511.0 ≒ 0.133072407

3文字分の情報量を最大限に利用.X座標の範囲を[-52.0,52.0]とする.

敵キーパの位置+体の向き

4文字で表現する.

敵キーパは敵陣ペナルティエリア内部(x:[36.5,52.5],y:[-20,20])に存在していると想定. よって,Xは[0,16],Yは[0,40]の範囲. 体の向きの精度を1度に固定する. 位置座標の精度をprecisionとすると,

16/precision * 40/precision * 360 < 74^4
16 * 40 * 360 / 74^4  < precision^2
precision > 0.087655223

よって,位置座標の精度を0.1とできる.


トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2016-03-14 (月) 14:51:37 (1890d)
SourceForge.JP
Creative Commons License
RoboCup tools by Hidehisa Akiyama is licensed under a Creative Commons 表示-非営利 2.1 日本 License.