読者です 読者をやめる 読者になる 読者になる

Shannon's Switching Game

id:tzik-tackによるシャノンゲームの実装が公開された.
http://www.misojiro.t.u-tokyo.ac.jp/~tzik/shannon/index.xhtml


シャノンゲームとは,無向グラフ上のゲームで,
2人のプレイヤーが交互に短絡除去(SHORT)と開放除去(CUT)を繰り返すことで行われる.
SHORTプレイヤーは特別な2点を1点に縮約できれば勝ちで,できなければCUTプレイヤーの勝ちである.


マトロイド理論を使うとうまくとけることで有名であり,そのため一昨年の5月祭で展示を行った.
今回のものは,それを離散凸の宣伝の一環として使えるように実装し直したもの.



注:まともな国際規格に従っているブラウザでないと動かないみたいです.