ソフトウェアの品質を学びまくる

ソフトウェアの品質、ソフトウェアテストなどについて学んだことを記録するブログです。

ソフトウェアそのものじゃないけど面白いアルゴリズムだなと思ったお話

この記事では、「プログラミングじゃないんだけど、すごくアルゴリズムっぽいな!」と思った話を2つ紹介します。タイトルそのままですね。

流量制御っぽい話

一つ目は、『ホルムヘッドの謎』という本からの紹介です。
本書は、国文学者・林望氏によるエッセイ集。英国を舞台の中心とした一つ一つのエッセイが含蓄と味わい、知識と考察に満ちていて、あっ「エッセイ」って本来こういうものなんだよな、単にその日あったことを書くのは「日記」なんだよ・・・と思い知らせてくれます。

エッセイの一つに、著者が絶賛してはばからない交通システム・「ラウンドアバウト」があります。
こんな構造の道路構造です。

The Cars At The Roundabout Go Round and Round..."The Cars At The Roundabout Go Round and Round..." by thienzieyung is licensed under CC BY 2.0

この写真だと四叉路くらいに見えますが信号はなく、入ってきた車が島の周りを回って、望む方向に出ていく、という形になっています。
本書によると、交通ルールは以下の通りです。

  1. なにはともあれ、ラウンドアバウトは一切の例外無く時計回りの一方通行である。
  2. そして、ともかくラウンドアバウトの内部に既に進入している車が全ての周辺流入路に対して絶対的優先通行権を有する
  3. 右側から来る車が優先権を持つので、ラウンドアバウトに入ろうと思うときはまず右から車が来ないかどうか確かめて、たといそれが自転車であろうと十トントラックであろうと、何らかの車が右からこのラウンドアバウトを周回してくるのを認めたら、その車が自分の前を通過してしまうまで周回路内に入ってはいけない
  4. もし、右から車が来ないことが容易に確認できる場合には、ラウンドアバウトに入るに際して一時停止するには及ばないので、安全を確認しつつそのまま進入してよい。
  5. 進入する道路から見てすぐ左隣の道に進みたいときは、左折信号を出しながら一番左の車線を進み、すぐに左折してラウンドアバウトを離脱する。
  6. それ以外の道に進みたいときは、右折信号を出しつつ進入してラウンドアバウトを周回し、目的の道の一つ前の道を過ぎたときに左折信号に切り換えて、目的の道に左折で入り、ラウンドアバウトを離脱する。

これはもう絵がないことには説明のしようもないので、東京海上日動さんのサイトから引用させていただきます。

f:id:kz_suzuki:20210815073136p:plain
ラウンドアバウトを通過するときのルールと注意点 (東京海上日動のサイトより)

上の絵で、たとえば赤の車が右折したければ、ラウンドアバウトに進入して270度ぐるっと回って抜けていくことで、論理的な右折をすることができます。
遠回りに見えますが、日本の普通の信号付き道路のように、対向車を伺いながら交差点の真ん中まで行き・・・とやるよりずっと安全に感じないでしょうか? また、クルマは常に時計回りなので、万一接触した際にも2台の車の相対速度が小さいという特性もあります。

右の道からの進入が続いたりすると、赤の車はいつまで経ってもラウンドアバウトに入れなくなるのではないか、と思えます。
しかし、車は右からだけでなく、左の道からも上の道からも入ってくるわけです。たとえば上から入ってくると、内部を進行を優先する原則から、右からの進入は保留せざるを得ません。すると下の車に進入のチャンスが生まれるというわけです。

面白いのは、「交通量の自然調節が行われる」(本書より)点。
どういうことか。

ラウンドアバウトでどれだけ車が通過するかは、経路によって異なります。
たとえば上の図で、左右方向の交通量が多く、上下方向は少ないとしましょう。左右方向にひっきりなしに車が流れていくと、上下方向からの車がラウンドアバウトに進入するタイミングがなくなるではないかと。
しかしそれでも、左右方向から来て上下方向に抜ける車がたまに現れるわけです。たとえば左からの緑の車が下に抜ける(論理的な右折をする)場合、その車が270度回る間に右からの流入をいったんせき止めることになります。その車が下に抜けることは左折信号から判断できるので、下からの赤の車は安心して進入できることになります。その赤の車がさらに左からの車の進入をせき止めて上の道に抜けるため、今度は上の道からの進入も可能になる、とこういうわけです。

しかしながら、B→D街道を直進する車の量は右折車両やA→C道の車の数に比しては圧倒的に多いだろうから、それだけ優先的にどんどん進むことができるというあんばいになる。つまりは、信号の時間をコンピュータで制御したりしなくとも、交通量の多寡によって、自然に自動的にラウンドアバウト内への流入量が制御される仕組みになっている*1

この見事な仕組み*2、流量制御のアルゴリズムっぽくないですかね?

強化学習っぽい話

こちらは『STATISTICS HACKS』からの紹介。
統計の本というと、抽象的な概念と数式が淡々と書かれていてだんだんつらくなっていくものなのですが、本書はその理論的な部分を、具体例や興味深い応用例で味付けしてくれており、最後まで読む気にさせてくれます。やたらとくだけた語り口に、訳者の方の苦労が偲ばれます。

本書で紹介しているのが、「どんどん強くなる三目並べ」の仕組みです。
用意するのは、以下だけ。

  • マッチ箱287個
    • 各マッチ箱は、三目並べでありうる盤面287パターンに対応している*3
      • たとえば、「真ん中にOが置かれて、あとはまだ空白」とか。これがマッチ箱の中に書かれている。
  • 9色の大量のビーズ
    • ビーズの色は、三目並べの9つのマスに対応している。
      • たとえば「真ん中のマスは赤」とか。
    • 各マッチ箱に、盤面に応じて選べるマスに対応するビーズだけを入れておく。
      • たとえば初期状態はすべてのマスが空なので、9色すべてのビーズを入れておく。一方「最後の一手」に対応する盤面では選べるマスが1つしかないので、そのマスに対応する1色のビーズだけを入れておくことになる。

これで準備完了。ゲームの進め方を引用します*4
なおゲーム自体は、地面の上にでも線を引いて行います。

  1. まずコンピュータの番だ。現在の盤面のマッチ箱を探す(第一手のときは、空白のもの)。目を閉じて適当にビーズを取り出す。
  2. ボード内の小石の色が示すマスにXを入れる。そのビーズを邪魔にならない場所に退ける。
  3. 自分が選んだ場所にOと記し、自分の番をこなす。
  4. 盤面は新しい配置になった。対応するマッチ箱の所に行って、ビーズを無作為に取り出す。ステップ2に戻る。
  5. 勝負がつくまでステップ2からステップ4までを繰り返す。
  6. コンピュータが負けた場合、マッチ箱から無作為に取り出したビーズを手にして、海に投げ込むことで罰する
  7. コンピュータが勝った場合、または引き分けた場合、ビーズを元のマッチ箱に戻し、同じ色のビーズを追加することで報酬を与える

一番最初のゲームでは、「コンピュータ」は可能な手すべてから、勝負の有利不利は関係なく、ランダムに(「目を閉じて」)手を選ぶことになります。
ですがゲームのたびに、負けにつながった手に対応するビーズが破棄され、勝ちにつながった手に対応するビーズが追加されるので、2ゲーム目以降、勝ちにつながる手を選ぶ確率がどんどん高くなっていくという仕組みです。

この章には明確に「強化」「学習」「罰する」「報酬を与える」という言葉が出てくるので、強化学習そのものにも見えるのですが、本書の原著が2006年でああり、そもそもこの話が雑誌に載ったのは1963年とのことで・・・先進が過ぎる。

まとめ

いかがでしたか?*5

「コンピュータっぽいことを人力でやる」話は、SFアンソロジー『折りたたみ北京』の中の一作、劉慈欣氏の『円』にも出てきます。周率を文字通り「人海戦術で」求める壮大なお話。

この『円』は、今話題の中国SF『三体』のエピソードを切り出したものとのこと。
『三体』自体も奇想天外なアイデアに満ちたスケールの大きいストーリーで、とてもお勧めです! わたしの好きなSFの条件って、「予想の上を行くファーストコンタクト」と「想像もつかないガジェット」なのですが、『三体』は特に後者、「智子(ソフォン)」と「宇宙社会学」がめちゃくちゃ効いていて、物語にガッシリとした芯を通しています。

興味のある方は、ぜひ!

三体

三体

Amazon

*1:ここでAが下、Bが左、Cが上、Dが右 に対応。

*2:こういった特性をもつラウンドアバウトですが、たとえば「全ての人が完全にルールを遵守する」ことを前提にしているといった欠点も紹介されています。

*3:ありうる盤面パターンのうち、回転・反転で同一になるものはを集約している。

*4:本文の「ココナッツ」を「マッチ箱」に、「小石」を「ビーズ」に読み替えている。他、一部修正

*5:未だにこの「いかがでしたか」ネタを愛している。