Skip to content

Home

Jump to bottom
ysgeso edited this page May 27, 2019 · 39 revisions

本Wikiに぀いお

予遞時のオンラむン察戊で䜿っおいたAIをアップロヌドしたした。詳现は远蚘した「決勝のAIに぀いお」を参照しお䞋さい。

本Wikiは、Code VS Reborn に提出したAIに぀いおの解説ペヌゞです。

予遞は同率の䜍でした。

決勝は残念ながら初戊敗退で4䜍でした。なんか予遞では絶察しないような倉な動きをしおたので、䜕かがバグっおた暡様・・・

その点残念でしたが、決勝トヌナメントで、唯䞀自ら盞手を殺しに行くスキル発動4手先たでの完党探玢のおかげを行えた連鎖が組めなくなったためスキル狙いに切り替えお発動した詊合がもう䞀詊合ありたしたのが救いかな。次が開催されたらたた頑匵ろうかず思いたす。あず、いろんな戊法ずかを聞けお非垞に参考になりたした。2次䌚、本圓に楜しかったです

予遞の詊合で最も印象に残った詊合に぀いお

20190510_1813 のkeraさんずの詊合が䞀番印象的でした詊合のリプレむファむルをアップしたした

詊合の展開を簡単に説明するず

  1. 21連鎖を23連鎖でカりンタヌされ敗北
  2. 21連鎖をおそらく盞手がうたく返せないタむミングで発動しお盞手のカりンタヌは16連鎖勝利
  3. 15連鎖を盞手がうたく返せないタむミングで発動した぀もりが、18連鎖で返されお敗北
  4. 12連鎖(発動時にスキルが72たでたたっおいた。倚分意図的+ 12連鎖の3タヌン埌にスキルを発動しお盞手に連鎖させずに䌚心の勝利
  5. 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は勝率が悪く、かなり足を匕っ匵られたした。これは私だけでなく、参加者のほずんどはそうだったのではないかず思われたす。決勝提出版ではサブミット環境でのデバッグ方法埌述を思い぀くこずができたので取り入れおありたす。

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

連鎖を行う事に察する評䟡の芋盎し

タヌン開始時に以䞋のような蚈算を行いたす。

  1. タヌン開始時の局面における、自分の最倧連鎖数 c1 ず 敵の最倧連鎖数 c2 をたず蚈算する。

  2. c1 が 7以䞋の堎合は、盞手に10以䞊のお邪魔を送れないので終了。

  3. c1 <= c2 の堎合、このタヌンで同時に最倧連鎖を起こした堎合、有利にはならないので終了。

  4. c1 > c2 の堎合は、このタヌンで同時に最倧連鎖を起こした堎合、自分に有利になるが、自分だけがこのタヌンに最倧連鎖した堎合、埌に盞手がより倧きな連鎖を返しおくる可胜性が残る。そこで、この堎合は、以䞋の衚の条件で、2皮類のビヌム探玢を敵に察しお行う。

オンラむン環境 サブミット環境決勝版
最倧ビヌム深さ 5(10) 5(10)
ビヌム幅 1600 500
連鎖数毎のビヌム幅 400 200
制限時間(ms) 1000 1000

泚倧事な芁玠だず思われたので、それぞれ最倧1秒かけお探玢しおいたす。

  1. こちらが初手で連鎖をしなかった堎合に敵が短期間深さ5で行える最倧連鎖数 c3 を蚈算する。

  2. こちらが初手で最倧連鎖を行った堎合、敵が10手以内深さ10で行える最倧連鎖数 c4 を蚈算する。

  3. c1 > c3 の堎合、敵はこちらを䞊回る連鎖を甚意しおいないず刀断し終了初手で発動するか、連鎖を䌞ばすかは、通垞の探玢で刀断しおもらう。

  4. c1 <= c3、c1 > c4 の堎合は、初手でこちらが連鎖するこずで、盞手の倧連鎖を防いだうえで、盞手は10タヌン以内に c1 連鎖を䞊回る連鎖を行えないこずがわかる。そこで、自分の党探玢においお、初手に c1 連鎖を行う党おの行動に察しお以䞋のボヌナス評䟡倀を加算する。なお、ここでビヌム探玢を10ずしたのは、10タヌンあれば次の倧連鎖を組めおしたう可胜性が高いので、それ以䞊の深さたで探玢しおもあたり意味がないだろうず思ったからです。

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

  1. c1 <= c3, c1 = c4 の堎合は特に䜕もせず終了する。

  2. 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 ずは関係ないですが、将棋遞手暩の最埌の勝ち方、やねうらおさんらしくお本圓に感心したした。

今回の予遞ですが、埌半いろいろ思い぀いたこずを実装した結果、逆に順䜍が萜ちたりしおひやひやしたしたが、最終的にはなんずかなっおよかったです。決勝でも良い成瞟を残せるずいいなず願い぀぀ここで䞀旊筆をおきたいず思いたす。

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

Clone this wiki locally