GPCC2010問題


ハイパーロボット(Ricochet Robots)

何人でも行えるパズルゲームである。16×16のボードにロボットが4台置いてある。ボード上の指定されたゴールに、なるべく少ない手数で、指定されたロボットを移動させることを目指す。

各ロボットの動きには制限がある。障害物に当たるまでは止まらずに、縦または横に直進する。障害物は、ボードの端、ボードにあらかじめ描かれた壁、他のロボットである。各ロボットの直進1回を1手と数える。

人間同士でプレイする場合には、ロボットを動かす前に手順を考えて、手数を宣言する。詳しくは、合同会社ニューゲームズオーダーのRicochet Robotsにある日本語のルールを参照。

以下の盤面は、今年のプログラミング・シンポジウムの夜の自由討論の時間に、参加者同士で勝負したときの一場面である。太い線は壁、は今回のゴール、はゴールに動かすべきロボット、は障害物として使えるロボットである。

┏━┯━┯━┯━┯━┳━┯━┯━┯━┯━┯━┳━┯━┯━┯━┯━┓
┃□│□│□│□│□┃□│□│□│□│□│□┃□│□│□│□│┃
┠─┼─┏━┥─┼─┸─┼─┼─┼─┼─┼─┸─┏━┥─┼─┼─┨
┃□│□┃□│□│□│□│□│□│□│□│□│□┃│□│□│□┃
┠─┼─┸─┼─┼─┼─┼─┼─┼─┼─┼─┼─┸─┼─┰─┼─┨
┃□│□│□│□│□│□│□│□│□│□│□│□│□│□┃│□┃
┠─┼─┼─┼─┼─┼─┰─┼─┰─┼─┼─┼─┼─┼─┗━┥─┨
┃□│□│□│□│□│□┃□│□┃□│□│□│□│□│□│□│□┃
┠─┼─┼─┼─┼─┼─┗━┥─┗━┥─┼─┼─┼─┼─┼─┼─┨
┃□│□│□│□│□│□│□│□│□│□│□│□│□│□│□│□┃
┣━┥─┼─┼─┝━┓─┼─┼─┼─┼─┰─┼─┼─┼─┼─┝━┫
┃□│□│□│□│□┃□│□│□│□│□┃□│□│□│□│□│□┃
┠─┼─┰─┼─┼─┸─┼─┼─┼─┝━┛─┝━┓─┼─┼─┼─┨
┃□│□┃□│□│□│□│□│□│□│□│□│□┃□│□│□│□┃
┠─┝━┛─┼─┼─┼─┼─┏━━━┓─┼─┼─┸─┼─┼─┼─┨
┃□│□│□│□│□│□│□┃□│□┃□│□│□│□│□│□│□┃
┠─┼─┼─┼─┼─┰─┼─┃─┼─┃─┼─┼─┼─┼─┼─┼─┨
┃□│□│□│□│□┃□│□┃□│□┃□│□│□│□│□│□│□┃
┠─┼─┏━┥─┼─┗━┥─┗━━━┛─┼─┼─┝━┓─┼─┼─┨
┃□│□┃□│□│□│□│□│□│□│□│□│□│□┃□│□│□┃
┠─┼─┸─┼─┼─┼─┼─┼─┼─┰─┼─┼─┼─┸─┼─┝━┫
┃□│□│□│□│□│□│□│□│□┃□│□│□│□│□│□│□┃
┠─┼─┼─┼─┼─┼─┼─┼─┼─┗━┥─┼─┼─┼─┼─┼─┨
┃□│□│□│□│□│□│□│□│□│□│□│□│□│□│□│□┃
┣━┥─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┨
┃□│□│□│□│□│□│□│□│□│□│□│□│□│□│□│□┃
┠─┼─┼─┼─┝━┓─┼─┼─┼─┼─┼─┼─┼─┼─┼─┰─┨
┃□│□│□│□│┃□│□│□│□│□│□│□│□│□│□┃□┃
┠─┼─┰─┼─┼─┸─┼─┼─┼─┏━┥─┼─┼─┼─┝━┛─┨
┃□│□┃□│□│□│□│□│□│□┃□│□│□│□│□│□│□┃
┠─┝━┛─┼─┼─┼─┰─┼─┼─┸─┼─┰─┼─┼─┼─┼─┨
┃□│□│□│□│□│□┃□│□│□│□│┃□│□│□│□│□┃
┗━┷━┷━┷━┷━┷━┻━┷━┷━┷━┷━┻━┷━┷━┷━┷━┛

人間同士では、真の最小手数を求める必要はない。この勝負では、28手、25手、20手の宣言があり、20手を宣言した人が勝った。その手順はおそらく以下のようなものであった(例えばを右、下、左の順に止まるまで動かすことを、→↓←と書く)。

→↓←
→↓←(で止まる)
↓←(で止まる)
↑→↓←(で止まる)
↓→
←↑←(で止まる)
↓→(で止まる)

計算機では、最小手数は簡単に求まってしまうはずである。真の最小手数はいくつであろうか。[2010-6-16解答あり]

これだけでは簡単なので、次は、ロボットの初期位置を任意に選べるとする。上の盤面で、ロボットの初期位置だけを変えて、最小手数が最も大きくなるような配置はどのようなものだろうか。[2010-6-16解答あり]

解答へ


コリドール(Quoridor)

2人で行うボードゲームである(4人で行うルールもある)。9×9のボードの自分側の辺の中央に自分の駒を置いて始め、先に対岸に着いたほうが勝ちである。2人で交互に、駒を1マス進めるか、長さ2の壁をマスの境界に置く。ただし、対岸に着けないように壁を置いてはいけない。

ARiAdoNEというフリーソフトがある(ルール説明も含まれている)ので、まずはこれに勝てるようなプログラムを作ってみよう。


以下余白