- @ThothChildren
- 2018.10.20
- PV 153
Thue-Morse列
ー 概要 ー
Thue-Morse列は、数を数え上げていくときにその数字を2進数で表記した時の1の偶奇を並べた列.
この章を学ぶ前に必要な知識
効果
- 数え上げている数字の二進数表示で1のbit数の偶奇の列を得る
- 先手が有利になるときに常に先手有利にならないようにする
- チェスで3回繰り返さなくても無限に続く手があることの証明に使用された
ポイント
- T列を作る時に Tn = T(n-1)+ ~T(n-1)のようにも作れる
- L System表記によって文字列の置換でも表記できる
- 3回同じパターンが続くことがない
- 列の中のいかなる長さのパターンも3回以上続くことはない.(0,0,0や0110, 0110, 0110のようにはならない)
解 説
Thue-Morse列は、数を数え上げていくときにその数字を2進数で表記した時の1の偶奇を並べた列.
すなわち、0,1,2,3...の数字を二進数表示にして、0, 1, 10, 11, ...その1の数が偶数個ある場合は0、奇数個ある場合は1とする.
特徴
・列の中に現れるいかなる長さのパターンも3回以上連続しない.
| Thue-Morse列 |
Thue-Morse Sequenceの作り方 | |
Thue-Morse Sequenceの作り方は、先に述べた厳密な定義以外に、他二つの作り方がある.
まず置換ベース.
文字列の置換を繰り返して作成
・0を開始.
・0→01, 1→10に置換する.
上記ルールで行うと
$$0\rightarrow01\rightarrow0110\rightarrow01101001\rightarrow0110100110010110$$ | Thue-Morse Sequenceの作り方詳細① |
次はビット操作ベース
ビット操作によって作成
・\(T(n-1)\)があったら
$$T(n) = T(n-1) NOT(T(n-1))$$
自身をビット反転させたものを自身の後ろに繋げる.
すなわち\(T(n-1) = 0110\)なら
$$T(n) = 0110\ 1001$$
のようになる. | Thue-Morse Sequenceの作り方詳細② |
先手が有利になってしまう操作があり、それを交互に行うと最後まで先手が有利なことが多い.
そこでどちらかが有利にならないようにThue-Morse Sequenceの順番にする方法などがあります(Fair Share Sequence).共有しているリソースなどがあるときなどにも先手必勝にならないようにすることができます. | Thue-Morse Sequenceの使いどき |
他に参考になりそうなリンクを貼っておきます. | 外部リンク 他Thue-Morse列に関してまとめているサイト(英) |
Fair Share Sequenceに関する解説動画 (英語) |
この章を学んで新たに学べる
Comments