ブロックス

ブロックス (wikipedia:ja:ブロックス) - Blokus.

こういう陣取りゲームって大好きですよね。ここで試用できます。音が流れるのでご注意下さい。Mac に対応していない... だと... でも大丈夫。ここのクイックプレーがあります。楽しいですね。CPU相手でもなかなか勝てませんよ。弱す！
このゲーム先手がかなり有利な気がするんですけど、手札ピースにアレンジ加えるとバランスとれそうでしょうか。例えば、アリーナが20x20の場合、２人のプレーヤは200個の箱が渡されて、そこから自由にテトリスピースを用意します。どんなピースを持っているかはオープンします。意味がない。まだ先手が有利な気がする。
後手はピースを見せなくても良いことにする。完全情報はやめる。テトリスピースに限ると意味がないような気がする。
ピースの制限を変えます。例えば、箱8個ぐらいまででピースを構成する。ピースの任意の箱は少なくとも一辺を他の箱と共有する。辺じゃなくて頂点でも良いや。それから、ラウンド数を 200/4 = 50 以下にするとかに制限するとちょっと変わってくるでしょうか。これで先手は後手がどういうピースをどのタイミングで置いてくるか分かりません。あまり小さなピースばかりを用意すると手詰まりの可能性は少なくなりますが得点はのびません。まだ先手が有利な気がする。
Open だった。それもそこそこ有名な... 勘などあてになりません。何も変えなくてもフェアなのかなぁ。困難性と公平性は別ですけど。どうなんですかね。きちんとNash均衡とか考えてみないとダメですか？困難性については、しりとりと同じくらい難しそうですよね。クロスワードみたいに途中の接点から単語が延ばせたり、配置できるピースに（幾何的な？topologicalな？）制約があるとか、ピース共有してないし、それぞれシーケンス異なるし。ってことを考えると、ぜんぜん似てませんね。では HEX はどうでしょう。ピースに形があるところが違いますね。なので下部構造のグラフが複雑になってきますよね。だって、I と L が区別できないんだもん。出エッジをCCWでラベル貼りましょう。でも、各手が独立で配置できるし、スコア計算違うし、これもちょっと遠いかなぁ。
と、とにかく、確かに、PSPACE 完全な気はしますよね。ね！えーと、しりとりの論文はどこだ。HEXって何だ？ポリノミオ？知ってるゲーム挙げてるだけじゃないですかよ。もうゲームの困難性とか考えないだろうと思っていたけど、Games, Puzzles, and Computation これ、買いますか？