(cache) ルールについて｜学生プログラマ世界一決定戦

ルールについて

1 ルール

このゲームの目的は、マップにブロックを落としていき、一定のライン以上に積み上がらないように多くのスコアを稼ぐことです。あなたが作成するのは、どの場所にどのように回転してブロックを落とすかを判断するプログラムです。

1.1 ゲーム概観

図1 ゲームのスクリーンショット

1 フィールド
フィールドは正方形のグリッドで構成される長方形です。この一番上までブロックが積み上がるとゲームオーバーになります。
2 ブロック
ブロックはそれぞれ、配置されると下にどんどん積み上がっていきます。ブロックにはそれぞれに番号が振られており、連続して直線につながった複数のブロックの合計値が指定の値になるとブロックは消去されます。
3 お邪魔ブロック
ブロックを消すのに必要な合計値より大きい数を持ったブロックがゲームの中で出現することがあります。ブロックが消去された場合、隣接したお邪魔ブロックも消去されます。
4 パック
パックはブロックの集まりとして与えられ、プレイヤーはブロックを積み上げていく際にこのパックをどの位置から落とすか、どれだけ回転させるかを選ぶことができます。パックは投下されるとパックを構成するブロックは独立したものとなり、それぞれが一番下まで落ちていきます。
5 ターン
ターンはパックを落としてからフィールドに落ちているブロックもこれ以上消えるブロックも無くなるまでの流れを指します。フィールドごとに最大で許されるターン数は決まっており、プレイヤーはこのターンの間死なないようにするのはもちろん、許されたターン数の中でより高い評価を得ることを目指します。
6 スコア
ブロックを消すことによって、与えられた式に応じてスコアが加算されます。基本的に後述するチェインを大きくすればするほど、また同時に多くの和が指定の値になる組みを作成するほど高得点が加算されます。
7 チェイン
一つのターンの中でパックを投下しブロックが消えた後、そのブロックの消去に依って別のブロックが落下し、さらにもう一度ブロックが消去されることがあります。これを何度繰り返したかの回数をチェインとよび、チェインが大きければ大きいほど消えた時の点数は大きくなります。
8 最大チェイン
このゲームが始まってから出した最も大きい数のチェインです。
9 ネクスト
次に投下する予定のパックを表しています。ゲーム画面に表示されているネクストは一つのパックのみですが、プログラムには予め全てのターンのパックの情報が与えられます。

1.2 より詳細なゲームのルール

ゲームのうち、パックを投下してから次のパックを投下するまでの間をターンと呼びます。一つのゲームにおける最大のターン数 N は予め与えられます。一つのターンは次のような流れで進行します。

1. パックの回転、投下位置の指定
2. 終了条件を満たしていれば終了、そうでなければ 3 へ
3. 落下できるブロックがあれば全て落下
4. 消去できるブロックがあれば全て消去
5. 落下出来るブロックが再び現れたなら 3 へ、無いなら 6 へ
6. 終了条件を満たしていれば終了、そうでなければ次のターンへ

次からの項目でそれぞれの処理内容について説明します。

1.2.1 パックの投下

パックを投下する段階ではパックの投下位置、回転回数を標準出力に所定のフォーマットで出力する必要があります。パックは常に正方形の中に収まる形で与えられ、その正方形の大きさ T はチャレンジの最初に整数で与えられます。
また、ゲームの最初に全てのターンで投下することになる T × T の大きさのパックの構成は与えられます。

パックの投下位置

パックの落とす位置は一つの整数 X で指定します。空白の列も含んだパックの最も左の列がフィールドの最も左の列と一致する場所に落とす場合を X = 0 とし、そこから右を正とした座標を入力します。パックを落とすにあたって、ブロックが一つでもフィールド外に落ちてしまうような位置にパックを配置することは許されません。逆に言えば、ブロックがフィールド外に落ちてしまわなければ、パックの最も左の列がフィールドの最も左の列より左になるような座標を指定することも許されます。

図2 パックの投下：1,2は可能、3は不可能

パックの回転

パックを回転する回数を一つの整数 R で指定します。パックは 1 回回転するとパックの中心を基点として時計回りに 90 度回転します。以下に例を示します。

図3 パックの回転

回転する回数は 0 ≤ R ≤ 3 でなければなりません。

ブロックの落下

パックの投下を指示すると、それぞれのブロックは独立して落下を開始します。それぞれのブロックは一つ下のマスが床になるか別のブロックになるまで一マスずつ落下を繰り返します。全てのブロックが落下できなくなると落下の段階は終了します。

図4 ブロックの落下の例

1.2.2 ブロックの消去

全てのブロックが落下した状態になると、所定の条件をみたすようなブロックが全て消去されます。この際、消去された状況に応じてスコアが加算されます。ブロックはそれぞれ数字を持っており、縦、横、斜めのいずれかの方向にブロックが繋がり、かつそのブロックの合計の数字が最初に与えられる数 S になると、その和を構成する全てのブロックが消滅します。再度落下できるブロックがある場合はもう一度落下、消去の流れを繰り返し、落下できるブロックがもう無い場合は次のターンへと進みます。

チェイン

一つのターンの中でブロックの消去が何回目であるかの回数をチェインと呼びます。一つでもブロックを消すとチェインの数は 1 となり、このチェインでのブロックの消去によりブロックが落下し、さらに別のブロックが消えた場合はチェインが 2 となります。このように連鎖を繰り返すことでチェインの数が増えていきます。以下に 2 以上のチェインが発生する例を示します。

図5 チェインの例（10を作る）

ブロックの消滅カウント

一回の消去によって加算されるスコアはチェイン C とブロックの消滅カウント E で決まります。消えたブロックの数は実際にフィールドに配置されているブロックの数ではなく、一回の消去の段階で全ての和の条件を満たした組を構成するブロックの数を組の数だけ重複を許して数えた値になります。例えば、1_1 というブロックが底に並んでいて、構成するべき和が 2 である場合に中央の_に 1 のブロックを投下した時、消えたブロックの数は実際に存在する数字の数の 3 ではなく、左の 11 の組みと右の 11 の組みを構成するブロックの数を足した 4 になります。以下に例を示します。

図6 消滅カウント計算の例

お邪魔ブロックの消去について

ブロックを消去した際、消去されたブロックの八方向に隣接したお邪魔ブロックも一緒に消去されます（下記図参照）。お邪魔ブロックを消去した場合、ブロックの消滅カウントEにお邪魔ブロックを消去した個数分加算されます。

図7 お邪魔ブロックの消える範囲

発火数カウント

あるターンで加算されるスコア(ターンスコア)が閾値Thを超えた時に、発火数カウントFcが1加算されます。Fcはゲームを通しての累計です。ゲーム開始時はFc=0で与えられます。Fcがカウントされるタイミングは、ターンスコアが決定した後になります。つまり、1ターン目のFcの値は必ず0になります。

スコア

上で説明した２つの値、消えたブロックの消滅カウントE、消去が起きた時のチェインの数C、発火数カウントFc、及びケースごとに与えられる値Pの4つの値を用いて以下の式に従います。

投下して最初に起きる消去はC=1になります。またE/3は整数除算した値になります。さらにゲーム開始時のFcの値は0になります。
よって、最初のターンで2つのブロックを消した場合はC=1, E/3=0,Fc=0となり1点となります。

1.2.3 終了条件

ターンの標準出力後あるいは終了時に以下の終了条件を満たしているとその地点でゲームは終了となり、その地点でのスコア、最大チェイン、ターン数でゲームの結果が確定します。

フィールドの一番下のY座標を0として、これ以上ブロックが落下も消去も起きない状態でHの座標に一つでもブロックが置かれている。
フィールドの幅をはみ出る位置にブロックを投下した
フォーマットに従わない標準出力を行った
実行時間が3時間を越えた

また、全てのターンのパックを以上の終了条件を満たさずに投下した場合はゲームクリアとなり、ゲームは終了しゲームの結果が確定します。
ゲーム開始時、あるいは進行中に以下の条件が満たされた場合、ゲームは終了し、スコアも送信されないか、あるいは送信後に履歴から削除されます。

内部データが不正に操作されている
指定した実行ファイル、あるいはコマンドが正しく実行できない
指定した実行ファイル、あるいはコマンドの標準入出力を取得できない
ネットワークのエラーから、サーバにゲーム開始、終了のリクエストが送れない
チャレンジの途中で中断ボタンを押した
標準入力を読み取らずバッファがいっぱいになる、あるいは必要以上の標準出力を一度に送り標準出力のバッファがいっぱいになる

終了条件に関する諸注意

クライアントはターン開始時、最初のターンからの経過時間からクライアントの処理時間を引いたプログラム自身の実行時間が既に3時間を超えていると、その地点で終了条件を満たしゲームオーバーとなります。よって、最後のターンでは3時間をオーバーしても結果として受理され、これを3回繰り返して提出された結果はそこまでのスコアが結果として採用されます。ただし、各々のケースにおける3回の連続した実行の、クライアントの処理や通信時間などを含んだ実行時間が9時間30分を超えると正しい回答として処理されませんのでご注意ください。
終了条件の一番最後にある標準入出力のバッファがいっぱいになるという現象は、作成したプログラムが標準入力を受け取らない、あるいは標準出力を送り過ぎると発生します。特に標準出力は言語に依ってはストリームをフラッシュする関数を呼び出さないと実際に反映されません。
(例えば C 言語では環境によっては printf によって書き込んだ文字列は fflush(stdout)を呼び出さないと反映されません。) ゲームを解く際は必ず最初に標準入力を受け取ってから標準出力を送信するようにしてください。
提出された解答はサーバ上で不正な操作を行われていないかのチェックを経た後に結果に反映されます。このため、コンテストの趣旨に反する操作を行った場合の成績の提出は正しく結果に反映されません。

2 コンテストの流れ

2.1 結果提出まで

参加者にはこちらで用意したクライアントプログラムを用いて、プログラムの計算した出力をサーバに提出して貰います。クライアントに名前(ハンドルネーム)を入力したら、クライアントで作成したプログラムの実行コマンドを指定します。コンテスト挑戦時にはそのコマンドが実行され、プログラムの標準入力に判断に必要な情報が決まったフォーマットで流し込まれるので、プログラムはその情報からどのようにパックを落とすかの判断を決まったフォーマットで標準出力に出して貰います。参加者は期限までであれば何度でも課題に挑戦することができます。サーバ上では web の受付とは別に、その提出された答えに不正な内容が含まれていないかを巡回して検証するチェックプログラムが動作しており、そのプログラムが正しい提出であると判断すると(即ち参加者が問題の差し替えやパラメータの不正な操作などをしていないと検証されると)、その成績はランキングに掲載される結果として認められます。

2.2 使用言語、参加環境

使用する言語に特に制限はありませんが、外部から実行されることが出来、標準入出力を扱うことが出来る必要があります。また、クライアントプログラムは Java で実装されているので、 Java が動作する OS で実行可能なプログラムを生成できる言語というのも条件となります。プログラムは実行可能であれば、単一の実行ファイルを出力するもの (C/C++,C#) でも、外部実行ファイルを用いて起動するタイプのもの (Java,Python,Ruby など) のように直接実行ファイルが出力されないものでも、実行コマンドを指定することで参加可能です。

2.3 ランキング、決勝進出について

予選では予選向けに与えられるSmall,Medium,Largeの３つのケースについてそれぞれの最高成績で総合の順位が決められます。
それぞれのケースは一回チャレンジするごとに三回の実行が連続して行われ、その三回のスコア、最大チェイン、進んだターン数の合計がチャレンジの成績として提出されます。
Small,Medium,Largeはそれぞれ独立にランキングが付けられ、以下の優先順位で全体順位が決められます。

1.３つのランキングの順位の合計の小ささ
2.３つのケースのスコアの合計の高さ
3.３つのケースの最大チェインの合計の多さ
4.３つのケースの進んだターン数の合計の多さ
5.３つのケースの最高成績のうち、もっとも提出したものが遅いケースの提出日時の早さ

上記によって定められる上位８人が決勝戦への進出権を得ます。
上位に決勝戦進出権を持たない方がいた場合、あるいは辞退者が出た場合は9位以降の方を順次繰り上げとさせて頂きます。
詳しくは後日公開される決勝戦のルールを御覧ください。

3 プログラムの入出力のフォーマット

3.1 インプット

最初にフィールドの幅 W、高さ H、投下するブロックの正方形領域の一辺 T、消去のために作るべき和の値 S、与えられるパックの数 N が半角スペースを開けてこの順に一行で与えられます。次に、投下するべき正方形の領域の構成が以下でN 個与えられます。正方形の領域は、T 行 T 列の行列の要素 Bx,y の形で、値は半角スペースを開けて与えられます。このうち、一行目が最も天井に近い行、最後に与えられる行が最も底に近い行になります。また、0 は空白を意味し、それ以外の値はそのブロックが持つ値を意味します。それぞれのブロックの入力は一行の END と書かれた行で区切られています。これらのパックの情報はゲーム開始時に全て与えられます。以下は入力の例です。

15 20 4 10 3
0 0 0 0
0 0 1 0
0 1 4 0
0 0 0 0
END
0 0 0 0
0 1 1 0
1 5 0 0
0 0 0 2
END
5 4 1 0
0 0 0 0
0 0 0 0
0 0 0 0
END

以上の入力では、以下の3つのパックがこの順番で与えられていることになります。

図8 上記の場合に与えられるパックを左から順に並べた場合

3.2 アウトプット

プログラムはターンごとに、パックを落とす位置X 、時計回りに 90 度の回転を何回行うかの回数 Rを、半角スペースを開けて一行で出力します。例えばパックの左端の列がフィールドの左端の列の一列右にあり、かつパックを 180 度回して落下させる場合は、以下のように一行で出力します。この二つの数より多い、あるいは少ない数の数字を出力した場合は不正な出力をしたとしてゲームが終了します。

1 2
5 2
-2 1

インプットの章における入力に対して以上の出力を行うと、以下に示す位置と回転した状態でパックが投下されます。

図9 上記の input をこの output で処理した場合の落下順序

3.3 与えられるブロックの分布について

パックやブロックは以下のようにして決定されます。

数字i(1≦i≦S)を持つブロックの個数は以下のように決定されます。
：4*(i-1)をSで整数除算した値Dとそのブロックの個数は以下のような比率で決定されます。
　-D=0：1
　-D=1：2
　-D=2：0
　-D=3：0
：比率1でA個のブロックが与えられます。
：お邪魔ブロックはB_obs個与えられます。
ゲームを通して現れるブロックの総数B_totは、
B_tot=((D=0に属する数字の個数)*1+(D=1に属する数字の個数)*2)*A+B_obs
と一定です。
各パックに含まれるブロックの個数はB_totをNで整数除算した値か、その値に1を足した値になります。
パックは、パック内に含まれるブロックの個数が上記と一致するようにしつつ、ランダムな順序で現れます。
ブロックがパックのどこに配置されるかは一様にランダムです。

3.4 与えられるパック列の生成例

例えば、S=5, N=5, A=2, B_obs=5の時、数列は
D=0のi=1,2が1*A=2個
D=1のi=3が2*A=4個
D=2のi=4が0個
D=3のi=5が0個
で構成され、これにB_obs個のお邪魔ブロック(i=6)を加えて13個のブロックの列
[1, 1, 2, 2, 3, 3, 3, 3, 6, 6, 6, 6, 6]
が生成されます。この数列は順序がランダムにシャッフルされます。
[3, 2, 1, 6, 6, 6, 2, 3, 3, 1, 6, 3, 6]
次に、合計ブロック数をN分割する個数の列を作成し、これをシャッフルします。
[2, 2, 3, 3, 3]
↓
[3, 3, 2, 2, 3]
この順番で先程のブロック数個の数字の列を区切ります。
[3, 2, 1], [6, 6, 6], [2, 3], [3, 1], [6, 3, 6]
それぞれのパックは自身の領域内に自分が所有する数値をランダムに配置します。
例えば、T=3の時は以下の様に配置されたパックが与えられます。

2 0 3
1 0 0
0 0 0

0 6 0
0 6 6
0 0 0

0 0 2
0 0 0
0 3 0

0 0 3
0 0 0
0 0 1

0 0 0
6 0 6
0 3 0

このようにして生成されたパックがプログラムの標準入力として与えられます。
シャッフルなどをする際の乱数シードは毎回変動するため、ブロックの順序は一定ではありませんが、以上のように与えられるそれぞれの数字を持ったブロックの総数は常に同じです。