• [librcsc] メッセージ圧縮フォーマットのメモ (akiyama) 14:14:00

コミュニケーション関係をちゃんと整理する一環として,メッセージ圧縮フォーマットを整理してみるためのメモ.

プレイヤが喋れる文字は全部で74種類. プレイヤが一度に喋れる文字数は10. よって,一度に喋れる最大の情報量は,74の10乗.

74^1  : 74
74^2  : 5476
74^3  : 405224
74^4  : 29986576
74^5  : 2219006624
74^6  : 164206490176
74^7  : 12151280273024
74^8  : 899194740203776
74^9  : 66540410775079424
74^10 : 4923990397355877376

10文字をフルに使うと,4,923,990,397,355,877,376. 四百九十二京 三千九百九十兆 三千九百七十三億 五千五百八十七万 七千三百七十六. この数値は,符合付き64ビット整数で表現可能.

これを 2^n - 1 で追いかけると以下のようになる.

n
1 : 1
2 : 3
3 : 7
4 : 15
5 : 31
6 : 63
7 : 127
8 : 255
9 : 511
10 : 1023
11 : 2047
12 : 4095
13 : 8191
14 : 16383
15 : 32767
16 : 65535
17 : 131071
18 : 262143
19 : 524287
20 : 1048575
21 : 2097151
22 : 4194303
23 : 8388607
24 : 16777215
25 : 33554431
26 : 67108863
27 : 134217727
28 : 268435455
29 : 536870911
30 : 1073741823
31 : 2147483647
32 : 4294967295
33 : 8589934591
34 : 17179869183
35 : 34359738367
36 : 68719476735
37 : 137438953471
38 : 274877906943
39 : 549755813887
40 : 1099511627775
41 : 2199023255551
42 : 4398046511103
43 : 8796093022207
44 : 17592186044415
45 : 35184372088831
46 : 70368744177663
47 : 140737488355327
48 : 281474976710655
49 : 562949953421311
50 : 1125899906842623
51 : 2251799813685247
52 : 4503599627370495
53 : 9007199254740991
54 : 18014398509481983
55 : 36028797018963967
56 : 72057594037927935
57 : 144115188075855871
58 : 288230376151711743
59 : 576460752303423487
60 : 1152921504606846975
61 : 2305843009213693951
62 : 4611686018427387903
63 : 9223372036854775807  <-- ここで 74^10 をオーバー
64 : 18446744073709551615

続く。。。

  • [librcsc] メッセージ圧縮フォーマットのメモ 続き (akiyama) 16:30:53

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

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

更に続く。。。

  • [librcsc] メッセージ圧縮フォーマットのメモ 続きの続き (akiyama) 17:32:58

ある程度の精度を残しつつ,位置と速度を圧縮することを考える. フィールドのサイズが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文字.

以上より,位置の精度を0.2m,速度の精度を0.1mとして5文字に圧縮するのがもっとも効率が良さそう.同じ文字数でもう少し精度は上げられるけど,これは検討の余地あり.少し実装がややこしくなる上にコードの可読性も落ちてしまうし.

とりあえず,使えるbit数を考慮して,位置速度以外の情報についてももう少し詰めてみよう.

  • [librcsc] 位置+速度の圧縮を再実装. (akiyama) 19:44:38

上記の方針に従って再実装した.ついでに,全く使われていなかった関数を削除した.

X座標の精度は, 105.0/1023.0 , Y座標の精度は 68.0/511.0, 速度成分の精度は 5.4/63.0 で上手くいった. これで,ボール情報が6文字から5文字に減っただけでなく,精度も高まった. 文字数が減っているのに逆に精度が高まっているのは嬉しい.コミュニケーション関係の実装が,今までいかに手抜きだったかということがばれてしまったな.

他のメッセージも順次修正する予定.続きは明日.位置情報だけのメッセージは何文字にしようかな.


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