前書き
これは Hamee Advent Calendar 2019 19日目の記事です。
今年も残すところあと僅かなのにこのタイトルはどうなんだというツッコミは華麗にスルー！ネタが他になかったんだYO！
というわけで旬はとっくに過ぎていてアレなのですが、今年の大型連休中に趣味でやっていた競技プログラミング、CODE VS Reborn の体験レポートを書こうと思います。
とは言っても私は競技プログラミングに参加するのは初めてでガチ勢というわけではないです。「競技プログラミングに興味はあるんだけどどんなもんなの？」という方の参考になればと思います。
読み進める前の注意！
このエントリーは、主にプログラミングの楽しさ、面白さを伝えるために書いています。そのため詳細なアルゴリズムの解説は書きません。コードはちょこちょこ掲載しますが完成したコードを公開したりはしません1。あと、わりと勢いで書いているところもあるので内容の正確さも保証しかねます。ご理解いただきたく！
CODE VS Reborn の概要
公式はこちら。
https://codevs.jp/
(2019/12/19 注記：上記リンク先がシステムメンテナンスの表示になっていることを確認しました。2週間ほど前までは普通に公式のページが見れていたのですが…orz)
ざっくり説明すると↓こんな感じです。
- ある対戦型ゲームで対戦して勝敗を決める。
- ただし人間が対戦するのではなくてプログラム同士が対戦する。参加者はそのプログラムを作成する。
- 今回のゲーム（お題）は落ち物パズル。
使う言語に制限はなく2、基本的には現在の状態（盤面）を標準入力で受け取り自分のアクションを標準出力で吐き出すようなプログラムを作ることになります。ガチな方々は C/C++ がデフォだと思うのですが、初参加でしかも出遅れまくっている私（3月下旬にルールが公開されていたようなのですが、私が手を動かし始めたのは4月下旬からだったりします…）はプログラミングを楽しむことを念頭に Java で書くことにしました。レッツエンジョイプログラミング！
ゲームのルール
ルールはざっくり以下の通り。
- ぷよぷよに似たシステム
- 1～9の数字ブロックが3～4個固まって落ちてくる
- 隣接した二つの数字ブロックの和が10だと消える
- 3連鎖以上でお邪魔ブロックを相手に送れる。連鎖数が多いほど多くのお邪魔ブロックを送れる。
- 決まった計算式でスキルゲージが貯まっていき一定量貯まるとスキルを発動できる
- スキルを発動すると、自フィールド内すべての「5」のブロックが爆発して周囲のブロックが全部消える。
- AI にはゲーム開始時に、落ちてくる予定のブロックの全情報が渡される
- AI には各ターン開始時に現在の状態が（敵フィールドの状態も含めて）渡される
- AI はターンごとに自分のアクションを決める必要がある。
- ブロックを落とす場合は「どの位置に」「どう回転して」落とすのか
- それともスキルを発動するのか
本題：AI の開発
準備編
さあやっと本題に入れる！わけですが、具体的なAIを考える前に、まずは下準備としてAIで利用する部品を作りましょう。
具体的には以下のクラスを作ります。
- パックを表すクラス
- フィールドを表すクラス
- プレイヤーの状態を表すクラス
パックを表すクラス
パックはイミュータブルなクラスとして実装してみました3。ブロックは1バイトの数値で表すことにして、以下の意味を持たせます。また回転するためのrotateメソッドも実装します。
- 0 : ブロックはない
- 1～9 : 数字ブロック
- 11 : お邪魔ブロック
class Pack {
private byte[][] blocks = new byte[2][2];
Pack(byte block1, byte block2, byte block3, byte block4){
blocks[0][0] = block1;
blocks[0][1] = block2;
blocks[1][0] = block3;
blocks[1][1] = block4;
}
// コピーコンストラクタ
Pack(Pack pack){
blocks[0][0] = pack.blocks[0][0];
blocks[0][1] = pack.blocks[0][1];
blocks[1][0] = pack.blocks[1][0];
blocks[1][1] = pack.blocks[1][1];
}
// 各位置のブロックを返す
byte getBlock(int x, int y){
return blocks[y][x];
}
// 回転した結果を返す
Pack rotate(){
return new Pack(
blocks[1][0],
blocks[0][0],
blocks[1][1],
blocks[0][1]
);
}
}
フィールドを表すクラス
フィールドの情報は思考ルーチンの中で頻繁な書き換えが必要になると予想できるのでミュータブルなクラスとして実装しておきます。また以下の便利なメソッドも実装しておきます。
| メソッド名 | 内容 |
|---|---|
readFromStdIn |
標準入力からフィールドの状態を読み取る |
fall |
宙に浮いているブロックをすべて下に落とす |
putPack |
パックを最上位の指定の位置に置く |
putOjama |
お邪魔ブロックを最上位の位置に置く |
isDangerOut |
デンジャーラインにブロックがあるかチェックする |
vanishBlocks |
隣接ブロックの和が10になるブロックを消して、消したブロックの数を返す |
countVanishBlocksUsingSkill |
スキルを使用した場合に消えるブロックの数を返す |
vanishBlocksUsingSkill |
スキル使用によるブロック消去を実行し、消したブロックの数を返す |
import java.util.Scanner;
class Field {
static final int ROWS = 18;
static final int COLUMNS = 10;
private byte[][] blocks = new byte[ROWS][COLUMNS];
Field(){
}
// コピーコンストラクタ
Field(Field field){
for(int i = 0; i < ROWS; i++){
for(int j = 0; j < COLUMNS; j++){
blocks[i][j] = field.blocks[i][j];
}
}
}
// 初期化
void clear(){
for(int i = 0; i < ROWS; i++){
for(int j = 0; j < COLUMNS; j++){
blocks[i][j] = 0;
}
}
}
// 標準入力からフィールド情報を読み込む
void readFromStdIn(Scanner scanner){
for(int y = 0; y < Field.ROWS - 2; y++){
for(int x = 0; x < Field.COLUMNS; x++){
int n = scanner.nextInt();
blocks[y + 2][x] = (byte)n;
}
}
for(int y = 0; y < 2; y++){
for(int x = 0; x < Field.COLUMNS; x++){
blocks[y][x] = 0;
}
}
}
byte getBlock(int x, int y){
return blocks[y][x];
}
// 宙に浮いているブロックを下に落とす
void fall(){
for(int x = 0; x < COLUMNS; x++){
int soko = ROWS - 1;
for(int y = ROWS - 1; y >= 0; y--){
byte block = blocks[y][x];
if (block == 0) continue;
if (soko != y) {
blocks[soko][x] = block;
blocks[y][x] = 0;
}
soko--;
}
}
}
// パックを指定位置（の最上位位置）に置く
void putPack(Pack pack, int position){
for(int y = 0; y < 2; y++){
for(int x = 0; x < 2; x++){
byte block = pack.getBlock(x, y);
if (block == 0) continue;
blocks[y][position + x] = block;
}
}
}
// 特定の位置のブロックを設定する
void setBlock(int x, int y, byte block){
blocks[y][x] = block;
}
// お邪魔ブロックを最上位の位置に配置する
void putOjama(){
for(int x = 0; x < COLUMNS; x++){
blocks[0][x] = 11;
}
}
// デンジャーラインを越えたらtrue
boolean isDangerOut(){
for(int x = 0; x < COLUMNS; x++){
if (blocks[1][x] != 0) return true;
}
return false;
}
// 条件が一致したブロックを消去し、消去したブロックの数を返す
int vanishBlocks(){
boolean[][] vanishArea = new boolean[ROWS][COLUMNS];
// 消滅エリアを探す
for(int y = 0; y < ROWS; y++){
for(int x = 0; x < COLUMNS; x++){
byte block = blocks[y][x];
if (block == 0 || block > 10) continue;
if (x < COLUMNS - 1 && block + blocks[y][x + 1] == 10){
vanishArea[y][x] = true;
vanishArea[y][x + 1] = true;
}
if (x < COLUMNS - 1 && y < ROWS - 1 && block + blocks[y + 1][x + 1] == 10){
vanishArea[y][x] = true;
vanishArea[y + 1][x + 1] = true;
}
if (y < ROWS - 1 && block + blocks[y + 1][x] == 10){
vanishArea[y][x] = true;
vanishArea[y + 1][x] = true;
}
if (x < COLUMNS - 1 && y > 0 && block + blocks[y - 1][x + 1] == 10){
vanishArea[y][x] = true;
vanishArea[y - 1][x + 1] = true;
}
}
}
// 消滅エリアのブロックを消し、消したブロックの数を数える
int vanishedCount = 0;
for(int y = 0; y < ROWS; y++){
for(int x = 0; x < COLUMNS; x++){
if (vanishArea[y][x]){
blocks[y][x] = 0;
vanishedCount++;
}
}
}
return vanishedCount;
}
// スキルを使用した場合の消去ブロック数を返す
int countVanishBlocksUsingSkill(){
boolean[][] vanishArea = createVanishAreaUsingSkill();
// 消滅エリアのブロックを消し、消したブロックの数を数える
int vanishedCount = 0;
for(int y = 0; y < ROWS; y++){
for(int x = 0; x < COLUMNS; x++){
if (vanishArea[y][x]){
vanishedCount++;
}
}
}
return vanishedCount;
}
// スキルを利用してブロックを消去し、消去したブロックの数を返す
int vanishBlocksUsingSkill(){
boolean[][] vanishArea = createVanishAreaUsingSkill();
// 消滅エリアのブロックを消し、消したブロックの数を数える
int vanishedCount = 0;
for(int y = 0; y < ROWS; y++){
for(int x = 0; x < COLUMNS; x++){
if (vanishArea[y][x]){
blocks[y][x] = 0;
vanishedCount++;
}
}
}
return vanishedCount;
}
// スキル使用時の消去エリアを返す
private boolean[][] createVanishAreaUsingSkill(){
boolean[][] vanishArea = new boolean[ROWS][COLUMNS];
// 消滅エリアを探す
for(int y = 0; y < ROWS; y++){
for(int x = 0; x < COLUMNS; x++){
if (blocks[y][x] != 5) continue;
for(int y2 = y - 1; y2 <= y + 1; y2++){
if (y2 < 0 || y2 >= ROWS) continue;
for(int x2 = x - 1; x2 <= x + 1; x2++){
if (x2 >= 0 && x2 < COLUMNS){
byte b = blocks[y2][x2];
if (b > 0 && b <= 9) {
vanishArea[y2][x2] = true;
}
}
}
}
}
}
return vanishArea;
}
}
プレイヤーの状態を表すクラス
プレイヤーの状態は、フィールドの状態、スコア、お邪魔ストック数、スキルゲージ、使用時間で表すことができますので、それらを持つクラスを実装します。また、ゲーム中に変化することはないので「状態」とは言えませんが、各ターンで投下されるパックの情報もついでに持たせておきます。
class UserSpace {
Field field = new Field(); // 現在のフィールドの状態
int score = 0; // 現在のスコア
int ojamaStock = 0; // 現在のお邪魔ストック数
int skillGage = 0; // 現在のスキルゲージ
long cpuTime = 0; // 使用時間（ミリ秒）
Pack[] packs = new Pack[500]; // 各ターンで投下されるパック
}
AI の基底クラス（インタフェース）
先にも書きましたが、Code VS の AI は標準入力から状態を受け取り自分のアクションを標準出力に吐き出す必要があります。ですが標準入出力とのやり取りは AI 開発の本質ではありません。そこで AI の思考ルーチンを実装するクラスと標準入出力を行うクラスに分離することにします。また、今後いろんな思考ルーチンを考えることになりますので、思考ルーチンの基底クラスを作っておきます。
というわけでまずは思考ルーチンの基底クラスです。というかインタフェースですね。
public interface AI {
String getName();
/**
* アクション
* @param turn ターン
* @param mySpace 自分の状態
* @param opponentSpace 相手の状態
* @return アクション（b0～3: 投下位置, b4～b7: 回転, b8: スキル使用）
*/
int action(int turn, UserSpace mySpace, UserSpace opponentSpace);
}
次に標準入出力を行いゲームの進行を制御するクラスです。
import java.util.Scanner;
class Game {
private UserSpace[] userSpace = new UserSpace[2];
private AI ai;
private Pack[] packs = new Pack[500];
private Scanner scanner = new Scanner(System.in);
Game(AI ai){
this.ai = ai;
}
// 全ターン分の投入パックを生成する
private void initPacks(){
for(int i = 0; i < 500; i++){
byte a1 = (byte)scanner.nextInt();
byte a2 = (byte)scanner.nextInt();
byte a3 = (byte)scanner.nextInt();
byte a4 = (byte)scanner.nextInt();
packs[i] = new Pack(a1, a2, a3, a4);
while(!scanner.nextLine().equals("END"));
}
}
// ゲーム開始
// 0=プレイヤー0の勝ち、1=プレイヤー1の勝ち、-1=引き分け
public int startGame() {
return game();
}
private int game(){
// AI名を出力する
System.out.println(ai.getName());
// 初期化
initPacks();
System.err.println("Read packs OK.");
for(int i = 0; i < 2; i++){
userSpace[i] = new UserSpace();
userSpace[i].init(packs);
}
for(int turn = 0; turn < 500; turn++) {
System.err.println("Turn " + turn + " start.");
// 各プレイヤーの状態を読み取る
scanner.nextLine(); // ターン数
for(int i = 0; i < 2; i++){
scanner.nextLine(); // 残り時間（ミリ秒）
userSpace[i].ojamaStock = scanner.nextInt(); // お邪魔ストック数
userSpace[i].skillGage = scanner.nextInt(); // スキルゲージ
userSpace[i].score = scanner.nextInt(); // スコア
// フィールド状態
userSpace[i].field.readFromStdIn(scanner);
while(!scanner.nextLine().equals("END"));
}
System.err.println("Read field OK.");
// アクション
int action = ai.action(turn, userSpace[0], userSpace[1]);
if ((action & 256) != 0){
// スキル使用
System.out.println("S");
} else {
// パックを落とす
int pos = action & 15;
int rot = action >> 4;
System.out.println(pos + " " + rot);
}
}
return -1;
}
}
まずは小手調べ：「今が良ければすべてよし！」なアルゴリズム
以上で下準備は完了です。そうしたら、まずは超簡単な AI を作ってみましょう。
AI といっても定形があるわけではないですし色んな考え方があるとは思うのですが、基本的には以下のような考え方のアルゴリズムを作っていこうと思います。
- いま実行し得る全アクションについて、各アクションを実行したときの結果をシミュレートして、その結果に点数をつける。
- 点数は「自分にとって都合の良い結果」であるほど高得点になるよう計算する（この計算式のことを一般に 評価関数 と言います）。
- 点数がもっとも高くなるアクションを採用する。
ここでは評価関数として、「消えるブロックの数＋連鎖数×２＋安全度」を採用してみます。本当はそれ以外にも「いつスキルを使うか」も考えないといけないのですが、ここではひとまずスキルは使用しないことにします。
@Override
public int action(int turn, UserSpace mySpace, UserSpace opponentSpace){
int position = 0;
int rotate = 0;
int maxScore = 0;
Pack pack = mySpace.packs[turn];
for(int pos = 0; pos < Field.COLUMNS - 1; pos++){
for(int rot = 0; rot < 4; rot++){
int score = evalAction(mySpace, pos, pack);
if (score > maxScore){
maxScore = score;
position = pos;
rotate = rot;
}
pack = pack.rotate();
}
}
return position | (rotate << 4);
}
// アクションの評価関数
private int evalAction(UserSpace mySpace, int position, Pack pack){
// 動作をシミュレートしてスコアを計算する
Field field = new Field(mySpace.field);
// お邪魔ブロックの投入
int ojamaStock = mySpace.ojamaStock;
while(ojamaStock >= Field.COLUMNS){
field.putOjama();
field.fall();
ojamaStock -= Field.COLUMNS;
}
// パックを配置
field.putPack(pack, position);
// チェイン開始
int chainCount = 0;
int vanishCount = 0;
for(;;) {
field.fall();
int vanishCountOfThisFall = field.vanishBlocks();
if (vanishCountOfThisFall == 0) break;
vanishCount += vanishCountOfThisFall;
chainCount++;
}
// できるだけ下に積もる方が良い
int blockScore = 0;
for(int y = 0; y < Field.ROWS; y++){
for(int x = 0; x < Field.COLUMNS; x++){
if (field.getBlock(x, y) == 0){
blockScore += Field.ROWS;
} else {
blockScore += y;
}
}
}
return blockScore + vanishCount + chainCount * 2;
}
では出来上がった AI を実行環境に入っているサンプルの AI (NormalAI という名前の AI) と対戦させてみましょう。
左が自分の AI、右が敵の AI です。
ぐ・・・ぐぬぬぬッ！
我が軍は確実にブロックを消していっているにも関わらず、敵軍がお邪魔ブロックを送り込んでくるせいであえなく敗北…！
許さん…許さんぞ…！！
基本中の基本：探索アルゴリズムの導入
先のアルゴリズムでは「いま」だけを見ていました。つまり「いま消せるブロック数」「いま実現できる連鎖数」しか評価していなくて「あとで連鎖するための仕込み」を一切考慮していませんでした。そこでこの「仕込み」を考慮した AI を作ってみましょう。
先のアルゴリズムでは、「いまの状態」に対するすべてのアクションの結果を計算しました。つまり「いまの状態」に対する「次の状態」を計算しました。この考えをさらに深掘りして、「次の次の状態」「次の次の次の状態」を計算するようにして、最終的にたくさんブロックを消せてたくさん連鎖できる起点となるアクションを導き出すアルゴリズムを目指します。
図：「次の次の状態」まで探索する場合のイメージ。この場合では「いまは(位置=0, 回転=1), 次のターンでは(位置=0, 回転=1)」を選択するのが最適ということになる。
どこまで深く探索するかによって AI の賢さは違ってきますが、あまり深くしてしまうと計算に時間がかかってしまいますし、メモリも大量に消費してしまいます。ここでは「次の次の次」まで探索することにしましょう。また、ついでにスキルを使った場合も探索に含めてみることにします。
なお、このゲームでは敵のアクションが自分のフィールドに影響を与える可能性がある（お邪魔ブロックが送られてくるとか）ので、本来的なことを言えば「敵のアクション」も探索の対象にするべきかも知れません。でもそれをやってると探索空間がめっちゃ広くなってしまうので無視します！
static class Node {
int depth;
Node parent;
Field field;
int ojamaStock;
int action;
int score;
Node(int depth, Node parent, int action, Field field, int ojamaStock, int score){
this.depth = depth;
this.parent = parent;
this.field = field;
this.ojamaStock = ojamaStock;
this.score = score;
this.action = action;
}
}
private static final int MAX_DEPTH = 4;
private List<Node>[] nodeDepthList = new List[MAX_DEPTH];
/**
* アクション
* @param turn ターン
* @param mySpace 自分の状態
* @param opponentSpace 相手の状態
* @return アクション（b0～3: 投下位置, b4～b7: 回転, b8: スキル使用）
*/
@Override
public int action(int turn, UserSpace mySpace, UserSpace opponentSpace){
this.mySpace = mySpace;
this.turn = turn;
// スキルを使うか？
if (mySpace.skillGage >= 80){
int vanishCount = mySpace.field.countVanishBlocksUsingSkill();
if (vanishCount >= 20){
return 256;
}
}
// 広さ優先で探索する
Node root = new Node(0, null, 0, mySpace.field, mySpace.ojamaStock, 0);
for(int i = 0; i < MAX_DEPTH; i++) {
nodeDepthList[i] = new ArrayList<>();
}
nodeDepthList[0].add(root);
for (int i = 0; i < MAX_DEPTH - 1; i++) {
for (Node node : nodeDepthList[i]) {
evalNode(node);
}
}
// 最高スコアのノードを探す
Node maxNode = null;
int maxScore = 0;
for(int depth = MAX_DEPTH - 1; depth >= 0; depth--) {
for (Node node : nodeDepthList[depth]) {
int score = node.score * 10 + evalField(node.field);
if (score > maxScore) {
maxNode = node;
maxScore = score;
}
}
if (maxNode != null) break;
}
// そのノードへ辿るアクションは？
Node actionNode = maxNode;
if (actionNode == null || actionNode == root) return 0;
while(actionNode.parent != root){
actionNode = actionNode.parent;
}
// アクションの変換
int action = actionNode.action;
if (action >= (Field.COLUMNS - 1) * 4) {
action = 1 << 8;
} else {
int pos = action / 4;
int rot = action % 4;
action = pos | (rot << 4);
}
return action;
}
private void evalNode(Node node){
if (turn + node.depth >= mySpace.packs.length) return;
Pack pack = mySpace.packs[turn + node.depth];
Field baseField = node.field;
// お邪魔ブロック投下後のフィールドを生成する
int ojamaStock = node.ojamaStock;
if (ojamaStock >= Field.COLUMNS){
ojamaStock -= Field.COLUMNS;
baseField = new Field(baseField);
baseField.putOjama();
baseField.fall();
}
int depth = node.depth + 1;
List<Node> sameDepthNodeList = nodeDepthList[depth];
int max_i = (Field.COLUMNS - 1) * 4 + 1;
for (int i = 0; i < max_i; i++){
Field field = new Field(baseField);
int score = -1;
if (i == max_i - 1){
// スキル使用
if (mySpace.skillGage >= 80) {
score = evalSkill(field);
}
} else {
// 通常のパック投下
int pos = i / 4;
score = evalAction(field, pos, pack);
pack = pack.rotate();
}
if (score >= 0) {
Node child = new Node(depth, node, i, field, ojamaStock,node.score + score);
sameDepthNodeList.add(child);
}
}
}
// フィールドの状態の評価関数
private int evalField(Field field){
// できるだけ下に積もる方が良い
// ただし最下の6行はブロックがあっても気にしない
final int calcArea = Field.ROWS - 6;
int score = 0;
for(int y = 0; y < calcArea; y++){
for(int x = 0; x < Field.COLUMNS; x++){
if (field.getBlock(x, y) == 0){
score += calcArea;
} else {
score += y < calcArea / 2 ? 0 : y;
}
}
}
return score;
}
// アクションの評価関数
private int evalAction(Field field, int position, Pack pack){
// パックを配置
field.putPack(pack, position);
// チェイン開始
int chainCount = 0;
int vanishCount = 0;
for(;;) {
field.fall();
int vanishCountOfThisFall = field.vanishBlocks();
if (vanishCountOfThisFall == 0) break;
vanishCount += vanishCountOfThisFall;
chainCount++;
}
// ゲームオーバー状態になっていたらスコア0
for(int i = 0; i < Field.COLUMNS; i++){
if (field.getBlock(i, 1) != 0) return -1;
}
// スコアの計算
int score = 0;
for(int i = 1; i <= chainCount; i++){
score += (int)(Math.pow(1.3, i));
}
score /= 2;
return score;
}
// スキル使用の評価関数
private int evalSkill(Field field){
// スキルでブロックを消す
int skillVanishCount = field.vanishBlocksUsingSkill();
// チェイン開始
int chainCount = 0;
int vanishCount = 0;
for(;;) {
field.fall();
int vanishCountOfThisFall = field.vanishBlocks();
if (vanishCountOfThisFall == 0) break;
vanishCount += vanishCountOfThisFall;
chainCount++;
}
// スコアの計算
if (skillVanishCount > 11) {
int score = 0;
// チェインスコア
for (int i = 1; i <= chainCount; i++) {
score += (int) (Math.pow(1.3, i));
}
score /= 2;
// 爆発スコア
score += (int) (25.0 * Math.pow(2.0, (double) skillVanishCount / 12.0)) / 2;
return score;
} else {
return -1;
}
}
ではさっそく動かしてみましょう。NormalAI と対戦します！
（左が自分の AI、右が敵の AI です）
うおおおぉぉぉぉッ！勝てる！勝てるぞ！！
ちょっと集中的に積みまくっちゃってるのは少し気になりますが、でもちゃんとに仕込んで連鎖してるのが分かります。これはイイ！
自分で落ちゲーやるときもこの連鎖の爽快感がたまらんわけですが、自分が組んだ AI がそれをやってくれる快感はそれ以上ですぜ！
人は速さを求めるものさ：マルチスレッド対応
さて、探索アルゴリズムを導入したわけだけど、探索は「どこまで深く探索するか」で AI の強さが決まってきます。当然深ければ深いほど強くなるはずですが、そうすると計算に時間がかかってしまいます。競技プログラミングでは時間制限が設けられるので、決まった時間内にどこまで深く探索できるかがキモになります。
そこでまず考えたのがマルチスレッディングです。PC 向け CPU がマルチコアになって 10 年以上経ち、今となってはどんな低スペック PC でもマルチコア CPU を積んでいます。スマホやタブレットも同様ですし、ちっこい IoT デバイスでさえそっちの方向に向かっています。それらマルチコア CPU をいかに活用するかも重要なプログラミングスキルと言えるでしょう。
というわけで各ノードのスコアの計算を一つの「タスク」として、タスク単位でスレッドプールに突っ込んでみます。
private static final boolean MULTI_THREAD = true;
@Override
public int action(int turn, UserSpace mySpace, UserSpace opponentSpace){
// 中略
if (MULTI_THREAD){
// スレッドプール生成
int vcpu = Runtime.getRuntime().availableProcessors();
executorService = Executors.newFixedThreadPool(vcpu);
executorService.execute(new EvalNodeRunner(root));
// 処理が終わるまで待つ
synchronized (this){
if (executorsRemain > 0){
try {
this.wait();
} catch(InterruptedException e){
e.printStackTrace();
}
}
}
executorService.shutdown();
} else {
for (int i = 0; i < MAX_DEPTH - 1; i++) {
for (Node node : nodeDepthList[i]) {
evalNode(node);
}
}
}
// 中略
}
class EvalNodeRunner implements Runnable {
Node node;
EvalNodeRunner(Node node){
this.node = node;
synchronized (MyAI.this) {
executorsRemain++;
}
}
@Override
public void run() {
if (turn + node.depth < mySpace.packs.length) {
Pack pack = mySpace.packs[turn + node.depth];
Field baseField = node.field;
// お邪魔ブロック投下後のフィールドを生成する
int ojamaStock = node.ojamaStock;
if (ojamaStock >= Field.COLUMNS){
ojamaStock -= Field.COLUMNS;
baseField = new Field(baseField);
baseField.putOjama();
baseField.fall();
}
int depth = node.depth + 1;
List<Node> sameDepthNodeList = nodeDepthList[depth];
int max_i = (Field.COLUMNS - 1) * 4 + 1;
for (int i = 0; i < max_i; i++){
Field field = new Field(baseField);
int score = -1;
if (i == max_i - 1){
// スキル使用
if (mySpace.skillGage >= 80) {
score = evalSkill(field);
}
} else {
// 通常のパック投下
int pos = i / 4;
score = evalAction(field, pos, pack);
pack = pack.rotate();
}
if (score >= 0) {
Node child = new Node(depth, node, i, field, ojamaStock,node.score + score);
synchronized (sameDepthNodeList) {
sameDepthNodeList.add(child);
}
if (depth < MAX_DEPTH - 1) {
executorService.execute(new EvalNodeRunner(child));
}
}
}
}
synchronized (MyAI.this) {
executorsRemain--;
if (executorsRemain == 0){
MyAI.this.notify();
}
}
}
}
我が家のメインマシン（Core i5-6400, 4コア4スレッド）で試したところ、シングルスレッドで動かした場合に比べて3倍弱程度の速度になりました。
うーん、もう少し速くなってほしかったなぁ、タスクの粒度が細かすぎたかな？などと色々考えていてふと気づきました。
「そういえば、本番環境の CPU コア数（スレッド数）はいくつなんだろう？」
そうなんです、競技プログラミングでは自分が書いたプログラムを主催者側が用意した実行環境で動かすことになります。いくら自分の PC で速くなっても本番環境で速くなければ意味がありません。当然その環境の情報がどこかに公開されているはずです。というわけで公式サイトで公開されている文書をいくつかダウンロードして読んだところ、それらしい記載が見つかりました。
提出されたAIが稼働する環境は下記の条件になります。ただし、完全に保証された値では
ありませんので、参考程度にしてください。
● CPU：1コア
● メモリ：1024MB
な・・・なんだってーーー！
＼(^o^)／ｵﾜﾀ
ドキュメントはちゃんと読まないといけませんね…(´；ω；`)
それでも深く探索したいのだぜ：枝刈りの導入
マルチスレッドの夢は絶たれましたがそれでも高速化は諦めきれないのであります。そこで検討すべき王道っぽい手法としては枝刈りがあります。「これ以上深く掘ってもあまり意味がないノード」には見切りをつけて、そのノードより下のノードは評価しないようにする、という手法です。ただこれ、見切りをつけるノードの条件を設計するのが難しい。。ぷよぷよをやり込んでる人とかだったらすぐに思いつくのかも知れませんが、大昔にちょろっと遊んだことがある程度で対人戦なんてやったこともない私にはとんでもない難題です。それでもなんとか捻り出したのが以下のような仮説とアルゴリズム。
仮説： 2連鎖以上の連鎖が発生すると、その後数ターンは大量の連鎖は発生しにくい。
アルゴリズム： 2連鎖以上が発生するノード以降のノードは評価しない（ノードを作らない）。
自分でも「ホントかよ…」と思ってしまうような仮説ですし、これでどの程度計算量を減らせるのかも疑問ですが、アルゴリズムは簡単ですし実装も楽でしょうからとりあえずやってみましょう。これまでより1段深く探索するようにしてみます。
private static final int MAX_DEPTH = 5;
@Override
public int action(int turn, UserSpace mySpace, UserSpace opponentSpace){
// 中略
// 最高スコアのノードを探す
Node maxNode = null;
int maxScore = 0;
for(int depth = MAX_DEPTH - 1; depth >= 0; depth--) {
for (Node node : nodeDepthList[depth]) {
if (node.isLeaf) {
int score = node.score * 10 + evalField(node.field);
if (score > maxScore) {
maxNode = node;
maxScore = score;
}
}
}
//if (maxNode != null) break;
}
// 中略
}
private void evalNode(Node node){
// 中略
if (score >= 0) {
Node child = new Node(depth, node, i, field, ojamaStock,node.score + score);
// scoreが1以上（＝2連鎖以上）なら葉にする
if (score > 0 || depth == MAX_DEPTH - 1) {
child.isLeaf = true;
}
sameDepthNodeList.add(child);
}
// 中略
}
それではこれまで通り NormalAI と対戦させてみましょう。
うおおおおおおおお！怒涛の18連鎖だZEッ！！
大量のお邪魔ブロックを送りつけられた敵はナススベナシィッ！！！
しかし実際には、このアルゴリズムは採用できませんでした。なぜなら、計算量があまり削減できていなくて時間切れになることが多いうえ、実はこれまでの AI にあまり勝てないのです…(´・ω・｀)ｼｮﾎﾞｰﾝ
大量連鎖を狙えて面白い AI なんですが、やはり枝刈りの条件が適切ではないのでしょうね。。
作戦変更：スキルを積極的に使おう！
う～ん、良い枝刈り条件を思いつくことができません…もうこれ以上やれることはないのだろうか…？
いや、そんなことはありません。我が軍には、まだ試していない戦法が残されています。それは「スキルを積極的に活用する」戦法です。
ルール説明のところにもちょろっと書きましたが、このゲームにはスキルという概念があります。スキルを利用すると大量のブロックをいっぺんに消すことができ、その結果相手に大量のお邪魔ブロックを送りつけることができます。
これまでは連鎖でお邪魔ブロックを送りつけることを狙っていましたが、今回はスキルでそれをやってみることにしましょう。
基本的なアルゴリズムは以下のようにしてみようと思います。
- フィールドの評価関数（フィールドの状態に対する評価基準）に「スキルを使った場合に得られるスコア（≒相手に送れるお邪魔ブロックの数）」を加算するようにし、また、このフィールドの評価値を大きめのウェイトを設定する。
あと、ついでに探索アルゴリズムを広さ優先のものから深さ優先のものに変更します。変更する理由は以下の通りです。
- 深さ優先は再帰で書けるので実装が楽になる。
- 全ノードの状態（コンテキスト）を保持する必要がなくなるのでメモリ使用量がぐっと減る。
- 細かいことをするには広さ優先の方が良いけどそこまでやるつもりはない（時間的にそこまでやる余裕がない）。
private static class ActionAndScore {
int action;
int score;
ActionAndScore(int action, int score){
this.action = action;
this.score = score;
}
}
@Override
public int action(int turn, UserSpace mySpace, UserSpace opponentSpace){
this.mySpace = mySpace;
this.turn = turn;
// スキルを使うか？
if (mySpace.skillGage >= 80){
int vanishCount = mySpace.field.countVanishBlocksUsingSkill();
if (vanishCount >= 30){
return 256;
}
}
// 深さ優先で読む
ActionAndScore actionAndScore = evalNode(mySpace.field, 0, mySpace.ojamaStock);
// アクションの変換
int action = 0;
if (actionAndScore != null){
action = actionAndScore.action;
}
if (action >= (Field.COLUMNS - 1) * 4) {
action = 1 << 8;
} else {
int pos = action / 4;
int rot = action % 4;
action = pos | (rot << 4);
}
return action;
}
private ActionAndScore evalNode(Field field, int depth, int ojamaStock){
if (depth >= MAX_DEPTH) {
return new ActionAndScore(0, evalField(field) * 10);
}
if (turn + depth >= mySpace.packs.length) return null;
Pack pack = mySpace.packs[turn + depth];
Field baseField = field;
// お邪魔ブロック投下後のフィールドを生成する
if (ojamaStock >= Field.COLUMNS){
ojamaStock -= Field.COLUMNS;
baseField = new Field(baseField);
baseField.putOjama();
baseField.fall();
}
int childDepth = depth + 1;
int maxScore = 0;
int maxAction = 0;
int max_i = (Field.COLUMNS - 1) * 4 + 1;
for (int i = 0; i < max_i; i++){
Field f = new Field(baseField);
int score = -1;
if (i == max_i - 1){
// スキル使用
if (mySpace.skillGage >= 80) {
score = evalSkill(f);
}
} else {
// 通常のパック投下
int pos = i / 4;
score = evalAction(f, pos, pack);
pack = pack.rotate();
}
if (score >= 0) {
score = score * 10 + 1; // ゲームオーバーになっていない分の加算
ActionAndScore actionAndScore = evalNode(f, childDepth, ojamaStock);
if (actionAndScore != null) {
score += actionAndScore.score;
}
}
if (score > maxScore){
maxScore = score;
maxAction = i;
}
}
return new ActionAndScore(maxAction, maxScore);
}
// フィールドの状態の評価関数
private int evalField(Field field){
// できるだけ下に積もる方が良い
// ただし最下の6行はブロックがあっても気にしない
final int calcArea = Field.ROWS - 6;
int score = 0;
for(int x = 0; x < Field.COLUMNS; x++){
for(int y = 0; y < calcArea; y++){
if (field.getBlock(x, y) == 0){
score++;
} else {
break;
}
}
}
// スキル使用時の消去数
int skillVanishCount = field.countVanishBlocksUsingSkill();
if (skillVanishCount > 36) skillVanishCount = 36;
score += (int) (25.0 * Math.pow(2.0, (double) skillVanishCount / 12.0));
return score;
}
それでは対戦させてみましょう。今回は NormalAI とではなく、さっきまで自分で作っていた AI （失敗作ではない方）と対戦させてみます。
左が今回の AI 、右がこれまでの AI です。
お、おお！おおおおお！！なんだかガチバトル感ありませんか！？
序盤は相手から少しずつお邪魔ブロックが送られてきて若干ピンチに見えますがスキルの利用で一気に逆転。大量のお邪魔ブロックのせいで連鎖を組むのに四苦八苦している相手を尻目に再度スキル発動でダメ押しのお邪魔ブロック大量送付！
熱い戦いだゼ！！
自分が作った AI 同士が必死に戦ってるのを見てると、なんだか湧き上がってくるものがありますね。フフフ…私を楽しませておくれ。（←最後に AI に裏切られるマッドサイエンティスト風）
最後の悪あがき：相手の手の内を読む
ここまででだいぶ時間を使ってしまいました。連休もあと2日ほどしか残っていません。この残された時間をどう活用するべきか悩むところですが、ここはこれまでにやってこなかった**「相手のフィールドの状態を見ることで相手がやろうとしていることを推定し、それに対処する」**というアプローチを取り入れてみましょう。「相手がやろうとしていること」には「大量連鎖を狙っている」場合と「スキルで一気にブロックを消そうとしている」場合の2種類があると仮定し、それぞれ以下のような対処を行うようにしてみたいと思います。
- 相手が大量連鎖を狙っている場合は、こちらはスキルで一気にブロックを消すよう仕込んでいく。
- 相手がスキルを使おうをしている場合は、相手のスキルゲージを削っていく。
これまで説明してきませんでしたが、実は3連鎖以上すると相手のスキルゲージを削ることができます。そうすることによって相手がスキルを発動できなくすることができるんです。相手がスキルの発動を画策しているときはスキルを発動できなくしてしまい、相手がまごついている隙にお邪魔ブロックを少しずつ送り込んでしまおうという作戦です。
次に「相手がやろうとしていること」の判定方法ですが、以下のようなロジックで行こうと思います。
- 現在の相手のフィールドでスキルが発動した場合のブロック消滅数が一定数以上ならスキルを使おうとしていると判断する。
- そうでない場合は連鎖を狙っていると判断する。
ではコーディングしていきましょう。
private int opponentOjamaLines; // 相手フィールドに積もっているお邪魔ブロック数
private boolean opponentPrepareSkill; // 相手がスキル発動を画策しているか否かの判定結果
private static class ActionAndScore {
int action;
float skillGageIncreaseScore; // 自分のスキルゲージ上昇スコア
float skillGageDecreaseScore; // 相手スキルゲージ減少スコア
float skillPrepareScore; // スキル仕込みスコア
float safetyScore; // 安全度のスコア
ActionAndScore(int action, float skillGageIncreaseScore, float skillGageDecreaseScore, float skillPrepareScore, float safetyScore){
this.action = action;
this.skillGageIncreaseScore = skillGageIncreaseScore;
this.skillGageDecreaseScore = skillGageDecreaseScore;
this.skillPrepareScore = skillPrepareScore;
this.safetyScore = safetyScore;
}
}
@Override
public int action(int turn, UserSpace mySpace, UserSpace opponentSpace){
// 中略
// 相手フィールドのお邪魔線の数
opponentOjamaLines = 0;
for(int y = 0; y < Field.ROWS; y++){
if (opponentSpace.field.getBlock(0, y) == 11){
opponentOjamaLines++;
}
}
// スキルを使うか？
if (mySpace.skillGage >= 80){
int vanishCount = mySpace.field.countVanishBlocksUsingSkill();
int ojamas = (int) (25.0 * Math.pow(2.0, (double) vanishCount / 12.0)) / 2 + opponentSpace.ojamaStock;
if (ojamas + opponentOjamaLines * 10 >= 150){
return 256;
}
}
// 相手がスキルの使用を画策している？
opponentPrepareSkill = opponentSpace.skillGage >= 30 && evalSkillPrepare(opponentSpace.field, 0) >= 0.3f;
// 中略
}
private ActionAndScore evalNode(Field field, int depth, int ojamaStock){
if (turn + depth >= mySpace.packs.length) return null;
Pack pack = mySpace.packs[turn + depth];
Field baseField = field;
// お邪魔ブロック投下後のフィールドを生成する
if (ojamaStock >= Field.COLUMNS){
ojamaStock -= Field.COLUMNS;
baseField = new Field(baseField);
baseField.putOjama();
baseField.fall();
}
int childDepth = depth + 1;
float maxScore = 0f;
float maxSkillGageIncreaseScore = 0f;
float maxSkillGageDecreaseScore = 0f;
float maxSkillPrepareScore = 0f;
float maxSafetyScore = 0f;
int maxAction = 0;
int max_i = (Field.COLUMNS - 1) * 4 + 1;
for (int i = 0; i < max_i; i++){
float skillGageIncreaseScore = 0f;
float skillGageDecreaseScore = 0f;
float skillPrepareScore = 0f;
float safetyScore = 0f;
Field f = new Field(baseField);
if (i == max_i - 1){
// スキル使用
if (mySpace.skillGage < 80) continue;
int skillScore = evalSkill(f);
if (skillScore < 0) continue;
} else {
// 通常のパック投下
int chainCount = evalAction(f, i / 4, pack); // 連鎖数
pack = pack.rotate();
// ゲームオーバー状態になったらこれ以上掘らない
if (chainCount < 0) continue;
// 1連鎖以上していればスキルゲージは8上昇する
skillGageIncreaseScore = chainCount > 0 ? 1f : 0f;
// 相手のスキルゲージ減少数
int skillGageDecrease = chainCount < 3 ? 0 : 12 + 2 * chainCount;
if (opponentPrepareSkill && skillGageDecrease > 0) {
skillGageDecreaseScore = skillGageDecrease <= 20 ? 0.9f : 1f;
}
}
if (childDepth < MAX_DEPTH) {
ActionAndScore actionAndScore = evalNode(f, childDepth, ojamaStock);
if (actionAndScore != null) {
skillGageDecreaseScore = skillGageDecreaseScore * 0.6f + actionAndScore.skillGageDecreaseScore * 0.4f;
skillGageIncreaseScore = skillGageIncreaseScore * 0.6f + actionAndScore.skillGageIncreaseScore * 0.4f;
skillPrepareScore = actionAndScore.skillPrepareScore;
safetyScore = actionAndScore.safetyScore;
}
} else {
skillPrepareScore = evalSkillPrepare(field, opponentOjamaLines);
safetyScore = evalSafety(field);
}
float score =
weight.skillGageIncreaseWeight * skillGageIncreaseScore +
weight.skillGageDecreaseWeight * skillGageDecreaseScore +
weight.skillPrepareWeight * skillPrepareScore +
weight.safetyWeight * safetyScore;
if (score > maxScore){
maxScore = score;
maxSkillGageIncreaseScore = skillGageIncreaseScore;
maxSkillGageDecreaseScore = skillGageDecreaseScore;
maxSkillPrepareScore = skillPrepareScore;
maxSafetyScore = safetyScore;
maxAction = i;
}
}
return new ActionAndScore(maxAction, maxSkillGageIncreaseScore, maxSkillGageDecreaseScore, maxSkillPrepareScore, maxSafetyScore);
}
// 安全度を計算する
private float evalSafety(Field field){
// できるだけ下に積もる方が良い
int score = 0;
for(int x = 0; x < Field.COLUMNS; x++){
int y = 0;
for(; y < Field.ROWS; y++){
if (field.getBlock(x, y) != 0) break;
}
// yが大きい＝安全
int danger = Field.ROWS - y; // 危険度
score += Field.ROWS * Field.ROWS - danger * danger;
}
return (float)score / (Field.COLUMNS * Field.ROWS * Field.ROWS);
}
// スキル仕込み度合いを計算する
private float evalSkillPrepare(Field field, int ojamaLines){
if (ojamaLines >= 15) return 0;
// スキル使用時の消去数
int skillVanishCount = field.countVanishBlocksUsingSkill();
// スコア
int score = (int) (25.0 * Math.pow(2.0, (double) skillVanishCount / 12.0));
// 相手にぎゃふんと言わせられるスコア
int requestScore = (15 - ojamaLines) * 20;
float ret = (float)score / requestScore;
if (ret > 1f) return 1f;
return ret;
}
だいたいこんな感じでしょうか。ではさっそく前回の AI と対戦させてみましょう。
左が今回の AI 、右が前回の AI です。
ちょっと分かりにくいかも知れませんが、相手のスキルゲージを削りながら自分のフィールドを仕込んでいって、相手より先にスキルを発動できています。その結果、一気に勝負を決めることができています！
良いですね～、狙いが見事にハマりました！
といったところでタイムオーバー。連休最終日の夜がとっぷり暮れて、私の初競技プログラミングは終わりを迎えるのでした。
あとは出来上がった AI をサーバにアップロードして結果を待つだけです。ドッキドキです！
予選結果発表～！
36位（112人中）でした！
本戦への切符は逃しましたが、じっくりやれなかったわりには健闘した方なのかな？
感想
めっちゃ楽しかったです！
やっぱりプログラミングは楽しむものだと思うんですよね。あーでもない、こーでもない、これで行けるはず、でもこっちの方が良いかもしれない、そんな風に色々考えを巡らせながらコーディングしていって、狙い通りに動いた時の爽快感は格別です。
時間的な制約が強くてやりたかったことを全部できたわけではありませんが、十分楽しい時間を過ごすことができました。
謝辞
とても面白いコンテストを開催してくれたリクルートさんに、心より感謝いたします。
また、このエントリーを最後まで読んでくださった皆さんにも感謝します。
プログラミングの楽しさやアルゴリズムを考えることの面白さを少しでも感じてくれたなら嬉しいです！
-
駆け足で書いたコードのためそのまま公開するにはちと恥ずかしい様相を呈しているという理由もあったりなかったり。需要があったらリファクタして公開します。 ↩
-
ただしサブミット対戦機能（コードをサーバにアップロードしてサーバ上で自動的に対戦する機能）を使う場合は Java, C++, C#, Ruby, Python のうちのどれかを使う必要があります。参加者は全員、最初にサブミット対戦機能を使わなければならない（そうしないとオンライン対戦もできない）ので、事実上、これらの言語を使うことになります。てかこれってどうなんでしょう？言語に制限がないのかあるのか判然としません。それにサブミット対戦ではどの参加者も同じコンピュータリソースを使うことになりますがオンライン対戦ではローカルマシンのリソースを使えるからハイスペックなマシンを持ってる人がやたら有利になるような気がします。そういうものなんでしょうか…？ ↩
-
パフォーマンスが重要視される競技プログラミングでイミュータブルとか持ち出すのはどうなんだ？と思う方もいそうですが、奇遇なことに私もそう思います。でもまぁそのなんというか、パフォーマンス優先ならそもそも Java は選ばないわけで、まぁあの、あれです（眠くて語彙が出てこない）。 ↩