Home

本Wikiについて

予選時のオンライン対戦で使っていたAIをアップロードしました。詳細は追記した「決勝のAIについて」を参照して下さい。

本Wikiは、Code VS Reborn に提出したAIについての解説ページです。

予選は同率の４位でした。

決勝は残念ながら初戦敗退で4位でした。なんか予選では絶対しないような変な動きをしてたので、何かがバグってた模様・・・

その点残念でしたが、決勝トーナメントで、唯一自ら相手を殺しに行くスキル発動（4手先までの完全探索のおかげ）を行えた（連鎖が組めなくなったためスキル狙いに切り替えて発動した試合がもう一試合ありました）のが救いかな。次が開催されたらまた頑張ろうかと思います。あと、いろんな戦法とかを聞けて非常に参考になりました。2次会、本当に楽しかったです！

予選の試合で最も印象に残った試合について

20190510_1813 のkeraさんとの試合が一番印象的でした（試合のリプレイファイルをアップしました）

試合の展開を簡単に説明すると

21連鎖を23連鎖でカウンターされ敗北
21連鎖をおそらく相手がうまく返せないタイミングで発動して（相手のカウンターは16連鎖）勝利
15連鎖を相手がうまく返せないタイミングで発動したつもりが、18連鎖で返されて敗北
12連鎖(発動時にスキルが72までたまっていた。多分意図的）+ 12連鎖の3ターン後にスキルを発動して相手に連鎖させずに会心の勝利
22連鎖をおそらく相手がうまく返せないタイミングで発動して（相手のカウンターは16連鎖）勝利

決勝でこういう試合をしたかったなぁ・・・

予選の中で増改築を繰り返すうちに、自分でも解説を早いうちに書かないと何が何だか分からなくなりそうなコードになってしまったので、覚えているうちに解説を書くことにしました。

端折った部分や、不正確な部分が多々あると思いますが、その点はご容赦ください。

なお、本Wikiでは、下記の内容については解説しません。リンク先または、その手の参考書、HP、Wikiなどを参照して下さい。

ゲームのルール。
ゲーム木、ビーム探索など、この手のゲームのAIを作成する際に必要となる基礎知識。
256ビットの論理演算を一度のCPU命令で高速に実行するSIMD(Single Instruction Multiple Data)命令や、64ビットの特殊なビット演算を行う事ができる BMI(Bit Manipulation Instructions Sets)命令など。

更新情報：

2019/05/26:

決勝時のAIについてと、予選時のAIのコードを追加しました。

2019/05/25:

決勝の感想とリプレイを一つ追加しました。

2019/05/24:

最後のほうに「対戦の記録」を追加しました。
record.xlsx に日ごとの20位以内の参加者の順位の推移のデータを追加しました。

2019/05/23:

一通りの記事の完成。

決勝時のAIについて

決勝戦の自分のAIですが、最初の連鎖発火前に謎の3連鎖を行うなど、不可解な行動がみられたので、おそらく何かがバグっているのではないかと思っていました。さらに、今日（5/26日）にtogatogaさんのツイッターで、私のここで公開されているAIとtogatogaさんのAIを対戦させた成績がアップされており、私のAIが惨敗しているのを見て、予選時の対戦成績を考えるとそこまで負けるはずはないので、やはり決勝のAIには何か不具合があるに違いないと確信しました。

そこで、予選の最後でオンライン対戦時のAIと、決勝提出版で40戦ほど対戦させたところ、予選のAIが30勝10敗で圧勝でした。

やっぱりやらかしてました！！！！！

決勝のサブミット環境で他のAIとの実対戦のチェックができなかったとはいえ、完全に自分のミスなので言い訳は全くできないのですが、予選時の私のAIと対戦してみたい人がもしいましたら、予選版のAIをアップロードしておきましたので、使ってやってください。実行する際のパラメータは、下記のオンライン環境のパラメータで動くはずです（なお、このバージョンは -ut をつけないとうまく動作しません）。

なお、サブミット環境とほぼ同じ条件で実行させたい場合は、下記のパラメータで動作させると良いのではないかと思います（一応動くことは確認しました）。実際にこのコードを予選のサブミット環境で走らせてはいないので、変な動作をする可能性はあります。

-bw 5000 -bcw 1500 -bd 16 -bcm 12 -bcm- 1 -bcm2 -1 -bminx 2 -bmaxx 6 -bhm 0 -nbhm 0 -nc -nbw 700 -nbcw 350 -nbihd 10 -nftl 1350 -bihmax 70 -bihmin 70 -bihd 35 -hl1 -20 -hl2 -10 -emdh -5 -ai2 -ai3 -fmcn 10 -fmcm -10 -smcm -5 -nbminc 9 -nfb -ut

なお、予選から決勝までの間に行った何が改悪、もしくはバグっていたのかはまだ調べていませんが、コードは予選時のものは決勝時のものよりもさらに読みづらいと思いますので、中身をみるのはあまりお勧めしません。

今から考えると、なまじサブミット環境でデバッグする方法を見つけてしまったため、あれも変えられる、これも変えられるって感じで予選終了後にいろいろと詰め込んでしまったのが敗因だったような気がするかも・・・

開発環境

開発は、Visual Studio 2017 で C++ を使って行いました。

予選のオンライン対戦は Core i7 8550U メモリ 16G の Windows 10 のノートPCで行いました。

コンパイル方法と実行方法

オンライン環境

オンライン環境では、Visual Studio 2017のReleaseモードでコンパイルしました。「プリコンパイル済プロセッサを使用しない」とする設定以外は特に設定をいじっていないと思います。

実行時に与えたパラメータですが、予選最終時は以下のようになっていましたが、gitにアップしたコードはそれからいろいろと変更されているので、ここで設定されているパラメータのいくつかは最新版では存在していません（予選時の最後のほうでは、5/26にアップロードした予選時最終版のコードをこのパラメータで動作させていました）。

-bw 30000 -bcw 4900 -bd 20 -bcm 12 -bcm- 1 -bcm2 -1 -bminx 2 -bmaxx 6 -bhm 0 -nbhm 0 -tm -nc -nbw 3850 -nbcw 1470 -nbihd 10 -nftl 2500 -ut -bihmax 70 -bihmin 70 -bihd 50 -hl1 -50 -hl2 -25 -emdh -5 -ai2 -ai3 -fmcn 10 -fmcm -20 -smcm -10 -nbminc 8 –nfb

サブミット環境

compile.sh は以下のようになっています。

g++ -o ysai.exe -std=c++11 -O2 -DNDEBUG -march=native -pthread codevsreborn.cpp

決勝提出版の run.sh は以下のようになっています。

./ysai.exe -bw 5000 -bcw 1500 -bd 16 -bcm 12 -bcm2 16 -bcm- -1 -bminx 2 -bmaxx 6 -nc -nbw 700 -nbcw 350 -nbihd 10 -nftl 1350 -bihmax 70 -bihmin 70 -bihd 35 -emdh -5 -ai2 -ai3 -fmcn 10 -fmcm -10 -smcm -5 -nbminc 9 -nebw 500 -nebcw 200 -dbw 200 -dbcw 75 -dbt 350 -ebw 500 -ebcw 200 -ebt 500

ブロック落下シミュレータの高速化

まず、基礎となるブロック落下シミュレータの高速化を目指しました。当然ですが、ここが高速であればあるほど深い探索を行う事ができるようになるため、非常に重要です。

データ構造

決勝のAIの締め切りの提出後に、参加者のブログなどで公開されたコードの解説などを見る限り、多くの参加者が、ブロックの種類が空白を含めても11種類で4ビットに収まることから、ゲーム盤の1マス分の情報を4ビットで表現している方が多いように見受けられました。また、1列の高さが16なので、1列のデータを4*16=64ビットで表現することで、ブロックの落下処理を pext_u64 で高速に行っている方が多いようでした。ただ、1列の高さは実際にはターン開始時の落下とパックの落下分を含めると19行あるため、この方法では1列のデータを64ビットに収められないのではないかと思うのですが、そこを参加者の方がどう対処しているかについては調べていません。

一方、筆者のAIでは、ゲーム盤のデータ構造は、256ビットのビットマップを後述のように20枚用意しました（1マス当たりのデータ量が20ビットということ）。上記の方法と比べると、単純に5倍ものデータ量が必要になりますが、その代わりブロックの消滅判定を非常に高速に行う事が出来ます。

また、それとは別に各列のブロック数を記録する変数 blocknum も用意しましたが、こちらに関しては高速化とはあまり関係ないので解説はしません。

ビットマップのデータ構造

このゲームのフィールドの大きさは、縦19、横10となっており、一列毎のデータに24ビットを割り当てることで、24*10=240 となり、256ビットで一枚のフィールドのビットマップを表現可能です。1枚のビットマップのデータを256ビットに収めることで、256ビットのビット演算を行うAVX256を利用した高速な計算を行う事ができるようになります。

具体的には、左の列から順に、256ビットのデータから24ビットずつ割り当てています。コードでは、 codevsreborn.hpp 内の BitBoard という名前の struct で定義しています。また、BitBoardでは、BitBoard内の任意の座標のビットを立てたり、BitBoard同士の論理演算を行うメソッドなどが定義されています。

20枚のビットマップの内訳

ゲーム盤のデータは、同じファイル内で定義されている PlayerInfo 内で BitBoard bb[BB_SIZE]; のように定義されています（BB_SIZE=20）。20枚のビットマップの内訳は以下の通りです。

インデックス	説明
0	任意のブロックが存在するかどうか
1~9	インデックスの番号のブロックが存在するかどうか
10	お邪魔ブロックが存在するかどうか
11～19	「20－インデックス」のブロックの周囲8マスのブロックを表す

ビットマップを20枚にした理由

Code VS reborn はそれ以前に開催された Code VS for student と比較すると、ブロックの消滅判定のルールは似てはいますが、以下のように決定的に異なる点があります。

Code VS for student では、縦、横、斜めに並んだブロックの合計 （何マス並んでも良い） が10になった場合にブロックが消滅する。
Code VS reborn では、隣り合った2つのブロックが10の場合のみブロックが消滅する。

Code VS for student のルールでは、ブロックの消滅判定の際に、縦、横、斜め方向のブロックの足し算が必要でしたが、Code VS reborn のルールの場合は、そのような計算は一切必要ありません。

Code VS reborn の場合のブロックの消滅判定は、例えば、1のブロックが消滅する条件は、対応する9のブロックの周囲8マスのいずれかのマスに1のブロックが存在するかどうかを確認するだけでできます。つまり、「1のブロックの所在を表すビットマップ」と「9のブロックの周囲8マスのマスを表すビットマップ」の論理積（AND）演算を行った結果得られるビットマップが、「1のブロックで消滅するマス」を表すビットマップとなります。この演算は、SIMD命令を使う事でCPUの1命令で高速に実行できます。

また、上記の消滅判定は、下記のように、すべての数字のブロックに対して毎回行う必要はありません。必要なブロックに対してのみ行う事で計算量を減らすことができます。

ターン開始時に落下させるパック内のブロック（3個 or 4個）それぞれに対して、「ブロックの番号のブロック」と「10－ブロックの番号のブロック」のみ判定すればよい。
ブロックが消滅した後の場合は、ブロックの消滅によって落下したブロックそれぞれに対して上記と同様のブロックのみ判定すればよい（こちらの場合は結果として全部の数字のブロックの判定が必要になる場合もあるが、そうでない場合もある）。

スキルによるブロックの消滅処理

スキルによってブロックが消滅する場合は、以下の計算で消滅するブロックの位置を計算できます。

「5のブロックのビットマップ」 OR (「5の周囲のブロックのビットマップ」 AND (NOT 「お邪魔ブロックのビットマップ」) AND 「任意のブロックのビットマップ」）

bbを使った場合は以下の式で表現できます。

bb[5] | (bb[15] & (~bb[10]) & bb[0])

ブロック消滅後の処理

ブロックが消滅した場合は、消滅したブロックの分だけ、ブロックを落下させる必要があります。ブロックの各列の落下処理は、ブロックの消滅したマスを列のビットマップデータがあれば、pext_u32 という BMI 命令を使って簡単に計算できます。これを 0 から 10 の 11 のビットマップに対して行えばブロックの落下処理は完了です。

各ブロックの周囲8マスを表すビットマップ（11～19）の計算

各ブロックの周囲8マスを表すビットマップの計算は以下の方法で高速化しました。

パックを落下させた場合

以下のようなテーブルをあらかじめ作っておく（BOARD_WIDTH=10, BOARD_HEIGHT=19)

// around_bb_table[x][y] は、ゲーム盤の(x, y)の座標のマスの周囲8マスを表すビットマップ。
BitBoard around_bb_table[BOARD_WIDTH][BOARD_HEIGHT];

これを利用すれば、パック内の各ブロックに対して、そのパックを落下させた座標を元に、このテーブルを引いて OR 演算を行えば各ブロックの周囲8マスを表すビットマップを計算できます。

ブロックが消滅した場合

ブロックが消滅し、その後消滅した場所にブロックがした場合は、各ブロックの周囲8マスを表すビットマップを計算しなおす必要があります（単純に、(x,y)の位置のブロックが消滅した場合に、around_bb_table と NOT 演算を使って差分で計算するということはできません）。そのため、この場合はまず、各ブロックの周囲8マスを表すビットマップをすべてクリアしてから盤面に残ったブロックの数だけ、around_bb_tableを引いて OR 演算をしなければならないように思えますが、この演算もテーブルを用意することで高速化することが可能です。

具体的には以下のようなテーブルをあらかじめ作っておきます。

// x列のビットパターンを示すことで、まとめて x列のビットが1の座標の周囲8マスを表すビットボードを計算できるようにするためのもの。
BitBoard around_bb_x_table[BOARD_WIDTH][1 << BOARD_HEIGHT];

例えば、ブロックが消滅し、その後にブロックが落下した後の x 列に存在する 1 のブロックのビット列が x1 だった場合、その列の1のブロックの周囲の8マスのビットマップは around_bb_x_table[x][x1] で表現できます。この方法で、「マス」ではなく、「列」単位で各ブロックの周囲8マスのビットマップを計算できるので大幅な高速化が実現できました。

また、この判定ですが、消滅したブロックと、落下したブロックと、そのブロックの対になるブロックだけ再計算すればよいので必ずしも1~9までの全ブロックに対して計算を行う必要はありません。

なお、このテーブルのデータサイズですが、BitBoard が 256bit = 32 byte、BOARD_WIDTH = 10、1 << BOARD_HEIGHT = 2 ^ 19 となっているので、合計は

32 * 10 * (2 ^ 19) = 10 * (2 ^ (5 + 19)) = 160 * (2 ^ 20) = 160MB

となり、かなり大きめではありますが、サブミット環境のメモリ1GBに十分収まっています。

この計算結果をファイルに記録して、実行時に読み込むという風にすれば早くなると思ったのですが、このテーブルの計算の所要時間はノートPCで0.2秒程度（サブミット環境では0.35秒程度でした）で計算できたので、その部分は後回しでいいやと放っておいたら忘れてしまい、このドキュメントを書いた今思い出しました。まあ、AIの強さにはほとんど影響はないと思われます。

まとめ

パックを落下させるたびに、上記の処理を、ブロックが一つも消滅しなくなるまで繰り返せば、ブロック落下時のシミュレータは完成します。繰り返した数が連鎖の数となります。上記の手法で、参加者の中でも最高クラスの速度のブロック落下シミュレータを実装できたのではないかと思います（もしかするともっと速いのがあるかもしれません。その場合は井の中の蛙だったということで・・・）。

連鎖の探索

このゲームは、ゲーム開始後は、できるだけ早く大連鎖を組むことが重要です。そのためには、早い手順での大連鎖を探す必要があります。

このゲームは1手あたり最大、4*9+1=37 (+1はスキル発動）種類の行動パターンがあるため、現実的には完全探索は4～5手が限界だと思われますが、4，5手は到底大連鎖を組むことは不可能です。そこで、ビームサーチまたはChokudaiサーチを使って深い探索を行って大連鎖を探索するのが一般的だと思います（このゲームのAIを解説するいろんなブログがありますので、検索すると良いでしょう）。

本AIでは、ビームサーチを採用しました。Chokudaiサーチは、多様性の確保、時間の管理の容易さというメリットがあるのですが、探索の幅を広げるとメモリを大量に消費する（もしかしてこれは誤解かも？）ため、サブミット環境のメモリ1Gの制限が厳しいと思って採用しませんでした。多様性に関しては別の方法で解決しました。

多様性の確保

ビームサーチでは、探索幅を w とすると各探索深さにおける、評価値が上位 w の局面を採用して次の深さの探索を行いますが、このゲームでは、評価値に工夫を行わないと評価値の上位の局面が似たような局面ばかりになってしまい、多様性が確保できないという問題がでると思われます。そこで、多様性の確保として、各深さの局面をその局面で可能な連鎖数毎に分け、それぞれの連鎖数毎の探索幅を決めることで多様性を確保することを考えました。

これは、例えば、深さ d で最大 10 連鎖可能だった場合、深さ d で 10連鎖を行う行動が必ずしもより深い局面で最大の連鎖を行う事ができる行動とは限らないことを考慮し、深さ d で10連鎖未満の行動も残すことで多様性を確保するということを表しています。

具体的には、ビームサーチを行う際に、最大深さ d, 各深さの探索幅 w, 各連鎖数の探索幅 w2 を設定します。例えば w = 100, w2 = 30 の場合、ある深さで計算された局面の数をその局面で可能な連鎖数ごとにソートした場合、以下の表のようにビーム探索を行います。6連鎖の時点で採用する局面の数の合計が w(100) になるので、5連鎖以下の局面は採用しません。

連鎖数	その連鎖が可能な局面の数	採用する局面の数
10	5	5
9	10	10
8	50	30
7	100	30
6	200	25
5以下	?	0

wに対して、w2をどの程度に設定すればよいかについては、いろいろ試してみたのですが、wの20%～30%あたりがよさそうな感じでした。

早めの大連鎖の達成

この手法で深さ d を増やした場合に見つかる連鎖は、確かに大連鎖を達成できるかもしれませんが、大連鎖を達成するまでの間のターンで大連鎖を達成できるとは限りません。例えば d = 15 で 20 連鎖を達成可能な手順を見つけたとしても、途中の 1 ～ 14 のすべての深さで 10連鎖以下しかできないという可能性があります。

予選で様々な試合結果を見るに、10ターン前後で12連鎖が行えるような連鎖を組んでいないと、たとえ15連鎖のような大連鎖を組めていたとしても先に相手に12連鎖を落とされてつぶされるという可能性が高いということがわかりました。そこで、まず目標とする連鎖数 c を設定し、このビーム探索を行った際に、c連鎖を初めて達成した深さから、c連鎖以外のデータをすべて削除して探索を続けるという手法を取りました。見つかった最速の12連鎖を取る行動を必ず残すということです。

予選では c には12を設定して実行しましたが、これだと12連鎖を最速で達成できる手順が数種類しか見つからないこともあり、多様性が確保できないと思い、最終的には一つ少ない 11 連鎖のデータも残すことにしました。

なお、1手20秒の制限があるので、少し余裕をもって19秒探索した時点で探索を打ち切って、その時点で最も深くまで探索できた深さにおけるもっとも評価値の手順を選びました。12連鎖を19秒以内に見つけられなかったケースはまずなかったと思います。

サブミット環境ではそれに加え、最終目標連鎖数（=16）を決め、それを以上の連鎖が見つかった時点で探索を打ち切りました。

カウンター戦術の普及とその対応

予選の後半になると、連鎖の発火点を上に設定し、相手に先に連鎖させて、それより大きな連鎖で返すというカウンター戦術がみられるようになりました。特にKeraさんのAIが顕著だったと思います。私のAIは特にカウンター戦術を意識して作っていたわけではないのですが、後述するように早いうちからこのカウンター戦術っぽいものをとることもありましたが、本格的にカウンター戦術を実装していたAIほどカウンターが得意だったわけではありません。自分のAIにもカウンター戦術を明確に取り入れてみようと思い、以下のような改造を施しました。

具体的には、上記のビーム探索で、c（=12）連鎖が初めて起きた深さで敵がお邪魔ブロックを40個送り込んだことにして大連鎖を組むという探索に変えてみました。こうすることで、連鎖の発火点が下から4段目より上になる組み方ができるのではないかという考えです。しかし、これを最終日の2,3日前に実装したあたりから、予選の順位が落ち、それまでは大体8位のgold圏内を保っていたのですが、8位圏内も危うくなりました。あせって、予選の最終日の夕方あたりからこの手法をやめて元に戻したところ、なんとか順位が戻って予選突破できたことから、（実際には、順位が戻ったのはこのコードを戻したのが原因と100%言い切ることはできませんが）おそらくこの手法は失敗だったのではないかと思われます。戻して予選を突破出来たの結果オーライだったのですが、最終日は本当に薄氷を踏む思いでした。

なお、この手法のコードは現在のコードから削除済です。

枝狩りについて

最初の大連鎖を組む際に、すべての手を探索すると1手当たり最大36通り（連鎖を組む探索なので、スキル発動は探索に入れない）の行動がとれますが、これを減らすことができればより深く探索を行う事が出来ます。そこで、最初の大連鎖を組むビーム探索では、ゲーム盤の左右2列にブロックを落とさないようにすることで、1手当たりの行動の種類を9×4=36通りから、5×4=20通りに減らしました。こうすることで、連鎖を組む際に、横に平べったく組むのではなく、縦に高く組みやすくなった結果、発火点が高くなって相手が先に連鎖してブロックを降らせて来てもカウンターをしやすくなるという効果も得られたのではないかと思われます。この工夫は予選の前半で実装した後は最後まで実施しました。

なお、この左右2列にブロックを落とさないという工夫は特に誰かの真似をしたわけではなく、自分の過去のバックアップを取っておいたコードで確認できる限りでは予選開始5日目の、4/19日の時点から行っていたようです。

置換表について

探索時に、異なった手順で同じ局面が現れるケースがあります。一度現れた局面をハッシュ化し、置換表に記録しておくことで、次に同じ局面が現れた時に探索を打ち切ることができます。この手法では大幅な高速化は達成できませんでしたが、それなり（数10%程度）の高速化は達成思います。

局面のハッシュ化は fnv_1 を使いました。最初はこの手のゲームの定番である zobrist hash を使ったのですが、zobrist ハッシュは局面が変わった時の差分が少ない場合には有効ですが、連鎖後など大きく局面が変わる場合はあまり早くなく、fnv_1のほうが総合的に早かったのでこちらを採用しました。

並列化について

予選のオンライン対戦で使っていたPCは Core i7 のクアッドコアだったので、並列化も途中から行いました。具体的はブロックを落とす位置（x座標）毎に C++ の thread を使ってスレッドを立ち上げてマルチスレッド化しました。その際に置換表は共有しました。本当は置換表の書き換え時に mutex などを使って排他制御を行うべきなのですが、排他制御をおこなわなくても変な動作がおきなかったので置換票の書き換え時の排他制御は省略しました。排他制御は、次の深さの局面をvectorにpushする際のみ使いました。これによって速度がクアッドコアの4倍にはなりませんでしたが、3倍くらいにはなったと思います。

得られた大連鎖の手順をどこまで採用するか

このビームサーチで得られた大連鎖の手順のうち、最初に c 連鎖が達成された所までを記録して採用しました。最後まで採用しなかったのは、あまり長く採用すると相手の先出しの大連鎖に対応できなくなるためです。ただし、8ターンまでに相手が大連鎖してくることはまず考えられないので、8手目までは無条件で最初に計算した手順を取ることにしました。8手目以降にビームサーチで計算した手をとるかどうかの判断については後述します。

評価値について

ビーム探索時の局面の評価値ですが、基本的にはその局面でとれるすべての手（その深さで実際にパックを落とせる最大36通り）を落としてみた時の最大連鎖数をベースに評価値を計算しました。他の方のブログとかを見ると、大連鎖を狙うビーム探索時の評価値は、一つだけブロックを落としてみて連鎖可能かどうかを調べるという、連鎖の潜在能力を測る方法で計算している人が多いようでしたが、本当にそのターンに連鎖できるかどうかが重要だと考え、その手法は取りませんでした（この後説明する、通常の探索時にもこのことは影響します）。評価値はいろいろ試行錯誤した結果以下のような式で計算しました。意図としては最深部までで行える連鎖数を最大に維持したうえで、最深部でも大連鎖を狙えるようにするというものです（ｂはほとんどおまけです）。

c1 = 探索した深さまでに行える最大連鎖数
c2 = 最深部での局面でとれる最大連鎖数
b = 最深部で最大連鎖した後の残りブロック数

評価値 = c1連鎖で落とせるブロック数 * 1000 + c2連鎖で落とせるブロック数 * 100 + b

ただし、あまり上まで積むとお邪魔が落ちてきたときに満足にカウンターできなくなるので、14段目以降にブロックが積まれる場合は評価値を0としました。

なお、途中では、以下のように評価値を計算していたころもありました。ただ、下記の評価値では、探索の途中で最大連鎖が組めた場合があったとしても、その行動が採用されないケースがあるので最終的には不採用としました。

評価値 = 前の深さまでの評価値 * k + c2連鎖で落とせるブロック数 * 100 + b

k は定数で、小さくすると深い局面での連鎖数が重視され、大きくすると浅い局面での連鎖数が重視されます。

また、他の参加者の方で、連鎖しやすいようなブロックとブロックの位置関係を評価している人も見受けられましたが、筆者のAIではそのような工夫は行いませんでした。筆者のやり方とどちらが優れているかは、比較していないので不明です。

ビーム探索に関するパラメータについて

自分のPCでオンライン対戦した際のビーム探索のパラメータは以下の通りです。（）がついているのは、並列化による高速化を実装する前に使っていた数値です。

	オンライン環境	サブミット環境
最大ビーム深さ	20	16
ビーム幅	50000（10000）	5000
連鎖数毎のビーム幅	5000（3500）	1500
最初の目標連鎖数	12	12
最終目標連鎖数	なし	16
制限時間(ms)	19000	19000

上記のパラメータで、少なくともオンライン環境では他の上位AIとほぼ遜色ない速さで12連鎖を組むことが可能な感触を得られました（統計を取ったわけではないので自分のAIのほうが本当に速いかどうかは不明）。サブミット環境でもおそらく連鎖の速さは平均して1ターン弱ほどしか変わらないような気がします。

最善手の探索（初期バージョン）

参加者のAIの記事を見ると、多くの方はビームまたはChokudaiサーチで大連鎖を探し、相手の状況もある程度見ながら連鎖の発火を行うかどうかの判断を行っているように思えます。筆者のAIでもビームサーチで大連鎖を探してはいますが、そちらはあくまで補助とし、常に自分と相手の両方に対して4手先（ただし、時間が無くなってきたらこれを3手先、2手先まで減らす）までの完全探索＋α（+αが何かについては後述します）を行って最善手を探すという手法を取りました。

利点と欠点

上記のように、自分と敵の両方で4手先までの全探索を行うことの利点と欠点は以下のようなものがあると思います。

利点

大連鎖を発動できるような状況になった時、いつ連鎖を発動するのが最も有利かをある程度判断できる。

大連鎖（例えば11連鎖以上）を発動できるような状況になった時でも、すぐに発動せずに数ターン待ってから発動したほうが良いケースがありますが、4ターン先まで、自分と相手の両方で全探索を行う事で、4ターン先までのどこで大連鎖を発動すればよいかの判断をある程度正確に行う事ができるようになります（もちろん4手目の時点では状況がよく見えても、実際には5手目以降で不利になるケースもままありますが・・・）。

小連鎖による妨害もうまく評価できる

ゲームの序盤ではまずありえませんが、相手のフィールドにある程度のお邪魔を降らせた後であれば、4手先までの間で、小さな連鎖を発動して相手にお邪魔をふらせることで、相手の連鎖の発火点をつぶすなどの理由で相手に大打撃を与えるケースがありますが、それを正確に読むことができるようになります。

最悪のケースを回避できる

相手の局面に対しても4手先まで全探索することで、各ターンにおける最悪のケースを想定し、それに対する対策を取ることができるようになります。中盤以降の相手の小連鎖による妨害にも対処できるようになります。

4手以内で相手が詰むような行動が存在する場合、確実に最短で相手を詰ませることができる。

滅多にありませんが、数手差で勝ち負けが決まるような状況で強くなれます。また、4手以内の相手の詰みを逃がすことがなくなります。

いわゆるボマー（スキルで相手に大量のお邪魔を降らす戦法）に強くなる。

スキルを発動するにはスキルポイントを80溜める必要がありますが、それを防ぐためには、約2ターンおきに3連鎖以上を行う必要があります。4手先まで完全探索を行えば、相手がスキルポイントを80以上溜められないような小刻みな3連鎖の行動を取ることができるようになります。

欠点

探索に時間がかかる

当然ですが、全探索には時間がかかります。特に、サブミット環境はあまり計算速度が速い環境ではないようで、筆者のPCと比べて並列処理を行わなかった場合に1.5倍くらい遅いような感じがしました。それでも前述の高速なシミュレータにより、4手先までの完全探索＋αを自分と敵の両方に対して毎ターン行っても、平均して勝敗の大勢が決まっている30ターンくらいまでは耐えられるようでした。

自分と敵の4手先までの全探索に時間がかかり、大連鎖を組むためのビーム探索に割り当てることが可能な時間が減る。

この欠点は確かにありますが、いろいろ試してみたところ、1秒のビーム探索と2秒のビーム探索で見つかる最大連鎖数に劇的な差はなく、得られる利点のことを考えるとこの欠点を上回ると思われます。

相手の行動を気にしすぎるのは必ずしも最善ではない（しかし、気にしないわけにもいかない・・・）

敵の4手先までの全探索を行う事で、各ターンにおけるもっとも自分に不利な状況を調べることができますが、実際に敵がそのような行動をとってくるとは限りません。また、敵が妨害してくると想定した場合の最善手は、敵が妨害してこなかった場合には悪手になってしまう可能性が高いです。ただ、最悪のケースを無視して行動した場合に、相手が最悪のケースの行動をとってきた場合は致命的なので、そこらへんをどうするかが非常に悩ましい問題となります。予選の序盤ではこの点については考えず、常に相手がこちらにとって最悪の行動をとると仮定しました。予選の後半ではこの点について後述のような対策を取りました。

序盤で中連鎖（8～10連鎖あたり）を行ってしまう

4手先までしか読まないので、4手先までで10連鎖以下しか連鎖を組めない場合、10連鎖以下を発動してしまうケースが出ました。特に序盤でこれをやってしまうとほぼ負けが確定するので（相手にお邪魔を25以下しか落とせず、相手の連鎖の妨害にならないケースが多いため、その後の相手の大連鎖を防げず負けてしまう）抑制する必要があります。最終的には評価値の計算式に手を加えることで対策しました。

小連鎖（7連鎖以下）による妨害をやりたがるようになる

4手先までしか読まないので、4手先までに大連鎖が見つからず、4手以内に小連鎖（相手に送るお邪魔が9以下）を行う事によって相手にお邪魔を降らせる行動が存在した場合、その行動をとりたがるようになってしまうようです。中盤以降はそのような行動が有効なこともありますが、序盤でこのような行動をとってしまうとやはり致命的です。こちらも最終的には評価値の計算式に手を加えることで対策しました。

5手目以降に大連鎖で逆転されるケースがある

4手先までしか読まないので、5手目以降で相手が大連鎖してカウンターされて負けるケースがある。

予選の序盤ではそのようなことはあまりありませんでしたが、予選の後半から連鎖の発火点を上にすることで相手に先に連鎖させ、より大きな連鎖をカウンターで返すという戦法がでてきました。発火点が上にある場合は、相手の大連鎖がこちらの連鎖開始後から5手目以降になる場合が多く、4手目までの全探索だけでは対応できません。この戦法に対する対処法については後述します。

敵の探索

次に、敵の4手先までの全探索＋αについて説明します。

このゲームでは、相手にどれだけお邪魔を送ったとしても、1ターンに降ってくるお邪魔の数は10で、残りは次のターンまで持ち越されます。そのため、各ターンにおいては「自分のフィールドにお邪魔が降ってこない」か「自分のフィールドにお邪魔が10個降ってくる」かの2通りの状況しかあり得ません。ただし、この2つのどちらの状況が起きるかによってその後どのような連鎖ができるかどうかは大きく変わってくるので、自分の4手先までの全探索を行う際には、各ターンにおいて、お邪魔が降ってくるかどうかを考慮に入れる必要があります。

やりたいことを一言でまとめると、自分の探索時に各深さにおいて、自分のフィールドにお邪魔が降ってくる可能性があるかどうかを知り、それを考慮に入れたい ということです。

詳細を書くと長くなりすぎるのではしょりますが、敵の4手先までの全探索+α時には「探索の各深さにおいて」、「様々な条件毎に」、「敵の様々な行動に対する敵にとってもっと有利な値」を計算します。

様々な条件としては以下のようなものが挙げられます。

どの深さで敵のフィールドにお邪魔が落下したか
スキルをその深さで使用したか
スキルをその深さ以前で使用したか

敵の様々な行動に対する値としては以下のようなものが挙げられます。

その条件で行える連鎖数
その条件でスキルが発動可能な場合に送り込めるお邪魔ブロック数
その条件でフィールド上に存在するブロック数
その条件でフィールド上に存在するお邪魔ブロック数
その条件でフィールド上に存在する、スキルで消せるブロック数（5と5の周辺の通常のブロック数）

また、敵の全探索時に、その深さで敵のフィールドにお邪魔が落下しなかった場合は、落下した場合の状況も加えて探索を行います（これが＋αです）。こうすることで、こちらが連鎖を行って相手にお邪魔を送り込んだ場合の敵の取れる行動も考慮に入れることができるようになります。ただし、当然ですが、これを行うと探索の局面数が増加します（最大2^4=16倍）。

なお、敵の場合は探索時に、上記の情報は調べますが、上記の情報を総合した局面の評価値のようなものは必要ないので計算しません。

この計算には、初期はで、サブミット環境（並列化しない）で長い場合は7秒ほど、平均すると3秒ほどかかったような気がします。探索局面数は最大で 37 ^ 4 * 16 = 約3000万局面なので、1局面あたり 1/数百万秒で計算できているということになるでしょうか（ただし、置換表をつかった枝狩りは行っているので実際に調べる局面数はもう少し少ないはず）。なお、予選終了後の改良ですが、深さ1で自分が相手に送り込めるお邪魔のブロック数の最大数が確定できることを考慮に入れるととでこの時間を約半分にすることができました。

自分の探索

上記の敵の探索で得られた情報を自分の4手先までの全探索時に利用します。自分の探索時には、自分が行った行動の結果、各行動で相手にどれだけお邪魔を送るかを正確に計算することができます。その情報を利用すれば、各深さで相手側のフィールドにお邪魔が降るかどうかがわかるので、自分がそれまでにとった行動に対して、相手がとることができる最悪の行動（例えば最大連鎖数や、スキルでおくりこめるお邪魔の最大数、相手が減らすことが可能なこちらの最大スキルポイントなど）がわかります。その情報を使って、相手が常に自分にとって最悪の行動をとったという仮定で探索を行います。そして、4手先の局面での評価値（計算方法は後述）の最も高い手を最善手として採用します。

こちらの場合は、最大 37 ^ 4 = 約200 万局面を調べる必要があり、サブミット環境でも大体1秒以下で計算することが可能でした。

上記の手順で、4手目まで自分と相手の全探索を行った結果わかる範囲に限られますが、相手が自分にとって最悪の行動をとった場合の最善手を計算して採用するというAIになります。オンライン環境では50ターンくらい、サブミット環境でも30ターンくらいは計算できたと思います（それを過ぎた場合は探索深さを減らす）。

ビーム探索の結果とどちらを採用するか

前述したように、8手目までは無条件で最初に計算したビーム探索の行動を必ずとるようにしていますが、9ターン目からはビーム探索の結果と、上記の全探索で得られた最善手のうちどちらを採用するかについては、以下のように判断しました。

お邪魔が降ってきたらビーム探索の結果は使えなくなるのでその時点で破棄する。
探索時に、初手がビーム探索で得られた行動をとった場合の評価値の最大値も計算しておき、最善手の評価値と比較して差が一定以下の場合は、ビーム探索の行動を優先する。差としては、いろいろ試しましたが最終的には 30 程度に落ち着きました。

評価値の計算方法

序盤の評価値は以下のような要素の合計で計算していました。

相手側の落下予定のお邪魔の数 - 自分側の落下予定のお邪魔の数
相手側のフィールド内のお邪魔の数 - 自分側のフィールド内のお邪魔の数
両端の列に存在する 5 のブロックの数によるペナルティ

この頃は、まだスキルが重要だと思ってたので、5はなるべく端に置かないほうが良いかなと思って入れてました。

自分のスキル発動に関する評価値

自分のスキルポイント	評価値
80 未満	スキルをこの時点で発動できた場合に相手に送るお邪魔の数 * (1 + スキルポイント) / 81
80以上	スキルをこの時点で発動した場合に相手に送るお邪魔の数

スキルポイントが0でも評価値が0にならないように工夫しています。また、この頃はまだスキルを積極的に狙いに行っていたような気がします。

敵のスキル発動に関する評価値

自分のスキルポイント	評価値
56 未満	0
80 未満	-スキルをこの時点で発動できた場合に相手に送るお邪魔の数 * スキルポイント / 80 / 5
80以上	-スキルをこの時点で発動された場合に相手に送るお邪魔の数

あんまり敵のスキル発動に敏感になりすぎると、敵が大連鎖を組んでいる場合でも、スキルを狙っていると勘違いしてしまうようになるので、スキルポイントが56未満（スキル発動まで最速でも4ターンかかる状況）の場合の評価値は 0 としました。

また、実際に発動できなければ危険ではありますが、実質的な被害はないのでさらに 5 で割っています。

上に積みすぎた場合の評価

あまり上にブロックを積みすぎると死にやすくなったり、お邪魔が降ってきた場合の行動が制限されるので、以下のようなマイナスの評価値を設定しました。なお、17段目にブロックが存在すると死んでいるように思えるかもしれませんが、ターン開始時に降ってくるお邪魔も評価の際に考慮に入れているため値が設定してあります。ただし、最終的（本戦提出版）にはこれらを入れると大連鎖を組む際の障害になるので 17 段目以外は最終的には 0 としました。

下からの段数	ブロックの数1つ当たりの評価値
15	-10
16	-20
17	-100

相手を殺しに行く評価

連鎖やスキル発動の結果、相手に致死量のお邪魔を送ることができる場合、なるべく早めに降らせたほうが良いはずです。そこで、相手に致死量のお邪魔を送ることができるかどうかを判断し、できる場合にかなり大きめの評価値を設定しました。詳細は次を見てください。

致死量のお邪魔の数の計算

後いくつ相手にお邪魔を降らせれば致死量になるかを計算しました。相手フィールドに落としたお邪魔ブロックは決して消えないので、単純に考えると160個落とせば致死量となりますが、もう少し工夫しました。具体的には、ターン開始時点での相手フィールドの状況に対して以下の計算を行いました。

上下左右（斜めも含む）が、お邪魔ブロックまたは、ゲーム盤の端で囲まれているブロックの塊を探す（ただし、上方向の端は無視する）。
そのようなブロックの塊があった場合に、その中に5のブロックが一つも存在しない場合は、そのブロックの塊はいかなる方法でも削除することはできないので、そのブロックの塊をお邪魔ブロックとみなす。
各列のお邪魔ブロックの数を計算し、その最大値 b を求める。
160 - b * 10 を致死量のお邪魔ブロックの数とする。

相手に致死量のお邪魔が送られているかの判断基準

探索の最深部において、相手に大量のお邪魔が送られている場合、相手は深さ4までの行動でこちらが送ったお大量の邪魔を返せていないということになります。そこで、そのような場合は、相手は大連鎖を行って送られたお邪魔を返すことができないということにします。

この仮定は、予選の序盤では確かにほとんどの場合に正しかったのですが、予選の後半ではあまり当てにならなくなったと思います（むしろ逆効果になりかねない）。ただ、「序盤で致死量と判断されるためには最低でもお邪魔160以上送る17連鎖以上が必要な点」と、「相手がさらなる大連鎖で返せる場合、深さ4までの行動で返せることが多い点」、「この致死量の判断がゲームの終盤で有効に働くことが多そうに見えた（もしかしたら気のせいかも・・・）」ので、決勝で提出したAIもそのまま残してあります。これが果たして吉と出るか、凶と出るか・・・

まず、致死量のお邪魔が送られているかについては以下の条件で判断します。

探索の最深部において相手側にたまっている落下予定のお邪魔の数が、致死量のお邪魔のブロックの数以上の場合
探索の最深部における敵のスキルポイントから、敵が最短で何ターンでスキルを発動可能かを計算する(= (80 -　スキルポイント) / 8)
スキル発動までに敵が死亡する場合は、致死量のお邪魔が送られていると判断する

上記の基準で致死量だと判断できた場合は評価値に以下の値を加算する。相手に致死量のお邪魔を送ることができる場合、なるべく早めにおくるようにするために、大量のお邪魔を送り込んだターンを引いています。

1e10 - 1e7 * こちらが相手に大量のお邪魔を送り込んだターン　

相手を瀕死にできる邪魔が送られているかの判断基準

致死の条件はかなり厳しいので、相手が瀕死になっている場合に評価値を加算することにしました。瀕死の定義ですが、致死量のお邪魔の数 - 30 以上相手にお邪魔を送っている場合としました。

こちらの場合は、相手を瀕死にするお邪魔が送られているかについては以下の条件で判断します（計算は多少簡略化しています）。

探索の最深部において相手側にたまっている落下予定のお邪魔の数が、瀕死になるお邪魔のブロックの数以上の場合
探索の最深部における敵のスキルポイントから、敵が最短で何ターンでスキルを発動可能かを計算する(= (80 -　スキルポイント) / 8)
スキル発動までに敵が死亡する場合は、致死量のお邪魔が送られていると判断する
そうでなければ、敵がスキルを最短で発動した場合に、こちらに送られてくるお邪魔の数を推定し、その分だけ相手に送られたお邪魔が相殺されたとしても、相手に瀕死となるお邪魔が送られている場合は瀕死とする。

1e9 - 1e6 * こちらが相手に大量のお邪魔を送り込んだターン　

並列化と深さ5までの探索

予選の中盤あたりで、探索の並列化を行った結果、オンライン対戦では自分の全探索を深さ5で行っても3～5秒で完了できることがわかったので、一時期は深さ5で自分の探索を行っていました（敵は最悪その16倍になるので無理）。ただ、強さが目に見えて強くなるという感じがしなかった点と、中盤での工夫で他に計算時間が必要になったので、深さ4に戻しました。

性能について

ここまでが、予選の序盤でのAIで行ったことです（予選開始前まででほぼここまでは完成していました）。大連鎖の探索は最初のターンのビーム探索（大体16～18連鎖くらいまで見つけられる）だけで、それ以降は4手先までの全探索のみでしたが、これでも対戦させるとたまに26連鎖とかがでました。また、意図してそうなったわけではないのですが、結果としてスキルを相手が発動しようとしている時に、ちゃんと妨害するような行動をとってくれたのが印象的でした。

また、自己対戦させると序盤の大連鎖の打ち合いの後は、多くのゲームが終盤は連鎖よりもスキルを発動しようとする側と阻止する側の対戦みたいな感じになりました。スキルが発動すると相手にお邪魔が2000個以上送られて終了みたいな感じが多かったです。そのため、最初は予選でも大連鎖をお互いに発動した後は、スキルの発動合戦になる試合が多くなるのかなと思ってたのですが、そうはなりませんでした。

予選の序盤では、自分のAIはかなり強かったと思います。1位になることも多かったですし、序盤でよくみかけた、とにかく最速で12連鎖を組んで、出来次第発動するというAIや、連鎖を狙わずにひたすらスキルによる大量のお邪魔を送るというAIにはかなり勝率が良かったと思います。

中盤の戦略

予選が中盤になると、最初に組んだ大連鎖だけではなかなか勝てなくなってきました。そこで、最初の大連鎖の後に、次の大連鎖を組む必要がでてきました。さすがに、4手先までの全探索だけでは、偶然大連鎖を組むことはありますが、効率よく大連鎖を組むような行動をとらせることは不可能です。そこで、最初の大連鎖の発動後に、ビーム探索で大連鎖を狙えるような行動を探索するようにしました。ただし、最初のように約20秒かけて探索を行うと時間がいくらあっても足りないので、以下のように規模を縮小し、1秒程度（最大2秒程度とったこともある）で探索を行う事にしました。

なお、当然ですが、最初に大連鎖を探索する場合と異なり、左右の2列にブロックを落とさないというような制限は行わず、すべての場所にブロックを降らせる形で探索を行っています。また、最初と異なり、最速12連鎖をめざす、というようなことは行っていません。

また、他のAIでは一度行ったビーム探索の結果の一部を次のターンの検索に使いまわしたりしているものがあるようでしたが、筆者のAIでは一切使いまわしはせず、毎ターン計算しなおしています。それが良かったのかどうかは不明ですが、特に問題は感じなかったのでそのようにしました。

なお、ビーム探索には時間がかかるので、残り時間が30秒を切った時点で、このビーム探索を含む、すべてのビーム探索は行わないようにしています（そうしないとあっという間に時間切れ負けになる）。残り30秒を切った後は深さの浅い（2~3）自分と敵の全探索のみを使って得られた最善手で行動します。

	オンライン環境	サブミット環境
最大ビーム深さ	20	16
ビーム幅	1500	700
連鎖数毎のビーム幅	300	350
制限時間(ms)	1000	1000

今見てみると、連鎖数枚のビーム幅はサブミット環境のほうが大きいですね。なんでこのようにしたかはちょっと覚えていません。

また、ここで得られたビーム探索による行動と、最善手の行動のどちらを採用するかについてですが、ビーム探索の行動を行った場合の評価値の最大値が、最善手の行動の評価値の差が10以下の場合にビーム探索による行動を採用するようにしました。

自分の探索の見直し

序盤では、相手は必ずこちらにとって最悪の行動をとってくるという仮定を取っていましたが、本当にそれで良いのかという疑問がありました。また、最悪の行動の定義を、「相手がお邪魔をこちらに降らすことが可能な場合、最大限降らせてくる」としていたのですが、相手がお邪魔を降らせた結果、こちらが有利になる（より大連鎖を組める）ケースもあることがわかってきました。

そこで、自分の全探索を見直し、相手がお邪魔を降らせることが可能な場合、「実際に降らせた場合」と「降らせなかった場合」の両方のケースで探索を行い、評価値の低いほうを採用するという風にしました。この実装により、計算量が最悪で 2 ^ 4 = 16倍となりますが、それでも最大3秒程度で計算を行えたので良しとしました。なお、これでゲーム木が min-max 木のようになるので、αβ枝狩りができるはずなのですが、現実的な時間で実行できてしまった点と、他に実装したい要素があったので、αβ枝狩りを後回しにしてしまった結果、結局そのことを忘れてしまい、決勝提出版もαβ枝狩りは実装されていません。ただ、実際には「実際に降らせた場合」と「降らせなかった場合」の両方のケースを計算する必要がある局面はそれほど多くないのでαβ枝狩りを実装しても、ものすごい時間の短縮になるという事はないと思います。

この実装でより正確に状況が判断できるようになったのではないかと思うのですが、これで強くなっているかどうかはちょっとよくわかりません。というのも、この実装をしても順位が目に見えて上がったりしなかったからです。もしかするとこの実装をしないほうが強かったという事もありうるのがこの手の改良の怖いところです。

評価値の見直し

いくつか評価値の見直しを行いました。ただし、それぞれどれくらい効果があったかどうかはいまいちよくわかりません。逆効果なものもある可能性は高いです。

敵の落下予定のお邪魔の数 - 自分の落下予定のお邪魔の数を評価値の一つとして計算していましたが、よく考えるとこの値の10の位は重要ですが、1の位はそれほど重要ではないと思ったので、1の位の値を 1/5 にして評価しました。
20ターン以内に、敵が9連鎖以下（降ってくるお邪魔の数が18以下）の行動をとることはほぼあり得ない点と、実際に落ちてくるお邪魔の数が10こだと、こちらの連鎖はほぼ阻害されないため無視しても良いと考え、敵のそのような行動に対して +50 の評価を加算しました。
自分のフィールドのお邪魔が 70 以下の場合、敵は8連鎖以下の行動を行わないだろうと仮定して、そのような敵の行動に対して、落としてくるお邪魔の数 * 0.9 の評価値を加算しました。
こちらが相手に降らせたお邪魔の合計が 15 以下の場合は、あまり効果がないだろうということで、降らせたお邪魔の数 * 0.9 を減算しました。なお、相手のスキル発動を防止する目的の3連鎖は、相手に降らすお邪魔の数が2なので、ここで減算してもほとんど評価値に影響は与えないので、この計算がスキル発動を防止する連鎖に悪影響をあたえることはほとんどないと思われます。
こちらの小連鎖の抑制

相手フィールドにお邪魔が少ない場合の4～8,9連鎖以下の連鎖は逆効果なので一定量（-10～-20程度）の評価値を減算しました。3連鎖は相手のスキル発動の妨害として行っている可能性があるので、除外しました。

終盤の改良

終盤になると、連鎖に対して、後出しの大連鎖で返すというカウンター戦術を取ってくるAIが増えてきました。筆者のAIは、意図してそのように作っていたわけではないのですが、最初のほうからカウンター戦術も結構とっていましたが、本格的にカウンター戦術を意図したAIと比べるとカウンターの精度は低いといわざるを得ない状況になりました。ただし、カウンター戦術のAIとの対戦成績がすごく悪かったわけではないです。

なお、サブミット環境では、デバッグが難しく、改良した結果動かなくなることが怖かったので、終盤の改良は予選の段階では行いませんでした。そのせいで、サブミット環境のAIは勝率が悪く、かなり足を引っ張られました。これは私だけでなく、参加者のほとんどはそうだったのではないかと思われます。決勝提出版ではサブミット環境でのデバッグ方法（後述）を思いつくことができたので取り入れてあります。

いずれにせよ対策を取ったほうが良いと思い、以下のような改良を行いました。

連鎖を行う事に対する評価の見直し

ターン開始時に以下のような計算を行います。

ターン開始時の局面における、自分の最大連鎖数 c1 と敵の最大連鎖数 c2 をまず計算する。
c1 が 7以下の場合は、相手に10以上のお邪魔を送れないので終了。
c1 <= c2 の場合、このターンで同時に最大連鎖を起こした場合、有利にはならないので終了。
c1 > c2 の場合は、このターンで同時に最大連鎖を起こした場合、自分に有利になるが、自分だけがこのターンに最大連鎖した場合、後に相手がより大きな連鎖を返してくる可能性が残る。そこで、この場合は、以下の表の条件で、2種類のビーム探索を敵に対して行う。

	オンライン環境	サブミット環境（決勝版）
最大ビーム深さ	5(10)	5(10)
ビーム幅	1600	500
連鎖数毎のビーム幅	400	200
制限時間(ms)	1000	1000

注：大事な要素だと思われたので、それぞれ最大1秒かけて探索しています。

こちらが初手で連鎖をしなかった場合に敵が短期間（深さ5）で行える最大連鎖数 c3 を計算する。
こちらが初手で最大連鎖を行った場合、敵が10手以内（深さ10）で行える最大連鎖数 c4 を計算する。
c1 > c3 の場合、敵はこちらを上回る連鎖を用意していないと判断し終了（初手で発動するか、連鎖を伸ばすかは、通常の探索で判断してもらう）。
c1 <= c3、c1 > c4 の場合は、初手でこちらが連鎖することで、相手の大連鎖を防いだうえで、相手は10ターン以内に c1 連鎖を上回る連鎖を行えないことがわかる。そこで、自分の全探索において、初手に c1 連鎖を行う全ての行動に対して以下のボーナス評価値を加算する。なお、ここでビーム探索を10としたのは、10ターンあれば次の大連鎖を組めてしまう可能性が高いので、それ以上の深さまで探索してもあまり意味がないだろうと思ったからです。

c1連鎖で相手に送る邪魔の数 - c4連鎖で相手がこちらに送るお邪魔の数

c1 <= c3, c1 = c4 の場合は特に何もせず終了する。
c1 <= c3, c1 < c4 の場合は、初手でc1連鎖しても、相手が10ターン以内にそれを上回る連鎖を返してくる可能性が高いことを表す。そこで、自分の全探索において、初手に 5連鎖以上（この場合の連鎖はすべて不利になるので5連鎖とした。また、3,4連鎖はスキル妨害の意味があるので除外した）を行う全ての行動に対して以下のペナルティ（負）の評価値を加算する。

c1連鎖で相手に送る邪魔の数 - c4連鎖で相手がこちらに送るお邪魔の数

ビーム探索による行動に対する評価の信頼性の上昇

このゲームではなるべく大連鎖を狙いたいので、毎ターン行う大連鎖を狙うビーム探索によって得られた行動を取りたいのですが、その行動を取ると不利になるケースがあります。これまでは、自分の全探索の最善手の評価値とビーム探索の行動を取った場合の最大の評価値の差が10今の場合はビーム探索の行動を優先するとしていましたが、ビーム探索の評価値をより正確に計算できれば、最善手を選ばずにビーム探索の行動をより安心して取ることができるようになるはずです。そこで、以下の方法で、ビーム探索の行動を行った場合の評価値をより正確に評価できるような工夫を実装しました。

	オンライン環境	サブミット環境（決勝版）
最大ビーム深さ	7	7
ビーム幅	350	200
連鎖数毎のビーム幅	100	75
制限時間(ms)	500	350

注：ここに時間をかけすぎると時間が足り無くなってしまうのと大体の目安が分かればよいので、太さや時間を小さめに設定した。

初手に大連鎖を狙うビーム探索で得られた行動を取った場合、「各深さにおいて、敵が取りうる最大連鎖を行った場合に」、「7ターン以内に行える最大連鎖数」を計算する。
その結果を、自身の全探索時に利用する。具体的には、ビーム探索の行動を取った場合で、こちらが大連鎖を行う前に先に敵がお邪魔を降らせてきた場合に、上記で計算した連鎖でこちらが返すことを前提に最終評価値を調整する。

上記の計算をすることで、ビーム探索で得られた行動を取った場合に相手が先に連鎖してきた場合の安全度をより正確に評価することができるようになります。

スキルモードの追加

このゲームは基本的に一度不利になるとそう簡単には逆転できない（例えば、フィールド上のお邪魔の数が相手より20以上多くなるとまず勝てない）ようになっていることがだんだんわかってきました。大連鎖の組みやすさが違うなどの理由からです。それを覆す可能性があるのがスキルの発動なので、大連鎖の組み合いに勝てそうにない場合は、早々に連鎖を組むのをあきらめてスキル発動に賭けたほうが良いことのほうが多いと思われます。ただし、早めにスキル発動を狙っても大抵の場合はうまくいかないのですが、まず勝てない連鎖合戦を挑むよりははるかにましだと思われます。

そこで、連鎖の組み合いに勝ち目がないと判断した場合は、ビーム探索の評価を変え、連鎖ではなく、より効率的なスキル発動をめざすことができるような評価に変えることで、スキル発動を狙うように変えてみました。

なお、この実装を行わなくとも、大連鎖が見込めない場合は、筆者のAIは自然にスキル発動を狙うようになっており、それで勝つこともたまにあったのですが、完全に手遅れになってからスキルを狙うような状況が多々見受けられたため、これを実装することにしました。

ただし、どのような条件で連鎖をあきらめ、スキルを狙うべきなのかは、非常に判断が難しいと思います。いろいろ試してみた過程で、まだ十分連鎖が狙えるのにも関わらず、連鎖を捨ててスキルを狙った結果負けた試合がかなり発生しました。最終的には以下のようなかなり厳しい条件でスキルを狙うようになったのですが、果たしてこれでよかったのかどうかはいまいちわかりません。

まず、ターンの開始時に、以下の計算を行います。

なお、一度スキル発動を目指すことにした場合は、自分または敵が一定上の連鎖を行う事で、状況が変化するまでは、下記の計算は行わす、スキル発動を目指すことにする。

ターン開始時に行う、大連鎖を狙うビーム探索の際に、各連鎖数を最短でどの深さで行えるかを計算する。
ターン開始時に、敵に対しても大連鎖を狙うビーム探索を計算し、敵が各連鎖を最短でどの深さで行えるかを計算する。ただし、その際のビーム探索の条件は以下のように自分の大連鎖を狙うビーム探索に比べて簡略化する。

	オンライン環境	サブミット環境（決勝版）
最大ビーム深さ	10	10
ビーム幅	750	500
連鎖数毎のビーム幅	250	200
制限時間(ms)	500	500

以下のいずれかの条件が満たされた場合、連鎖をあきらめ、スキル発動を狙う

10ターン以内に自分が行える最大連鎖数が 7 以下の場合。
以下のすべての条件が満たされた場合
- 自分のフィールドのお邪魔の数が20以上（序盤はスキルを狙わない）
- 相手の落下予定のお邪魔の数が20以下（20以上あるということはこちらが大連鎖した後の状況であり、次の大連鎖を狙うべき）
- 相手が10ターン以内に行える最大連鎖数が12以上
- 自分が10ターン以内に行える連鎖数が9以上で、5のブロックとその周囲のブロックの数が10未満（9連鎖以上を狙える場合で、スキル発動を狙ってもたくさん消せそうにない場合は連鎖を狙ったほうがまし）
- 自分が12連鎖を行う事が可能な最短の深さ >= 相手が12連鎖を行う事が可能な最短の深さ + 3
- 自分が11連鎖を行う事が可能な最短の深さ >= 相手が12連鎖を行う事が可能な最短の深さ + 3
- 自分が10連鎖を行う事が可能な最短の深さ >= 相手が12連鎖を行う事が可能な最短の深さ + 2
- 自分が9連鎖を行う事が可能な最短の深さ >= 相手が12連鎖を行う事が可能な最短の深さ + 1
- 自分が8連鎖を行う事が可能な最短の深さ >= 相手が12連鎖を行う事が可能な最短の深さ

下のほうの条件は、相手が12連鎖できる場合でも、それより先に10連鎖とかでつぶせる可能性がある以上、あまり早々とあきらめないようにするための条件のつもりですが、こんなんで良いのかはいまいちよくわかりません。

また、評価値に関してですが、連鎖を狙っている場合は、自分のスキル発動に関する評価値を下げ、スキルを狙いに行きにくいようにするという調整も行いました。

以上が（書き忘れたことは間違っている部分も多々あるかもしれませんが）筆者が主に行った工夫です。

パラメータについて

AIに与えることができるパラメータは、デバッグ用のものも含めてかなり多いです。細かく説明すると大変なので、デバッグ用のパラメータについて説明します。ただし、デバッグ用のパラメータを使いたい場合は、codevsreborn.hpp の最初のほうにある #define DEBUG のコメントを取り払う必要があります（取り払うとメモリ消費量がかなり増えるので、提出版はコメントアウトしてある）

-m オプションをつけて実行するとターンごとのかなり詳細なデバッグ情報が表示されます。大連鎖を狙うビーム探索で得られた行動や、最善手の行動や、ビーム探索で得られた行動を取った場合の行動などが視覚化されて表示されます。
-tm オプションをつけて実行すると、簡略化されたデバッグ情報が表示されます。-mを指定した場合は、-tm も同時に指定したことになります。
-g ゲーム番号　で、AIに与えるファイル内に、複数のゲームの情報が入っていた場合（例えば、ローカル対戦で、試合数を2以上にした場合に、標準入力から得られる入力データ）、これを指定することで、任意のゲームを選んで実行することができます。
-t ターン数で、特定のターン数のみ実行することができます。
Windows のコマンドプロンプトで、codevsreborn.exe パラメータ < input.txt 2> output.txt みたいな感じでデバッグしてました。

サブミット環境におけるデバッグ方法について

予選の間中、参加者のいろんなブログで、「サブミット環境にアップしたAIがタイムアウトする」、「デバッグ表示が見えないので対処したくてもデバッグできなくてどうしようもない」、などの発言が数多くみられました。私も予選期間中は、予選の中盤で作ったAIのうち、なんとかサブミット環境で動くものがアップロードできた後は、動かなくなるのが怖くて予選終了まで手を付けることができませんでした。予選終了後に見直したところ、かなりバグがあって、サブミット環境の対戦の勝率が悪いのはあたりまえだったことが実感できました。

決勝でもこの状況は改善されず、運営になんとかサブミット環境でデバッグ表示を出す方法を用意してもらえないかと問い合わせてはみたのですが、意見は次回以降の参考にするが、今回はこのままで行くとの返事が来ました。予選の最終段階のAIのプログラムは、サブミット環境に提出していたAIとくらべてかなりいろいろと追加されており、処理時間も増えていたので、これをサブミット環境にアップロードしてもおそらくまともに動かないことが予想され、予選のまま行くしかないかと一時は思っていたのですが、サブミット環境でデバッグする方法をうまく思いつけたので、なんとか最新のサブミット環境で動くAIを提出することが出来ました。せっかくなのでその方法について書こうと思います。

サブミット環境に、プログラム言語を zip で指定してAIをアップロードした場合、zip解凍され、その中の拡張子が .sh　のファイルが順番に実行されることは、提出タブに表示されているメッセージから推測できました。その際に、まず compile.sh が実行されてコンパイルが行われ、次にrun.shが実行されてrandomfall AI との対戦が始まると思われるのですが、その際にコンパイルや、対戦時にエラーが出なかった場合は、実行状況の所に一切メッセージは出力されません。

しかし、コンパイルでエラーが出た場合や、コンパイル後の randomfall AI との対戦において何らかのエラーが発生した場合は、さすがにエラーメッセージが表示されるようになっていました（さすがにこれすらなければコンパイルできなかった場合に対処が不能です）。ここにデバッグを行う余地があります。

具体的には zip に、ローカル対戦で得られた標準入力のデータが入った input.txt という名前のファイルを含め、 complie.sh の内容を以下のようにして submit します。

g++ -o ysai.exe -std=c++11 -O2 -DNDEBUG -march=native -pthread codevsreborn.cpp
./ysai.exe AIに与えるパラメータ < input.txt ←この行を追加する

すると、最初の1行目でコンパイルが実行され、その後すぐに、コンパイルして作られたAIの実行ファイルに input.txt の内容が送られ、サブミット環境でinput.txtの内容を元に、AIが実行されます。その後に、run.shが実行されますが、当然ですがその前にAIの出力としては、不正な内容が標準出力に出力されているため、run.shが実行された時点でエラーとなり、実行状況の所に、それまでにサブミット環境で出力された標準出力と、標準エラー出力の内容が表示されます。

後は、そのエラーメッセージを見ながらAIに与えるパラメータの調整を行い、サブミット環境で動くようにしたものを提出すればOKです。

最初はどうしようもないと思っていましたが、意外になんとかなるものです。

対戦の記録

予選期間中に、毎朝順位のスクリーンショットをとっていたもの（screenshot.docx）をアップロードしました。新ためて見返してみると、最後のほうで行った（改良のつもりの）改悪のせいで迷走してますね・・・

あと、オンライン対戦は、replayフォルダに記録が残るので、それをpythonで集計てexcelにまとめたもの(record.xlsx)もアップロードしました。オンライン対戦での日ごとの対戦相手毎の成績が載ってます。全体を通すと、bowwowさんだけに負け越してますね。何か相性が悪かったのかもしれません。

サブミットされたAIの対戦記録ははいっていないようなので、逆算すると以下のようになるでしょうか。やっぱりサブミット対戦だと勝率はガクッと落ちてますね。

	試合数	勝	負	勝率
予選全体	5068	4199	869	0.829
オンライン対戦	4290	3731	559	0.870
サブミット対戦	778	468	310	0.602

おまけ

最後に、codevsに今回参加しようと思ったきっかけについてせっかくなので書いてみようと思います。

codevsの存在を知ったのはやねうらおさんのブログで、確か codevs 4.0 の時だったと思います。AIに興味はあったし、面白そうだと思って参加してみたのですが、その時は予選開始半ばを過ぎており、時間的にどうにもなりませんでした。

次の codevs 5.0 の時も事情は全く同じで、やはりやねうらおさんのブログで存在を知り、参加したのですが、その時も予選開始半ば頃で、頑張ったのですが、silverで力尽きました。

かなり悔しかったので、大会後に自分のAIを改良して、ネットに公開されていた優勝したtakaptさんのAIに8割程度勝てるところまでいって次の大会に備えていたのですが、その後codevsの大会が開かれなくなって半ばあきらめていました。しかし、最近になって Code vs reborn が開かれるということを、またもややねうらおさんのブログで知り、今度こそということで予選を頑張ってなんとか突破することが出来ました。

欲を言えば、この大会を知るきっかけとなった、code vs 5.0 で準優勝したやねうらおさんと対戦してみたかったのですが、やねうらおさんが優勝したコンピュータ将棋世界選手権と日程がかぶっていたようで、その夢は残念ながらかないませんでした。あと、code vs とは関係ないですが、将棋選手権の最後の勝ち方、やねうらおさんらしくて本当に感心しました。

今回の予選ですが、後半いろいろ思いついたことを実装した結果、逆に順位が落ちたりしてひやひやしましたが、最終的にはなんとかなってよかったです。決勝でも良い成績を残せるといいなと願いつつここで一旦筆をおきたいと思います。

書いてて非常に長くなってしまいましたが、ここまで読んでいただいた方には、わかりにくかったかもしれませんがお付き合いいただきありがとうございました。