スイス式トーナメントって何だぜ(^~^)?

前の関連記事

📖 イロ・レーティングって何だぜ(^~^)?<その2>

情報

📖 Git Hub

はじめに

ramen-tabero-futsu2.png
「 スイス式トーナメントのマッチングを実装しようぜ?」

kifuwarabe-futsu.png
「 柿木さんか 瀧澤さんか 山田さんか カツ丼が ソースコードを持っているのでは?」

ohkina-hiyoko-futsu2.png
「 ソースコード読んでも あんたら 分かんないでしょ」

リーグ(League;総当たり)

ramen-tabero-futsu2.png
「 スイス・システム・トーナメント(Swiss-system-tournament;スイス式トーナメント)は、
リーグ(League;総当たり)できないときに 使われる。
リーグできない理由は、人数多いとか、時間無いとか、様々だぜ」

kifuwarabe-futsu.png
「 じゃあ まず リーグのマッチングのアルゴリズムを実装してくれだぜ」

202312__shogi__17-1301--League-o2o0.png

ramen-tabero-futsu2.png
「 👆 y が 1 ~4 の人たち、ここでは偶数の人数としよう、
全員が 次の人を選んだら……」

202312__shogi__17-1301--League-o2o1o0.png

ramen-tabero-futsu2.png
「 👆 ペアリングは成立しないので、
偶数番の人には 正負の符号を反転してもらう必要があるな」

202312__shogi__17-1301--League-o2o2o0.png

ohkina-hiyoko-futsu2.png
「 奇数と偶数で 挙動が変わるアルゴリズムなのかしらねえ?」

リーグ 2ラウンド目

202312__shogi__17-1301--League-o2o3o0.png

ramen-tabero-futsu2.png
「 👆 1 の代わりに 2 にしても うまく働いたな」

ohkina-hiyoko-futsu2.png
「 序数 めんどくさいので 基数 にしたらどう?」

202312__shogi__17-1301--League-o2o4o0.png

ramen-tabero-futsu2.png
「 👆 モジュロ(modulo;法)を使う時は 序数を使った方がいいかだぜ」

kifuwarabe-futsu.png
「 3ラウンド目も うまくいくのかだぜ?」

202312__shogi__17-1301--League-o2o5o0.png

ramen-tabero-futsu2.png
「 👆 うまく行ったが?」

ohkina-hiyoko-futsu2.png
「 永遠に上手くいく証明はできるの?」

ラウンド番号を序数 r とする
参加人数を yy とする。yy は偶数とする
参加者番号は基数 y とする

リーグでの対戦相手番号は

(y+yy+r)%yy    if 自分の参加者番号が偶数
(y+yy-r)%yy    if 自分の参加者番号が奇数

ramen-tabero-futsu2.png
「 👆 この定義の証明か。何も思い浮かばんな」

202312__shogi__17-1404--League.png

kifuwarabe-futsu.png
「 👆 yy が 8 のとき、 r=2 で ぐちゃぐちゃだぜ」

ohkina-hiyoko-futsu2.png
「 画面端でループしてるけど、
蛇の頭が ただ伸びてるだけですもんね」

ふつうに考えて 線対称なのでは?

kifuwarabe-futsu.png
「 対角線を軸とした、線対称になる式にしないといけないのでは?」

ramen-tabero-futsu2.png
「 まったくだぜ」

202312__shogi__17-1449--PositiveNegative.png

ramen-tabero-futsu2.png
「 0番目の+6と、 6番目の-6 は線対称になるのは 分かるし、
プラス方向に進むか、マイナス方向に進むかは 対角線の位置で分かる」

ohkina-hiyoko-futsu2.png
「 じゃあ 奇数、偶数じゃなくて 対角線を使って 分けりゃいいんじゃないの?」

202312__shogi__17-1509--League.png

ramen-tabero-futsu2.png
「 👆 対角線で分かれているのは確かだが、
xについても、yについても、排他的でないといけないぜ」

kifuwarabe-futsu.png
「 色分けしてくれだぜ」

202312__shogi__17-1517--Coloring.png

ramen-tabero-futsu2.png
「 👆 こうだぜ」

kifuwarabe-futsu.png
「 これだけ 分かってって あと何が分からないんだぜ?」

2つのグループに分けることができる

202312__shogi__17-1525--ColoringGroup.png

ramen-tabero-futsu2.png
「 👆 上のグループと、下のグループは 法則が別かな? 左右反転」

202312__shogi__17-1533--Window.png

ohkina-hiyoko-futsu2.png
「 👆 ウィンドウのようなものも あるんじゃないの?」

kifuwarabe-futsu.png
「 認識しづらいな…… もっと良い補助線があるんじゃないか?」

202312__shogi__17-1559--Rotate.png

ramen-tabero-futsu2.png
「 👆 複利計算みたいだな……」

セル・オートマトンで何とかならないか?

ramen-tabero-futsu2.png
「 分岐があるような計算 困難なんで
分岐が無くせないか まず考えてみよう」

202312__shogi__17-1604--CellAutomaton.png

ramen-tabero-futsu2.png
「 👆 対角線のセルに 1 が入っているとしよう」

202312__shogi__17-1604--CellAutomaton-o2o0.png

ramen-tabero-futsu2.png
「 👆 1 + 1 = 2 までは すぐ行けるが……」

202312__shogi__17-1604--CellAutomaton-o3o0.png

ramen-tabero-futsu2.png
「 👆 足すというより、自然数の蛇が伸びているとしよう」

202312__shogi__17-1604--CellAutomaton-o4o0.png

ramen-tabero-futsu2.png
「 👆 行き止まりに入った 4 が居るな」

202312__shogi__17-1604--CellAutomaton-o5o0.png

ramen-tabero-futsu2.png
「 👆 対角線に +4 した 5 を使って リスタートしたらどうだぜ?」

202312__shogi__17-1604--CellAutomaton-o6o0.png

ramen-tabero-futsu2.png
「 👆 なんか 数列ができてきたな」

202312__shogi__17-1604--CellAutomaton-o7o0.png

ramen-tabero-futsu2.png
「 👆 もう少し」

202312__shogi__17-1604--CellAutomaton-o8o0.png

ramen-tabero-futsu2.png
「 👆 乱数生成器みたいだ」

ohkina-hiyoko-futsu2.png
「 この数を 簡単に生成できないの?」

ramen-tabero-futsu2.png
「 今やった やり方を 短くできそうだな」

202312__shogi__17-1631--Copy.png

ramen-tabero-futsu2.png
「 👆 最大数を足して複写だぜ」

kifuwarabe-futsu.png
「 その手順のステップ数を セルに振ってくれだぜ」

202312__shogi__17-1637--Stepping.png

ramen-tabero-futsu2.png
「 👆 これで分かるだろ」

ohkina-hiyoko-futsu2.png
「 関数作れないの? 行番号と 列番号で ステップ数が出てくる Excel の関数みたいなやつ」

ramen-tabero-futsu2.png
「 思い浮かばなかったので、アルゴリズムでやりたい」

アルゴリズムを考える

202312__shogi__17-2019--Algorithm-o1o0.png

ramen-tabero-futsu2.png
「 👆 0ラウンド目」

202312__shogi__17-2019--Algorithm-1round-o2o0.png

ramen-tabero-futsu2.png
「 👆 1ラウンド目」

202312__shogi__17-2019--Algorithm-2round-o2o0.png

ramen-tabero-futsu2.png
「 👆 2ラウンド目」

ramen-tabero-futsu2.png
「 あとは 繰り返しだぜ」

kifuwarabe-futsu.png
「 16元数みたいだ」

ohkina-hiyoko-futsu2.png
「 実装してみましょう」

テーブル・サイズの変更

202312__shogi__17-2118--SizeUp.png

Source   Target
------   -----------
0, 1,    0, 1, 0, 1, 
1, 0,    0, 0, 0, 0,
         0, 0, 0, 0,
         0, 0, 0, 0,

ramen-tabero-futsu2.png
「 👆 テーブルサイズを大きくすると レイアウトが崩れるから、
4倍のテーブルは 新しく作るようにしないといけないな。
コピー中に 元の表の5倍 メモリサイズ食う」

kifuwarabe-futsu.png
「 ずれずに コピーするには どうやるんだぜ?」

Source   Target
------   ------------
0, 1,     0, 1, 2, 3, 
2, 3,     4, 5, 6, 7,
          8, 9,10,11,
         12,13,14,15,

ramen-tabero-futsu2.png
「 👆 現状、配列のインデックスなわけだが……」

Source          Target
-------------   -----------------------------------
(0,0), (0,1),   ( 0, 0), ( 0, 1), ( 0, 2), ( 0, 3),
(1,0), (1,1),   ( 1, 0), ( 1, 1), ( 1, 2), ( 1, 3),
                ( 2, 0), ( 2, 1), ( 2, 2), ( 2, 3),
                ( 3, 0), ( 3, 1), ( 3, 2), ( 3, 3),

ramen-tabero-futsu2.png
「 👆 (x, y) の座標形式に変換してから、同じとこへコピーする感じだな」

x = index % edge_size
y = math.floor(index / edge_size)

index = y * edge_size + x

ramen-tabero-futsu2.png
「 👆 x, y, index の変換は上記の通りだぜ」

.

ツイッターでシェア
みんなに共有、忘れないようにメモ

むずでょ@きふわらべ第29回世界コンピューター将棋選手権一次予選36位

光速のアカウント凍結されちゃったんで……。ゲームプログラムを独習中なんだぜ☆電王戦IIに出た棋士もコンピューターもみんな好きだぜ☆▲(パソコン将棋)WCSC29一次予選36位、SDT5予選42位▲(パソコン囲碁)AI竜星戦予選16位

Crieitは誰でも投稿できるサービスです。 是非記事の投稿をお願いします。どんな軽い内容でも投稿できます。

また、「こんな記事が読みたいけど見つからない!」という方は是非記事投稿リクエストボードへ!

有料記事を販売できるようになりました!

こじんまりと作業ログやメモ、進捗を書き残しておきたい方はボード機能をご利用ください。
ボードとは?

コメント