【Postmortem】HTTF2023予選(AHC016)

※画像は公式Visualizerよりお借りしています

この記事は11/11~11/20にAtCoderで開催されました、FUTURE様主催のHACK TO THE FUTURE 2023予選（AHC016）のPostmortemになります。

はじめに

　11/11~11/20の9日間開催されていた、HACK TO THE FUTURE 2023予選（AHC016）に参加しました。

　結果ですが、システス前54位、システス後は順位を一つ上げ53位でした。

　以下、最終提出について書いていきます。

この記事で用いる表現について

勝手に使っているあいまいな表現があるので書いておきます

・グラフの差

かなり直感的に考えていたのですが、あえてしっかりと定めるなら二つのグラフをそれぞれ01の行列の形で表し、そのxorをとったものです。xorをとったものの1の数を用いて差が大きいとか差が小さいとか言っています。他の方が的を得た表現をなさっていたので参考にしますと、おそらく辺についての編集距離というものです。

最終提出の概要

　言語はいつも通りGo言語です。

基本的にeps<=0.04かそれ以外の2パターンに分けて考えました。

eps<=0.04の場合

1.事前にグラフを用意しておく

2.与えられたHを頂点swapでM個の各グラフと差ができるだけ小さくなるようにする

3.差が小さかったグラフを答えとする

ちなみにグラフを大量に埋め込んでます。

magic4         形の違う11個のグラフ eps=0.00で使用

magic5         形の違う34個のグラフ eps=0.00で使用

magic6         形の違う100個のグラフ eps=0.00で使用

magic6_2     互いのグラフの差が3以上の13個のグラフ eps<=0.02で使用

magic7     　互いのグラフの差が3以上の37個のグラフ eps<=0.01で使用

magic8        互いのグラフの差が4以上の65個のグラフ 今確認すると不採用

magic9        互いのグラフの差が5以上の50個のグラフ eps<=0.02で使用

magic10      互いのグラフの差が7以上の25個のグラフ eps<=0.04で使用

magic10_2  互いのグラフの差が6以上の100個のグラフ eps<=0.02で使用

magic12      互いのグラフの差が9以上の100個のグラフ eps<=0.03で使用

magic15      互いのグラフの差が15以上の100個のグラフ eps<=0.04で使用

基本的に2k+1の辺の差があればk個までのエラーに確実に耐えられるので、そのあたりを考えつつ生成しました。

　これらのグラフの数はもっとうまくとればよりたくさん用意できると思いますが、そこまでは詰めませんでした。あんまりその頂点数のでの限界数もらっても、実際に5秒で走らせるほうのプログラムの差計算ががそこまで優秀でなかったのでちょっと間違って別の形のほうが近いといわれちゃうのは・・・。

公式解説放送やほかの方の解法を漁ってみたところ、差ではなくより確率的な計算をすれば、あるいはN=9ぐらいのところでグラフを100個用意できていたら、eps<=0.04で使う分にはN=15とかまで考える必要はなさそうです。

　与えられたHを上で用意したグラフそれぞれに寄せる際には頂点のswapによる局所解を500回くらい求めています。初期解を変えつつ500回こなせば頂点15でもそんなに間違えることはありません。

eps>0.04の場合

1.適当なdを求めて,k<M/2について

(A)1をd*k個並べたのちに残り0を並べる

(B)0をd*k個並べたのちに残り1を並べる

を考え、M個のグラフとして設定する

2.与えられたHに貪欲に頂点番号をつけていく

3.グラフの差について二項分布（頂点数が多い場合は正規分布とみなす）として確率を求める

2.の貪欲に頂点番号をつけるというのはepsが小さいときに行っていた「各グラフの形に近づける」という部分に対応しますが、以下のようにつけることで各Gごとに考える必要がなくなります。

2-0,Hの各頂点に頂点番号をつけておきます

2-1.最も辺の数が多い頂点を選びます（この頂点番号をiとする）

2-2.頂点番号iと1を入れ替えます

2-3.頂点番号が2以上の頂点のうち、頂点番号2以上への辺が最も多い頂点を選びます（この頂点番号をiとする）

2-4.頂点番号iと2を入れ替えます

2-5.以下同様にこれを頂点の数くらい繰り返します

最初に辺の数を計算してそこから入れ替えのたびに辺の数を更新していけば、この作業は非常に簡単に終わります。そしてこれは(A)タイプのグラフとの差を考える場合に、swap操作における局所解になります。（A）の01を反転させた（B）については割愛します。

注：一般にグラフ同士の差を考える場合はこのようにはいきません。あくまでM個のグラフを(A)(B)のようにとったからこそ使える方法です。

　実行時間に余裕があるので、初期値を変えつつ上の手法をやり直します。数百～数千回くらいやり直せましたが、多少精度が上がる程度です。

解法の大別

　様々な解法を拝見したのですが、おおよそ以下のように分類ができると思いました。

自分の最終提出は

・各グラフの合計の辺の数が全然違えばよいのでは？

・各グラフにそれらしい頂点番号をつけてみる

・「あるはずの辺がない」「ないはずの辺がある」これもある確率分布に従う？

を念頭に作られています。

（頂点番号をつけていますが、頂点番号の完全一致を目指すものではなく辺の多いグループと辺の少ないグループを当てることが目標なので、そういう意味ではグループ分けのほうが正しいかも？）

　エラー率が少ない場合(eps<=0.04)では

・グラフが形として全然違えばよいのでは？

・与えられたHにそれらしい頂点番号をつけてみる？

・「あるはずの辺がない」「ないはずの辺がある」をカウントしてみる？

を採用しています。

　エラーがひどい場合は諦めたらよいのでは？（つまりN=4にする）

というのは、最後まで採用するか悩みましたが、最悪ケースでもなんとかあきらめた場合と張り合えるようになったので採用しませんでした。

後悔している点

もっとグラフとしてとらえていれば・・・

　上の解法の紹介の段階でお気づきかもしれませんが、私MON.T+αは今回の問題を対称行列的にしか見ておらず、swapの実装もしっかり行列の行入れ替え・列入れ替えを念頭に実装してしまっています。頂点同士が辺でつながっているという感覚が全くありませんでした。結果、M個のグラフの選び方はPythonのサンプルコードの延長線でしかなく、クリーク（部分完全グラフ？）とやらのアイデアが浮かぶこともありませんでした。そういった解法を拝見した後で自分の解法を見ると、ある意味大きなクリークを埋め込んでいるとも言えるんですが・・・。次回はより広い視点で問題を見つめることで幅広い着想を得たいですね。

もっとM個のグラフについていろいろな場合を試していれば・・・

　これは問題の特徴をもう少し考えておくべきだったと反省しています。

　今回の問題、プログラムが考えるのは、

・M個のグラフを何にするか

・与えられたHがM個のどれから得られたものか

の二点ですが、「M個のグラフをどんな形にするか」を決めた時点で、ある程度取れる得点の限界が決まってしまいます。私は「生成が簡単かつ元のグラフの形を推し量りやすい」という理由で

上のようなグラフを採用してしまいましたが、これはバリエーション豊かなグラフの一部分しか使えていません。順位表といろいろな方の解法を照らし合わせてみると、たとえ各グラフからの生成確率を最も正確に判定しても、暫定テストのスコア限界は20~25Gなのではないかという気がしています（自分の前後あたりまで似た解法の方が多かった気がします）。特にエラーが少ない場合での頂点数が多くなりがちです。

　最終的に「与えられたHがM個のどれから得られたものか」の段階は十分妥当な結果を返しており、実行時間もかなりの余裕があったので、最上位陣のような「元の形を推し量るのに技術を要するが、推し量ることができたらかなり高得点」なグラフに挑戦してみてもよかったかもしれません。

頂点数N、ローカルで最善のものを探していれば・・・

　これはいうほどスコアにおいて致命傷になってるわけではないんですが、シンプルにローカルで試せることはいろいろ試しておくべきだったなと思っています。ローカルで回す分には特に何かを失うわけではないですし。

統計データ

ローカルでのSeed=0,...,99の得点

ローカルでデータを取っていたものの中での最高点を示しています。詳しくはわかりませんが、正答率100%をとれていないケースが20~25ケースほどあります。

Seed	M	eps	Score
0	10	0	250000000
1	76	0.01	100000000
2	87	0.25	10309278
3	48	0.34	8100000
4	31	0.05	62500000
5	32	0.06	58823529
6	80	0.04	66666666
7	51	0.15	23809523
8	93	0.31	6561000
9	47	0.26	14285714
10	72	0.38	119725
11	41	0.36	6561000
12	39	0.28	13698630
13	69	0.04	66666666
14	35	0.16	27777777
15	26	0.15	37037037
16	32	0.4	646108
17	97	0.38	46383
18	83	0.16	17543859
19	75	0.14	20408163
20	58	0.13	25000000
21	57	0.27	11111111
22	70	0.03	66666666
23	63	0.32	7290000
24	17	0.27	26315789
25	67	0.32	7290000
26	91	0.34	1350851
27	75	0.13	21739130
28	45	0.06	40500000
29	88	0.11	21276595
30	64	0	166666666
31	11	0.24	40000000
32	49	0.24	14285714
33	50	0.19	18867924
34	72	0.15	20000000
35	29	0.03	83333333
36	54	0.05	43478260
37	33	0.05	56250000
38	34	0.33	10000000
39	66	0.04	66666666
40	17	0.28	20833333
41	36	0.16	27027027
42	89	0.01	100000000
43	15	0.08	71428571
44	33	0.18	25000000
45	83	0.36	423911
46	96	0.02	100000000
47	92	0.3	7290000
48	30	0.39	2058911
49	27	0.1	45000000
50	30	0.18	27027027
51	48	0.26	13157894
52	82	0.1	25000000
53	18	0.35	12500000
54	58	0.09	34615384
55	14	0.26	32142857
56	49	0	166666666
57	77	0.03	66666666
58	42	0.36	4782969
59	71	0.36	717897
60	92	0.21	12857142
61	14	0.25	37037037
62	98	0.03	66666666
63	11	0.39	10000000
64	20	0.37	10000000
65	13	0.06	90000000
66	77	0.08	27777777
67	83	0.09	25641025
68	17	0.16	47619047
69	84	0.18	15625000
70	99	0.31	4304672
71	100	0.02	100000000
72	54	0.1	30303030
73	97	0.38	46383
74	87	0.38	107752
75	29	0.16	36000000
76	13	0.39	9000000
77	93	0.33	2541865
78	75	0.19	16666666
79	70	0.19	16666666
80	61	0.04	66666666
81	77	0.23	12658227
82	62	0.3	10000000
83	97	0.3	5314410
84	60	0.05	38461538
85	33	0.31	11363636
86	76	0.11	23809523
87	93	0.28	9000000
88	56	0.04	66666666
89	56	0.23	15000000
90	41	0.19	20833333
91	22	0.03	100000000
92	51	0.3	10000000
93	50	0.05	45000000
94	56	0.19	18518518
95	66	0.35	2287679
96	81	0.4	11790
97	26	0.35	10000000
98	32	0.3	11904761
99	88	0.12	20408163

M,epsとNの値

最終提出は各M,epsに対して以下をNとして返すみたいです。

　比較的0.04<eps<0.3付近のNがかなり多く、その部分が弱点っぽいです。これは比較的エラーが起こらないにもかかわらず、M個のグラフとして最終提出の概要で紹介した(A)(B)しか用いていないからだと思われます。

　また、eps>0.04では二つの計算式のmaxをとっているために黄色のラインが途中で曲がっているのが読み取れます。

おわりに

　コンテスト期間外にいろいろ試したことや少しコンテスト経験を積んできたことが功を奏してか、前回参加したAHC014に続き、なかなか好順位につくことができたと感じています。今後も定期的に参加してステップアップしていきたいです。（願わくばまた長期コンテストを・・・）

　今回の問題も難しい問題で、約一週間の間いろいろな試行錯誤を繰り返して楽しめました。コンテスト運営に携わっていた方々、大変楽しい時間をありがとうございました。

【Postmortem】AtCoder AHC014

画像は公式Visualizerからお借りしています(Seed=0)

はじめに

本日は、AtCoderにて9/17~10/1に行われましたAHC014の参加記録を記していきます。今回は最初に軽く最終提出を紹介します。また、最終提出に至るまでいろいろな提出を行ったのでそれらを日記風に時系列順にまとめて紹介をする流れになります。解説、検討というよりはどちらかというと日記です。

　なお、過去の自分の提出を見て振り返りながら書いているので、心情描写についてコードを書いた当時の心情と一致していない可能性もあります。

最終提出のプログラム

・Go言語

・評価値による貪欲

・評価値に多少の乱数を入れて時間いっぱい貪欲をやり直す

システムテスト前　50ケース最高記録　53.0M(58位)

システムテスト後　50ケースあたり　　52.4M(60位)

でした

コンテスト日記

9/17~9/20 コンテスト参加検討期

　今回は開催期間が2週間もあり、休日も多いので時間が取れるのではないか、と思い参加登録。このときはやる気十分だった。

　しかし、問題文を見るや否や、やっぱりやめておくか、となった。恥ずかしい話、最近はAtCoderのコンテストに出ていなかったので問題文のN,M,p,iや得点の計算式を受け入れることができなかったのである。

　以降、しばらく自分のいない順位表を眺めるだけであった。

　最初の週末を何も提出することなく過ごした自分に、天啓が降りる。それは、自明解である(気づくの遅くないか？)。入力を無視して０を出力すると、なんとACだというのだ。これを何の気なしに出してみると14M改善した(0M→14M)。斯くして正の得点を得た私は、抜け出せないコンテストの沼に足を突っ込んでしまったのである。

9/21~9/22基本方針確定期

　自明解の発見は14Mもの改善をもたらしたが、順位はあまり芳しくなかった。自分のプログラムで特に違和感を感じたのは、まだ格子上に点が置けるのに置かない点である。この問題を解消するため、各座標に対し、その場所に新たに点を置けるかどうかを返す関数を実装することにした。(正確にはその点を起点として作ることのできる四角形を列挙する関数)

　これが、書くのが遅い私にとっては難所となった。なおこれを書き終えたところであまり実用的な実行速度ではなかったのだが、このときの私はまだ何も知らなかった。

(少し実装の紹介)

判定の仕組みは非常に簡単である。スタートの座標から1マスずつ一直線に移動しながら、そこに点があるか、すでに間に線が引かれたかを確認する。線があればその段階で四角形は作れないことがわかるので中断する。すでに点がある座標に到着したら、時計回りに90度回転し、1マスずつ進んでゆく。これを繰り返し、スタートの座標に無事もどることができるか見れば良い。図付きの説明は最後の「よくありそうな質問」で。

この関数を実装し、置くことが可能な点を左下から探して見つけ次第おいていくことができるようになったのはn時間の実装作業の後だった。単純だが、スコアは自明解の比ではない。これを提出することにより・・・と思ったら提出していなかった。あまりに遅かったようで、ビット演算での処理が今後行えるよう点と線の情報をbitboardにしてから提出していた。(盤の情報をbitboardにするのはマラソンの問題で大いに役立つテクニックなので、もし知らなかった方がいれば一度調べてみてほしい)これにより16.5Mの改善(14.0M→30.5M)に成功する。

　このとき、上で述べていた判定の関数が遅かったので二手先などは考えず「この座標に点を置くこと亅に対して得点をつけることにした。すなわち貪欲である。この方針は最後まで貫くことになる。

　で、さっそくの手詰まりである。手動でテストケースをプレイしていても何もわからない。中心から遠いところに点がある方がいいのでは？と思い始めたころに上位の人が共有しているVisualizerを確認してみると、なんとめちゃくちゃ点が埋まっているではないか。

　したがって、「小さい長方形から優先して作る」というのが続いての目標となった。これは得点として長方形の外周の長さ×-1を採用することで完成した。申し訳程度に同じ大きさの長方形なら中心から遠いのほうを採用した。(30.5M→32.0M)

　ここで、一番小さい斜めの長方形の外周が8と計算されていたのでそれも斜めでない場合と同じ4となるように計算方法を変えて再提出した(32.0M→33.9M)

また実行時間2sと勘違いしていたので5sに変更(33.9M→34.0M)

（ランダム要素がないのに微増したということは一部のケースで2sでは間に合わず切り上げていたということに・・・）

さすがに実行速度が遅すぎてこれはやっていられない、と思い就寝。天井を見ながら「コンテストが終わるまでに40Mに到達する」を目標に掲げる。翌日は最低限の高速化に努めた。一番重かったテストケースがおおよそ3倍速に。(2300ms→800ms)

(点と辺のbitboardを上方向、右上方向、右方向、右下方向でもつことで長方形の大きさにかかわらず同じ時間で長方形が作れるか判定できるようになりました。このあたりの話は最後の「よくありそうな質問」で。)

時間に余裕ができたのでがちゃがちゃ評価関数をいじってみたけどほとんど変わらなかった。多分あまり本質的な部分ではなかった。(34.0M→34.2M)

時間に余裕ができたので、評価関数に若干の乱数を入れて時間いっぱいやり直すことにするとこれはかなり改善した(34.2M→37.2M)。とはいえ、一番重いケースだと6回くらいしか試せていないので乱数次第でかなり得点がぶれるようだ。乱数の取りうる範囲を狭めてみると多少得点は変わったが(37.2M→37.4M)、よくなったのかどうかわからなかった。

で、またしても手詰まりである。上位の人が共有しているVisualizerを確認してみる。よく見ると、小さい長方形が市松模様のように並んでいるではないか。こうして、「市松模様の形になるようにおける場合は特に優先するのがよいのではないか」という天啓を得る。雑な実装、より適切な実装、市松模様判定の高速化の段階を経て得点が伸びる。(37.4M→38.3M→40.3M→40.8M)

（実は作ろうとしている長方形で各頂点で辺をもう1マス伸ばしたところにすでに線が引かれているかでわかるのである。

一本でもひかれていれば、市松模様が繋がる。）

斯くして布団から天井を見て掲げた40Mの目標を早くも達成するのであった。

9/23~9/27 現実逃避期

　思いつくことを実装しきって40Mに到達したことで、非常に高い満足感を得るとともに、今の自分ではもうこれ以上は伸ばせないだろうという思いが湧き上がる。最終結果を知る今から見ればこの方針のまま少なくともあと13Mも改善できる余地があるのだが、一度こういう気持ちになってしまうと本当に何も思いつかないのでどうしようもないのである。

　うーん、AHCやめるかぁ・・・。

　この期間中何もしなかったわけではない。ローカルで50ケース程度の得点をとってみた。するとMが小さい（すなわち初期状態に置かれている点が少ない）場合は小さい長方形を優先的に選んだことでむしろ得点が悪化していることに気づく。おそらく小さい長方形を連鎖的にうまく作ることができないのだろう。よってMが小さいケースについては長方形の大きさによる評価値の影響を小さくし、苦し紛れの改善に成功する(40.8M→41.2M)。成功したのか？乱数の運程度の誤差ではないのか？とも思われるが、とりあえず成功したことにしないとこの期間の進捗はなくなってしまうのでこれは成功したことにする。

9/28　運命の日

　コンテストも終わりが近づいている。なんか順位もむちゃくちゃ下がっている。「ああ、やはり対戦botを作るタイプのコンテストのほうが得意なのかなあ。こういった得点最大化タイプのコンテストだと、自分のプログラムの粗削り感があらわれてしまうんだよなあ。」と思いながら試行錯誤していたところの出来事である。22日から変わらず市松模様の理想をベースに評価を加えていたところ、3M近く改善したのだ(41.2M→44.0M)。やはり市松模様が正解だと思うとともに久しぶりの大幅改善でやる気がよみがえってくる。

　また、ローカルテストで、Nが小さいときは選択肢が少ないため何度やり直してもほとんど決まった結果が出ていた。そのため、Nが小さいときは乱数の影響を多くしていろいろなパターンが出るのを期待した。(44.0M→44.8M)

　なぜ、40Mで止まっていた最高点を大幅に塗り替えられたのか。おそらくこれを読んでいる人（そもそもいるのだろうか）のほとんどはこの改善が気になることだろう。実際、この改善は自分のモチベーションとしても40Mから50Mへの要素としても重要な部分であり、おそらくほかにこれを実装している人はいないだろう。が、残念ながら語ることができない。なぜならば、「バグ」だったからである。私はこの時追加したものがバグでどのような評価を与えているかわかっていないからである。この時の私はバグには気づいていなかったので自分の発想が正しかったのだと思い込んでいる。一応、バグによる評価値の加減は最後の「よくありそうな質問」で述べている。

9/29~9/30 高速化期

　いよいよもう方針転換はできないころである。高速化して試せる回数を増やすほかないかと思う頃にまたしても自分に天啓が降りる。それは、有効な手を調べる際のループ回数の減少による高速化である。

アイデアは以下のとおりである。

・初期盤面ではN*N個の各座標から8方向に長方形を作ることができるか調べ、評価

・調べた結果を保存する

・最良の点を決定した後、次にその点を使って長方形を作ることができるかもしれない座標を、暫定的に作ることができる場所として調べた結果に追加する

・調べた結果を参照して、長方形を作ることができる場所が本当に長方形を作ることができるか調べ、評価

・調べた結果を保存する

・最良の点を決定した後、次にその点を使って長方形を作ることができるかもしれない座標を、暫定的に作ることができる場所として調べた結果に追加する

以下繰り返し

（この調べた結果もbitを使って保存するとかなり速かった）

これにより実行速度が大幅に改善した（5倍速くらい？）。これを提出することで数日の停滞を巻き返してゆく。(44.8M→46.2M→47.2M→49.4M)

これをきっかけとして、ほかの場所もいろいろと無駄があるのではないかという気がして、次々と高速化してゆく。この間、問題となっていたバグ部分を高速化しようとした結果さらに違うバグになっているのだが、なぜか気づかなかった。

これに評価値の調整を行い51.0Mまで到達する。

　また、高速化とセットで、ちょっと乱数の倍率を変更してみる。高速化のおかげで回数が稼げるので、前半は乱数要素少なめに貪欲を行ってもらい、貪欲のやり直し回数を重ねるごとに乱数を大きくすることで評価関数の型にはまりすぎて出にくかった結果にも多少到達できるようになった。仮に後半部分で良い結果が出なくても、前半部分で十分高得点が期待できるので良い方法に感じた。

　また、ついにバグに気づく。バグを取り除いてみる。ローカルで3M下がる。バグを戻してみる。ローカルで3M上がる。よって、バグを許容する。さらに、バグを改変してスコアの安定化に成功する。

乱数の運に左右されるので多少上下しつつ、最高53.0Mに到達する。

10/1 お祈り期

　もはや簡単に高速化できる場所はなくなった。実装の遅さに定評のある私は、一日にかけるコード量など微々たるものである（ちなみに短期コンテストにめったに出ない理由もそれである。逃げていても上達しないとわかってはいるが・・・）。雑なものを書いてそれが最終提出になってしまっては大事故である。したがって最終日は順位表の礼拝に努め、システムテストの得点の向上を祈った。

まとめ

　AHCに参加したのは久しぶり（おそらくAHC003以来？）になりますが、まさか黄色パフォーマンスに到達でき、レートも今回で水色になれるとは思っていませんでした。地道に実装力が上がっているということなんでしょうか・・・？長らく間が空いてしまいましたが、次回以降のAHCも時間を作って取り組んでみたいと思いました。

　（短期コンテストは苦手意識があるのでぜひ長期コンテストを・・・）

よくありそうな質問

・結局盤面ってどのように記録したの？

点、辺をそれぞれ上方向、右上方向、右方向、右下方向の四種類に分けて盤面を記録しました。以下の3*3の盤面での点の取り方を紹介します。辺は点の例の時に出てくる矢印に沿って同じように記録します

上方向は左の矢印から順に100,001,111（2進数）となります。

右上方向は上から順に001,000,100,110,100（2進数）となります。

右方向は上から順に101,100,110（2進数）となります。

右下方向は100,100,101,010,000（2進数）となります。

この形で持っておくことでの恩恵については詳細は省きますが、長方形が作れるかってどう判定したの？で若干触れます

・長方形が作れるかってどう判定したの？

上でも使用した3*3の盤面を使用して紹介します。

上のようにまず新しく起きたい場所からある方向に進みます。すでに点がある座標に到着したら、時計回りに90度回転し、また1マスずつ進んでいきます。これを繰り返し、スタートの座標に無事もどることができるか見れば良いです。上の例では戻ってきたので作ることができます。また、上の例の座標スタートでは、ほかの角度から始めるともどってこれません。

別の場所を起点にして何個か失敗パターンを載せておきます。

この次にぶつかる点までの距離は、一つ上の項目「結局盤面ってどのように記録したの？」で紹介したbitboardでは、1になっている位二つの間の距離を見ればよいです。このときbit演算を用いることであまり長さに影響なく高速に求めることができます。間に線がすでにあるかどうかについても同様に高速に求めることができます

・一応バグの部分教えて

一応、どんな値が加算されているかはコードを読んでわかっているので部分的に紹介しておきます。

「赤の四角を作る」という行動に対する評価値を考えるとき、緑の4辺にまだ一本も線が引かれていない場合、黄色の4頂点でまだおかれていない点の数だけ減点する。というものです。これを赤緑黄色の位置を90度ずつ回し計四回考えます。座標がずれた結果上のようなおかしなことになったのですが、上の赤の長方形と黄色のエリアの関連性が結果としてきれいな市松模様を構築することにつながったのだと思います。

・なんで焼かないの？

貪欲を時間いっぱいやり直すという方針をとったのは、当初、置くことができる座標を調べるのが非常に遅く、1回解を出すのに500msはかかるだろうと踏んでいたからです。本当は高速になり始めたころに焼きなましを考えるべきだったと思いますが、焼きなましのための一部破壊ができるようなデータ構造になっていなかったので、実装が間に合わないと判断しました。（嘘である。実行速度が遅かったのも理由だが、実はmontplusaは焼きなましの方法を知らないのでコンテストで焼きなませたことがないのである。そろそろ学ぶべきか・・・）

・天啓、多すぎでは？

天啓を得られるか、天啓が降りてくるかは運にもよるので今回は運がよかったと思いますが、より天啓を得やすくするためにできることもあります。（なんかスピリチュアルに聞こえますが違います）

・手動で試してみる（今回は手動で試してもあまり良い発想が得られませんでした）

・twitterで共有されていたVisualizerを見る

・トイレ、風呂、食卓、公共交通機関、外出先などあらゆる場所で問題を思い出してみる

このほか他コンテストの経験が活きる、他コンテストの解説記事が活きるなど、様々なきっかけで天啓を得ることができるので、天啓が得られそうなことをしてみるといいかもしれません。

（そもそも、私の「天啓を得る」の水準が低く、実は小発見程度である可能性もあります）

【Postmortem】Green Circle

※画像は公式Visualizerよりお借りしています

はじめに

　本日は6/16 - 6/27の期間にCodinGameで開催されたコンテスト「Green Circle」についての記事になります。全文に目を通してられない方は上目次だけでもぜひ見ていってください。

　CodinGameコンテストに参加するのは今回で3回目になりますが、結果5位/1758人(Legend内 5位/56人)でした。まだ夢の可能性を疑っています。

　いまだ用語等よくわかっておらずところどころ間違っていたりすると思いますが、発見された方は優しくご指摘いただけると嬉しいです。（かなり走り書きなのでいろいろ誤字脱字あるかもです。抜けてる大事な情報があれば随時加筆します）

　前回書いたSpring Challenge 2022 のPostmortemはこちら

montplusa.hatenablog.com

ゲーム概要

　ゲームルールにつきましては、おそらくここにたどり着いている方のほとんどが既知だと思いますので割愛します。雑にいえばアプリケーションを早く5個リリースするゲームです。

最終提出AIの詳細（言語、探索、戦術）

言語:Go言語

　今回コンテストに提出したAIはGo言語を使用したものになります。特にこの言語ならではのことをしたわけではないので、あまり関係はないです。

探索:1サイクル分の（ほぼ）全探索

　今回のゲームはカードをDrawするという操作が入ると何が出てくるかわからず一気にシミュレーションの価値が下がってしまうので、相手に手番が渡るまでにどんなパターンがあるかを調べ、それぞれのパターンについて、相手に手番を渡すタイミングで、どんな山札・捨て札になっているか、何がリリースされているかなどを見て得点化することにしました。それに加え、最大で3ターン目まではif文で分岐した「定石」を見て動くことがあります。（実はこれでLegendリーグでの後手の勝率が大きく上がりました。）

ほぼ全探索というのは、MOVE Phaseから考えたときは一番パターン数が膨れ上がりがちなので、この時だけRELEASEの選択肢をよさげな一つのみにしています。（たぶん今パターン数見たら全部見ても何の問題もなかった気がします）

　1サイクル分の全探索には貪欲であるというところにかなり明確な弱点があります。このターンは問題ないからと言ってリファクタリングに駆け込むと、次のターンはAdminで逆に負債を抱えることもありますし、無理してターン中にアプリケーションをリリースして山札・捨て札が負債だらけになることもあります。ここは、将来性のある状態に加点する必要があります。なお将来性へのだいたいの加点は5RELEASE目に近づくほどに弱くしていき、無駄に将来性を考えなくてよいようにしています。

以下、AIの概要です。

・ボーナスカードを4枚AUTOMATEDに入れ、手札と絡めて最後のRELEASE

AUTOMATEDが終わってから1RELEASE目ではLegendでは間に合わないので3つボーナスカードを入れたあたりからRELEASE数に応じて加点します。この戦術のためBONUSカード4枚以上（予備を考え5枚）は手札、山札、捨て札、AUTOMATEDにあってほしいところです。また、そのためCONTINUOUS_INTEGRATIONとBONUSをセットで同時に引いていきたいところです。

簡易的な引きやすさの指標として山札や手札、捨て札のすべてから二枚引いたらCONTINUOUS_INTEGRATIONとBONUSになる確率を使ったり、厳密に次のターン引いた時にそれぞれの出てくる枚数の期待値を求めたりしました。（ランダムに何度もドローしてみるのではなく数学的に四則演算で求めるのでかなり高速なうえに、なんか妥当っぽい値になります）

・初手2に行くか5に行くか問題

自分のAIは

・先手なら2に行くタイプ

・後手なら5に行くタイプ、無理なら2に行く

となっています。個人的には最初に5に行ったほうが安定してBONUSカードをAUTOMATEDに入れる手順があると思っていますが、1ターン全探索と相性が良いのは2に行く場合だと思っています。後手だと5としていますが、たいてい先手は2,5のどちらかに行くので、選ばれなかったほうに行くことになります。後手で5に行く際は一度Adminを通過するまでは「定石」を片手に隣で手を引っ張ってやることで、山札からどんな引きをしたとしてもたった一枚の最強カードCONTINUOUS_INTEGRATIONをAdminで手放さないようにします。

・移動量に応じては中程度の減点

いくらCONTINUOUS_INTEGRATIONが欲しいからと言って2ターンごとに回られては負債もたまり他の有益カードも減り困ります。かといって負債に大きなペナルティを与えるとすぐにリファクタリングルームに駆け込む開発チームの出来上がりですので、移動にペナルティを与えます。移動を抑えることは将来Adminを通らなければいけない回数を減らすことにつながります。

諸々の小細工

上だけだと他の人と差がつけられないため、順位を上げるためにいろいろと細工しました。その一部を簡単に書いておきます。

・adminを通過すると少し加点

基本的にadminを通ると手持ち札の加点部分は少なくなりがちなので、こうすると、adminを通ってもあまり痛くない場合にREFACTORINGルームまで粘らずに通過します。

・REFACTORINGルームにいるとき、CONTINUOUS_INTEGRATIONの引きやすさといった加点は小さめにする

そんなに次引きやすいのなら、REFACTORINGに止まらずこのターンのうちにadminを通っておいてください。

・後手ならは相手の2マス先にいると加点(特に、2マス先が5,6の場合)

前提として、後手は（少なくとも自分のAIは）弱いです。特に最上位陣の先手にはなかなか勝てません。そこで、突然5,6に顔を出すとadminでの予想外な負債増加や有用カード紛失などを誘発できます。きっちり組み立てている格上ほど効果があり、システムテストではそれなりに貢献できている感じでした。ちなみにこの要素が少し強めに出ているので先手と後手は得意な相手がかなり違います。

・各appのRELEASEに必要な各スキルについて、adminを通らずに取りに行ける位置のスキルなら加点、このときもう一方のスキルが山札にあるならその引きやすさによって加点量を大きくする

各appをみて加点していくのでいろいろなappに使えるスキルについては多重に加点することになります。これは現在のリリース数やAUTOMATEDのBONUSに応じて加点の強さを変えると5リリース目の見通しが良くなります。相手について考え減点すると5リリース目がしづらくなります。

・各appのRELEASEに必要な各スキルについて、次ターン山札からの引きやすさによって加点

この加点量は小さいです。まれに勝敗が変わるくらいだと思います

・（3つほどRELEASEを行うころ）今いる場所の番号が小さいほど加点

これは、5リリース目のスキルを取りに行く際にadminを通らずに目的の場所へ行ける可能性を上げるためのテクニックです。少し先に陣取っているので相手の邪魔にも多少なるかもしれません

・Training、Codingのスキル仕様を変更

ドロー枚数が山札の枚数以上の場合に山札が全部手に入る劣化スキルに変更

TrainingやCodingは確実な部分だけを適用しました。ランダムで引くとかなり負けやすくなります

ちなみにですが、これを一気に実装してもアンバランスなものができてしまいますので、料理のように少しずつfloat64を足して手作業でなじませてからまた新しいfloat64を追加します。（コンテスト終盤は小細工を思いついては実装し、整えてからまた新しい小細工を入れています）

サブミットを繰り返して戦績を見るのも有効です。

おわりに

　ここまで読んでくださった方、ありがとうございます。今回は、Goldボスで苦戦していた時に考えた小細工がLegendでも効果を発揮し、Legendでさらに進化させられたのでとても満足しています。また次回が楽しみです。

【Postmortem】Spring Challenge 2022

※画像は公式Visualizerよりお借りしました

はじめに

　何らかのコンテストへの参加はおよそ半年ぶりになります。本日は4/21 - 5/2の期間にCodinGameで開催されたコンテスト「Spring Challenge 2022」についての記事になります。全文に目を通してられない方は上の目次だけでもぜひ見ていってください。

　CodinGameコンテストに参加するのは今回が2回目だったのですが、前回に続きLegendに到達することができ、結果273位/7695人(Legend内 273位/390人)でした。

　いまだ用語がよくわかっておらずところどころ間違っていたりすると思いますが、発見された方は優しくご指摘いただけると嬉しいです。

　前回書いたHTTF for Youth+ のPostmortemはこちら

ゲーム概要

　ゲームルールにつきましては、おそらくここにたどり着いている方のほとんどが既知だと思いますので割愛します。雑にいえばモンスターを敵陣地に侵入させライフを削るゲームです。

最終提出AIの詳細（戦術、アルゴリズム）

言語:Go言語

　今回コンテストに提出したAIはSpringChallenge2021に続きGo言語を使用したものになります。ただ、今回提出したのは探索0なのであまり実行速度は気にしなくてよかったかも・・・。一番触れていてなじみのあるPython3で提出してもよかったかもしれません。

アルゴリズム:ルールベース

　CodinGameのbot programmingでは必ずと言っていいほどビームサーチによる探索を行っていたのですが、ゲームの不完全さやマルチエージェントであることなどが原因で難航し、最終提出はif文による分岐だらけのルールベースのプログラムになりました。（実は、ビームサーチのものが作りたくて、最初の週末が終わってから月～金の間はコードは書かず頭の中で評価関数のアイデアを出していました。自分の中ではそれなりによさそうなものが頭の中にできていたのですが、土曜日に作ってみると無茶苦茶弱かったのでルールベースを考えることにしました。結果評価関数含めほとんどが粗大ごみになりましたので、以下はごみにならなかった方のプログラムの話になります。）

以下、AIの概要です。

・DEFENDER、SUPPORTER、ATTACKERの3人

この3役職はそれぞれidが0,1,2(red側なら3,4,5)のheroがこの順で担当することになっています。それぞれのheroはほかの味方heroの状況をまったく知らされていないのでどのような状況になっても役割のスイッチは行なわれません。連携×

・マナを一定までためると攻撃モード、マナが減ったら収集モード

攻撃モードに切り替わる基準は250です。後半戦になるとこの基準値は下がり、積極的に攻撃モードに変わります。

一方、収集モードに切り替わる基準は50で、これは固定です。

・それぞれの配置は完全に持ち場制

各heroは味方のheroの存在を知らないので、それぞれ一人で戦っていると錯覚しています（その割に敵heroやmonsterの存在は知ってるらしい）。したがって、戦闘を繰り広げるにあたって、あらかじめ各ヒーローはどこを待機場所とするか、どのエリアの敵が自分の管轄かを明確に定められています。味方のheroがキャパオーバーであったとしても、それを理由にサポートに入ることは絶対になく、結果、非常に脆いbotになりました。下にみんなへ伝えた勤務担当を載せておきます。

DEFENDERくん「別マニュアル？( ;∀;)(if文約30個)」（一人体を張らせてしまってごめんね・・・）

SUPPORTERくん「え、担当ここだけ？( ･ิω･ิ)」（彼は積極的にコントロールすることで持ち場を離れないこともあって隅で一人ぼっちなことが多いです）

ATTACKERくん「別マニュアル？？( ;∀;)(if文約60個)」（攻撃が多彩なのはうれしいけれど、パスは取りに行こうね）

諸々の小細工

上だけだと他のルールベースの人と差がつけられない(むしろ連携等ないので弱い)ため、ボリューム層からLegend昇格できるまで順位を上げるためにいろいろと細工しました。その一部を簡単に書いておきます。

・スポーン後control,windされていないmonsterを見つけたら、対称な位置にmonsterがいるとして登録

若干見通しが良くなりますが、あまり有効に使っているところは見ません。

・対象を攻撃する際、複数巻き込めるなら巻き込む

なんとなくマナ回収効率が良くなったのが実感できます。

（Last battlesで対応しているセリフ：「両取り」）

・ATTACKERはshieldをかけたmonsterを定期的に送り込む

一人で敵の守備を破るにはshield,control,wind全てを使うのがよいと考えました。上で述べたshieldの使い方ですが、敵が複数Base前にいてWIND合戦だけではそもそも5000以内に入れさせてもらえない場合に有効でした。リプレイで見ると実装前に比べて攻撃的に見えました。

（Last battlesで対応しているセリフ：ATTACKERの「突破口にする」）

・DEFENDERの自己Shieldは敵が一度でもControlしてきた場合のみ

shieldはそれだけでマナを10消費するので無駄遣いしたくないところです。ただし、結局DEFENDERは一人なので、shieldを張ったとしても張りかえの時にcontrolされたりshield中にmonsterがWINDで飛び越えてきたりして簡単に負けてしまいます。

（Last battlesで対応しているセリフ：DEFENDERの「あの人、怖い」）

・敵3人を自分のbase周りで検知したらbase外からWINDでライフを削る戦法（いわゆるロマン砲）に警戒

ロマン砲に勘付いたら3人をコントロールし続け時間を稼ぎます。ただしLegend昇格のための雑対応なのでしっかりとしたロマン砲にはかないません。

（Last battlesで対応しているセリフ：ATTACKERの「時間ないぞ」「ごりおし」「ボールほしい」）

（Last battlesで対応しているセリフ：DEFENDERの「様子が変」）

・敵2人を自分のbase周りで検知したら攻撃モードに変更

こちらのDEFENDERは一人なので瞬殺されます。ここは一縷の希望に賭けてATACCKERが敵baseで1on1を申し込みます。

・monsterが多すぎる場合は森へ捨てる

敵がcontrolでmonsterを集めることで集中砲火を狙う場合、DEFENDER1人だけでは押し負けてしまいます。この場合は近くの森にWINDでポイ捨てすることにしています。monsterはマナの源でもあるので、辛くもないのにむやみやたらに捨てさせると逆に弱くなります。毎回できるような配置とは限らないので、これも特定の戦法に対する全敗回避策です。

（Last battlesで対応しているセリフ：DEFENDERの「捨てたい」）

・ATTACKERのWINDは確実に前に進めたい

攻撃をする際のWINDは、敵にとってmonsterを飛ばされるとまずい場合、ほぼ確実に逆向きのWINDによって打ち消されてしまいます。それとは違い、敵の位置の都合上相殺されない攻撃ができるだろう場合は少しWINDを緩い状況で放ちます。なお、たいていの場合その次のターンにWINDが返ってくるのでいうほど関係ないです。

（Last battlesで対応しているセリフ：ATTACKERの「フリーで打てそう」）

おわりに

　ここまで読んでくださった方、ありがとうございます。いろいろと工夫してみたつもりでしたが、ほかの方々のPostmortemを見ると「あ、そんな考え方があるのか」と驚かされました。

　CodinGameのbot programmingコンテストは比較的期間内の言及がしやすく、みんなで同時に取り組んでいる感が強いのでとても楽しめました。また次のコンテストが楽しみです。（次回いつなんだろう・・・）

おまけ：

【Postmortem】HACK TO THE FUTURE for Youth+

画像は公式Visualizerよりお借りしています

はじめに

　投稿はおよそ半年ぶりになります。コンテストに参加すること自体、かなり久しぶりでした。この記事は10/10にAtCoderで行われました、FIF様主催の「HACK TO THE FUTURE for Youth+」の記事になります。コンテストの詳細はこちら

　今回のコンテストはチームmonk1としてstatiolakeさんとともに参加しました。長期間のブランクで実装速度が遅くなっていたところstatiolakeさんに助けられまして、最終順位は本戦ページのチーム順位表で30位でした。個人的にはかなりうまくできたと感じているので、自身の備忘録も兼ねて書きます。

解法選び

　今回のコンテストでは、短いコンテスト時間内でどれだけの記録を出せるかに拘って取り組んでみました。コンテストとはそもそもそういうものなのでは？と思われたかもしれませんが、今回のコンテストではコンテスト時間が4時間しかなく、元々コーディング速度が致命的に遅い私ではたとえ筋が悪くても実装が簡単な方が好順位を取りやすいことが多いため解法があまり適切でなかったりします。自分の成長のためには適切な解法で取り組みたいところですが、今回はコンテスト時間内の記録に挑戦しました。

　今回の問題を見た印象ですが、一言でいうと「プログラム完成できなそう」という感じでした。私は考察のため最初の30分ほどはA問題を手動で試しつつ考えていましたが、思いついたのはどれも4時間のプログラムには落とし込めないような解法ばかりでした。（上位の方が普通に提出できている解法は私にはとても時間がかかるものばかりで間に合わないのです）

　そこで、解法を選ぶ前にチームとして前提となる方針を固めました。以下の通りです。

・問題Bと問題Cのプログラムはほとんど同じものを使用することにし、二人で一つのプログラムを書く

・試せる解法は1~2つくらい

上の方針がなければ実装が絶望的でした。問題が難しく、それなりな解を出すのがひとまずの目標でした。

　そのうえで、各解法についてどのくらいかかるかを考えました。

・ブロックの置き方でビームサーチ（4時間ではベースが完成しない。）

・ブロックで各印を覆いきってから最小全域木にする（4時間では覆うところまでかな・・・。効率の良い覆い方も見つからず、最小全域木にもならないかも）

問題が難しくこのままではどの解法でも完成させられない・・・。statiolakeさんには入力を受け取った順に印を1*1のミノでつなげるプログラム（さすがにこれを提出するつもりはなかった）を書いていただきながら悩むこと約1時間、まあまあな解法で実装がかなり簡単なものを思いつき、それを実装することにしました。（その解法は「最終提出プログラムの戦術」参照）

最終提出プログラムの戦術

　最終提出プログラムの戦術とは銘打っていますが、最終提出とつけるほど提出はありません。ソースコードの変遷はかなり一本道でした。「解法選び」の部分で書きましたが、4時間のうちに書くことのできる、非常にお手軽な解法となっています。

　戦術はかなり明確にパート分けされています。具体的には

1. 1*1で各点をできるだけ低コストになるようにつなぐ（最善ではなくそれなりくらいのコストで。A問題26万点程度で、出力例にあった1*1を使ったつなげ方では30万点程度だったことを考えるとそれなりの無駄があります）

2. 1*1以外のポリオミノをランダムに埋め込んで重なった1*1のポリオミノを取り除くことでコストの削減を狙う

という戦術です。1については私は4時間では実装できないのですがここはチーム戦ということでチームメイトを頼り、私はその1*1の置き方が与えられた仮定の下で2の関数を作成していました。

　ということで1の説明は私はできる自信がないので割愛いたしまして、2の説明をします。ポリオミノを埋め込んで1*1を取り除くというものについて下に図を載せておきます。

（1*1の接続例）

（置いてみるパターン1）

上のパターン1ではコスト3を一つ置くことによりコスト1を4つ取り除いています。

（置いてみるパターン2）

上のパターン1ではコスト2を一つ置くことによりコスト1を8つ取り除いています。

プログラムは10000パターンランダムにおいてみて最も節約できたものを置きます。そしてかぶる1*1ポリオミノを取り除きます。取り除き方から、無駄は多いですが必ず全印がつながっていることがわかります。一個置き換えただけでは大差ないので、置き換えた後の盤面にまた先ほどの操作をしてみます。1*1以外のポリオミノと重ならない置き方のみ試します。たいていは50個も置き換えればもう節約できなくなります。

　そうすると意外にもきれいに置いてくれています。

（２を行う前）

（2を行った後）

(ん？一番右の列と一番下の行が全く置き換わっていない・・・？バグでした。コンテスト中に気づきたかった。)

　あとは局所解な可能性があるので盤面を1で得たものにもどしてやりなおすということを時間の限り行うのみで、最終的に一番よくできた結果を出力します。

　2の部分の実装はかなり簡単な方で、私でも間に合わせることができました。（もし気になった方がいればmontplusaまたはstatiolakeさんの最終提出からoptimize()という関数を参照してね）

　時間に余裕があれば、最後に不要な1*1ミノも取り除ければもう少しスコアが上がります(コンテストには間に合いませんでしたが、statiolakeさんが実装してくれました)

おわりに

　今回のコンテストのような短期間のコンテストには苦手意識を持っていたのですが、非常に楽しく取り組めました。特に、今回は50*50のマスと比較的エリアが小さく人間でも楽しめるパズルゲームだったこともあり、プログラムの結果と人間の結果が比較できたりととても面白かったです。

　今回チームを組んでくれた方、ともに4時間競った他チームの方々、今回のコンテストを運営してくれた方々、本当にありがとうございました。

【検討】Spring Challenge 2021

※このページのゲーム画像は公式Visualizerよりお借りしています。

目次

はじめに

　先ほどPostmortemとして投稿したSpring Challenge 2021についてですが、そのゲーム性や、私のAI・戦術の詳細についてもう少し検討したいと思います。この検討内容は断定口調で書くことも多いですが個人の感想ですので、「これは間違っているのではないか」というようなところもあると思います。私の成長になりますのでそういった箇所があれば、連絡お待ちしてます。

　以下文体が敬体ではなくなりますが、今回は私の脳内の自問自答の再現ということでご理解のほどお願いいたします。

Spring Challenge 2021のPostmortemはこちら

 Spring Challenge 2021のゲーム性

　ここでは、Spring Challenge 2021のゲーム性について考える。ここで言いたいゲーム性というのは、ゲームのルールではなく、その性質のことである。一応、このゲーム性の検討によって、ゲームから少し抽象化した性質を抽出して似た性質をもつ別のゲームで利用できるようになりたいと考えている。

基本は資源（sun）をいかに相手より多く集めるかを競うゲーム

　今回のゲームでは、あらゆる行動をするたびにsunを消費する。このため

自分が得られるsunの量　≒　自分の行動能力

となる。また、最終的にsun3ポイントがscore1ポイントに換算されるので、sunの収入は最終スコアに直結し、各AIがいかに相手より多くsunを得られるかがカギとなる。

　これは参加者皆が同意するところであるろうけれども、このゲームはsunはそのまま保持しているよりは木にしておいたほうが将来的なsunが多くなる。したがって、ゲーム終盤か、次のターンにどうしてもコストのかかる行動がしたいということでもない限りはsunはあまり保持しておく利点がない。木はいわば配当がとてつもなく大きい株である。一方で、木が多くなるほどGROWの効率が悪くなるので、いずれは刈り取り、場合によってまた新しく種をまくことになる。

　CodinGameで私が取り組んだBot Programmingゲームはそれほど多くないのだが、この資源システムは私の取り組んだ中ではCodinGameのCode Royaleというゲームに少し近そうである。このゲームについて軽く触れると、資源地を建設し、その資源から兵を練兵場で生産し、相手の体力を減らすというゲームである。

相手との影響が少なそうだがそこに順位の差が現れるゲーム

　Wood2,Wood1,Bronzeと、ゲームのルールを一通り体験してみると、まるでOptimizationのような感じを受けた。Woodではそもそも相手が関係するルールがあまり適用されていなかったのでもちろんだが、Bronzeでもコンテスト開始当初は影の効果は自分自身の収入のOptimizationとして考慮されることがほとんどだった。コンテスト中よく見られた、とびとびのところにSEEDするというような戦術などがこれに含まれる。

　自分のOptimizationとして主に使われていたというのは、このゲームはCellがあるものの、既存の駒（木）を隣接するマスに移動させるといった行動は存在せず（逆にあったらホラーなのだが）、一度植えた木はCOMPLETEするまで消せないので相手の木のあるCellに日光を当てさせないという戦術は、ルールを理解した初期では成功させづらいからである。

　しかしこのゲームは比較的Sunを尺度に何が良い行動かをヒューリスティックで当てやすいために、いざコンテスト期間中盤となると、敵を無視したOptimizationを用いたAIは大量に膨れ上がり、敵を無視したOptimizationだけでは、大群に飲まれてしまう。結果、ゲームスコアとしてはさほど大きな差には見えずとも、扱いづらい相手との影響をうまく考慮できたAIが群れから前に飛び出せるようなゲームであった。

前半で劣勢だったのを後半で巻き返すというのが難しいゲーム

　このゲームは「資金を株の購入に使って得られた配当金でまた株を購入することを繰り返すゲーム」という形なだけに、序盤に一度劣勢に立つとあまり逆転は見込めない。サイトのほうで負けた試合の様子を観察していると、中盤から後半にかけて相手のほうがたくさん木を収穫しているという状況がよくあるが、そういったときはそもそも前半から劣勢に立たされた結果相手に比べて育っていた木が少ないということが多い。相手がスコアをたくさん獲得したターン前後に目が行きがちであるが、相手がそのターンでたくさんスコアを獲得できた背景にはもっと前の部分での立ち回りの良さがある。なお、特に一番わかりやすい例として、初日に隣にSEEDしてしまう場合、このAIをlegendで提出すると、もれなくこうなる。もちろん圧倒的な実力差があればそんなこともないが、いずれにせよ序盤の悪手は致命的であるということは間違いない。

木をいつ収穫するかの一種のチキンレース

　木はいつ収穫するのが一番だろうか？という問いには答えがない。もちろんある程度妥当らしいタイミングは絞ることができる。相手が全く収穫しない場合は、自分の木が多すぎてGROW効率、日光で得られるポイントの効率が悪くなった時に収穫すればよい。一方、相手が途中で収穫する場合、その前に収穫するか収穫が出遅れてしまうかではポイントが異なる。かといって、相手より先に収穫したからと言って有利になるとも限らない。早すぎる段階で収穫すると後に得られるSunが少なくなるため、この辺りはちょうど良いタイミングが選択されるような評価をしなければいけない。この、「ちょうど良いタイミング」がAIにより異なるだろう。以下の文章を読んでみてほしい。

「相手がちょうど良いタイミングでCOMPLETEすると仮定して、それを考慮したうえで自分がちょうど良いタイミングでCOMPLETEする」

何を言ってるかわからないかもしれないが、おそらくこのようにしてCOMPLETEしているAIが多いのではなかろうか。いわゆるDUCT？（ちょっと知識不足だが）というものではこうはならない気もするが、相手を考慮したビームサーチではたいていこうなる。では、

「相手がちょうど良いタイミングでCOMPLETEすると仮定して、それを考慮したうえで自分がちょうど良いタイミングでCOMPLETEする。この自分の行動を仮定して相手のちょうど良いタイミングを考え直してもらう」

とすると相手のちょうど良いタイミングがしばしば変わるのである。

　これはこのゲームでの相手の様子をうかがう要素で、私が思うにこの要素がほとんどのBot Programingの題材が持っている特性である。であるので、私は毎度この相手の様子をうかがう要素を見つけ、意識しながらコードを書くことにしている。

　なお、育てた自分の木をいつ消すかというこのチキンレースはややCodinGameのSmash the Codeみがある。このゲームを簡単に説明すると、連鎖が1ターンですべて処理されてしまうぷ〇ぷよである。

自身のAIの詳細

ここでは自身のAIについて、その詳細な情報及び、それらに至るまでに考えたことをつづっておく。

アルゴリズム

アルゴリズムは、行動1回=深さ1の、日数を揃えないビームサーチとなった。以下それまでを時系列順に述べる。

最初のアルゴリズムの選定

今回にかかわらず、私はCodinGameのBotProgrammingでは、基本以下の形を採用している。

一手全探索→数手全探索→ビームサーチ

上の変遷には、ひとつ前のコードの大部分をそのまま使えるという利点がある。一手全探索の部分でゲーム情報の格納、大まかな盤面評価などの一連の流れを実装し、数手全探索で再帰的関数あるいはループを用意し、ビームサーチで取り出し数に上限を設ける。段階的にビームサーチに持っていくことで途中途中である程度うまくいっているかが自動的に確認される仕組みのつもりである。

　今回もこの流れに従い、ビームサーチを実装した。この上の流れによって作られたビームサーチは自然と深さ1は行動一回に対応する。

ビームサーチはよい選択だろうか？

　実際にビームサーチを完成させたが、思ったよりうまくいかなかった。Githubで自身のコードの変遷を確認するとビームサーチが完成した時はシルバー解禁前で、確かこの時の順位は1000位前後であるから、ビームサーチの割にあまりうまくいっていないというのはお判りいただけるだろう。後に実際はビームサーチが壊れていたことが発覚した、というのは置いておき、これには私が考える「ビームサーチの弱点」が如実に表れていると考えた。先に断っておくと「ビームサーチの弱点」というのは、ビームサーチの欠陥ということではなく、しっかり考慮して利用すべき点ということである。

　ビームサーチはたいていの場合もっともらしい結果を返してくれるのでついつい何も考えず実装しようとしてしまうが、何も考えずにくみ上げたビームサーチには「良いものを選ぶ」という一方で「現実逃避、先延ばしをしたがる」という弱点がある。仮にビームサーチ中において相手は一切動かないと仮定し、評価値は行動後時点の盤面の評価値のみとして、今回のゲームでいくつか例を考えてみる。

例1.サーチの深さ内では評価が高いが、最終的には勝てないAI

自分：赤

現在のDay：7　（8日目）

ビームサーチの深さ：2　（2回の行動を決める）

盤面評価：その盤面から両者最後までWAITし続けた際の自身の獲得ポイント

　上のような場面、盤面評価というのは、このゲームでありがちである。特にこの盤面評価はゲームのルールに従って定めているだけに妥当に思われる。しかし、このような場合にSEEDするという選択肢が浮かぶだろうか。SEEDという行動は将来的にスコアを伸ばすためには必須のシステムであるが、この盤面評価では「SEEDをふくめてあと二回しか行動できませんよ。それ以降はWAITしてもらいます。」といわれているのである。であれば、残り日数も多いのでここはsize1の木を二つGROWし、得られる収入を最大化するであろう。あるいはもしかするとCOMPLETEしてしまったほうが良いという結論が出るかもしれない。いずれにせよ、将来的なスコアのために必須なSEEDという選択肢はビームサーチの上位には上がらず、木がいっこうに増えないのである。

　これを解消するにはいくつか方法があるが、その一つとして、「見込み」の評価値を追加するという方法がある。上の盤面評価も最終日までWAITした際のポイントとしているのでもらえる「見込み」のポイントを付けているのだが、それとは別に、「盤面に種があると加点」とか「木（種）の数とそのサイズに応して加点」とかが有効である。ただし、これらの加点方法はルールから生まれるものではないので、各自で適した大きさを設定しなければならないのが難しいところである。

　なお、私のAIでは1ターン目にSEEDする行動を別枠でもって置き、SEEDする中での最大評価のものも出すことにしている。あわせて、木の数でわずかに加点したり、SEED先の座標によって行動自体に得点を付けたりもしている。（評価重ねすぎなので非推奨）

例2.最後の深さでの評価は高いけれども、その前までの行動から目を背けるAI

自分：青

現在のDay：7　（8日目）

ビームサーチの深さ：3　（3回の行動を決める）

盤面評価：次の日に自分が貰えるSun-相手がもらえるSun

 　盤面は例1と同じで、今度は自分は青としている。深さも先ほどより1増えて、全探索よりビームサーチが有効になってくる頃かもしれない。盤面評価も変わって、これは相手の妨害も狙った評価方法だ。（こんな極端な評価はしないと思うが。）

　深さ3とあって人間の頭で全部考慮するのは難しいが、私が思うにこのAIがとるのは

GROW 3→WAIT→WAIT

か、この順を入れ替えたものであるだろう。（ほかに同点のものも見つけたが今回紹介したい残念な行動例はこちらのほうが適切なのでこちらを強引に採用する）これが高評価となるのはCell3がSize3にし、二日進めることで、その次の日Cell1,Cell4にある相手の木の収入をなくせるからである。

　ただしこれがあまり良い行動ではないことも明らかだろう。このAIは3日後自分の木の立ち位置が優位になることを知り、ビームサーチで最後の深さが2日後になるものを全体的に高評価にしているだけである。だから、今回GROWしたら、次のターンでの探索ではWAITではなく別の木を成長させたり、3ターンの間に「立ち位置が優位になる前の日」を過ぎなければならなくなる頃までゲームが進むと、途端に固執しなくなり行動を変えたりするのである。

　これを解消するにはいくつかあるが、私がお勧めしたいのは（自分はコンテスト中にできなかったが）日数をそろえるビームサーチである。例えば3日後まで探索するといったことである。この場合最終局面がすべて同じ日になるので、日について同一条件下で判定できる。これを一般に応用するといろいろな条件でそろえて評価できるが、なんでもそろえればよいというわけでもなく、例えば3回SEEDするまで探索といった揃え方は特に意味を持たない（私は今のところ見いだせない、というだけである）。ビームサーチの書き方が少し変わるので一度行動単位で作ってしまうと書きかえたくなかったりするが、その場合はその点でのディスアドバンテージは覚悟しなければならない。（多分結構痛い。それだけに日数をそろえるビームサーチは賢い）

　一応、前の行動まででの評価値を適度に加算していくことで、「最終の深さでだけよいもの」をはじくという手もある。

（例ここまで）

　以上二つの例からわかるように、今回のゲームはSEED、GROW、COMPLETE、WAITの効果が同列に並べがたい行動である（特に、SEED、WAITは他二つと大きく異なる）ために、雑に実装したビームサーチでは思ったほどの効果が出せないのである。

最終提出以外のAIのアルゴリズム

　最終提出は結局最初に組み上げたビームサーチを基盤にしたものであったが、コンテスト中盤では、あまり1行動を深さ1とするビームサーチで効果が出なかったためにほかの方針のAIも作成し検討した。

・一日を深さ1とするビームサーチ

日は揃えられるので整合性が取れるが、この場合一日に取りうる行動の組み合わせが膨大なだけに扱いきれなかった。

・モンテカルロ木探索

理論の言わんとすることはわかるのだが、実装がよくわからなくてただのモンテカルロ法になってしまった。このゲームではかなり有力な方法だと思う。

・遺伝的アルゴリズム

これは構想だけで終わったが、私は各ターンでの可能な行動が固定ではないようなゲームでは基本使わないので、今回もあまり使う気になれなかった。

ゲーム情報をどのようにして保持するか

　今回、Postmortemでも書いたようにBitBoardを使用した。64bit整数型の変数を11個用意し、木を、プレイヤーごと、サイズごとに2*4個の整数に振り分け、Dormantであるかをプレイヤーごと2個の整数に振り分ける。そして残りの一個はrichnessが0のところを示したものになる。各整数は37bitを使用する。

　しかし上の用意の仕方は少々余分で、もし盤面の情報を正確に保持したいだけであれば、以下の8個で充分である。

size0,size1,size2,size3,me,foe,dormant,richness

size0~size3:各セルに該当するサイズの木があれば1を立てる

me,foe:各セルに自分（敵）の木があれば1を立てる

dormant:各セルに行動済みの木があれば1を立てる

richness:各セルのrichnessが0であれば1を立てる

これでも十分に高速である。（例えば自分の木は(size0|size1|size2|size3)&meで求められる）

　では、最初に示した11個の整数で保持する方法では何が便利かというと、相手と自分が同じ場所にSEEDした場合に両方の種を植えられるのである。別にこの機能がいらないという人はいらないと思うが、相手側の行動を探索により先に決定して自分の行動を決定する場合、相手の行動と自分の行動がかち合う場合の挙動は考えておくべきである。仮に、ルールに従い両者が同じCellに種をまいた場合どちらも種をまけないとすると、相手側の行動はすでに完全に一つに定めてしまっているので仮定していた今後の相手の動きをシミュレーションできなくなる可能性がある。

　例えば、後の相手の行動で、その種をGROWする行動があったらどうするか。それらをすべて無効にする手もあるが、その場合は種の位置を相手に合わせる場合の評価値が高くなってしまうかもしれない。もちろん、それで相手のSEEDが防げるならそれほど悪くないかもしれないが、あくまで相手の行動はこちらの推測でしかないので、予想が外れた場合の悲惨さはこの上ないだろう。

　この点、11個の整数を用意する方法では、ゲームのルールを拡張したものになっている。ここでは、各Cellに対して、プレイヤーごとに1つまで木を保存できるので、同じターンでかぶってしまった際には応急処置的に両方の種を植えることで対応できる。シミュレーションの厳密性は弱くなるが、そもそも相手の動きの推測はそれほど的中率も高くないので、さほど問題はないように感じられる。

自分よりも相手に時間をかける

　自分のAIの100msの使い方であるが、

最初の45ms・・・相手の行動をビームサーチで決定

その後40ms・・・相手の行動をシミュレーションしつつ自分の行動をビームサーチで決定

である。

　これを見ると、相手の行動決定はもう少し短く20~30msでよい気がする。これについては、私のビームサーチが日数をそろえていないことに原因がある。自分の行動についてビームサーチで探索するときに相手も最初の45msで仮定した行動を同時にとってもらうのだが、この時、予測した相手の10ターン程度の行動がたまたまWAITをあまりしない行動だった場合どうなるだろうか。この場合、自分が多めにWAITをとると、あるタイミングで相手が急に動かなくなるのである。結果、まず先にWAITして、相手が全く動かなくなってからボコボコにするというものがビームサーチから得られてしまうことがある。そのため、相手の行動は自分よりも先の深さまで仮定しておくほうが安全である。

種を植える場合は4日後に注目

　ある程度AIが完成したもの同士では妨害の強さが勝者を決めるといっても過言ではない。このゲームでの妨害とは、すなわち場所の取り合いか日光の取り合いなのだが、今回は日光の取り合いに注目する。

　しかし、木のCOMPLETEを考えない場合、相手の木と影で争うようなところに植えるかどうかはほとんど相手との差を生まない。なぜならば、相手の陰になった3日後には相手が自分の木の陰になるからである。

　では、どのようにして相手の妨害にまわるか。一番わかりやすいのは、相手を自分の木の陰にして、その後撤収することである。ただし、このゲームのAIを考えた人はわかると思うが、そんなに臨機応変に動けるものではないし、すぐに撤収するのは今後手に入るSunから見てももったいない気がする。

　ならばできるだけ猶予を長くしてみてはどうだろうか。まず明日日が当たる側にあるCellに植えてみる。（下側の画像において、青を自分とした場合）

すると、次の日は種の状態で迎えることになる。いまいち妨害ができていない。また、順調に毎日育てると、その3日後最大サイズで朝を迎えるが、近くの赤の木が成長していたら相手の陰になってしまう。むしろ妨害されてしまうようだ。

　同様に2日後、3日後に日の当たる側になるものについても、自分が日の当たる側にいるときに自分の木が最大になっていないためにあまり効果を発揮できず、さらにその三日後には相手の木に隠されてしまう。

　種を植えた4日後に相手の木を隠せるかに注目したい。これは画像を見てもらったほうが早い。

上の画像で赤が自分だとして、赤い丸で囲った部分においてほしいのである。その左上でもまあ問題ないのだが、5日、6日後も考えると赤い丸のほうが好ましいように思われる。毎ターン成長させると、4日後は最大サイズで朝を迎えることになる。5、6日後までおいておくと3日連続で妨害することができる。その後はCOMPLETEして得点化することもできるし、その前にsize3を利用して次の場所へSEEDしておくこともできる。

　こうやって生まれる差はたかが3~9sunではあるが、ゲーム性で紹介した通り、序盤から中盤、その中でも特にDay7前後で行われる妨害は勝敗を分けうる（Day3とかでやろうとするとsize3にするためのsunが確保できなかったりする）。

おわりに

 　かなり長くなってしまいましたが、以上で終わりになります。上でいろいろなことを書いていますが、このコンテストでは何より楽しみながらコーディングできたのがよかったです。CodinGameでの次のコンテストは秋のようですが、次の大会も今から楽しみです。

【Postmortem】Spring Challenge 2021

※画像は公式Visualizerよりお借りしました

はじめに

　投稿はおよそ二か月ぶりになります。本日は5/6 - 5/17の期間にCodinGame様主催で開催されたコンテスト「Spring Challenge 2021」についての記事になります。全文に目を通してられない方は上の目次だけでもぜひ見ていってください。

　私がCodinGameを知って以降初めて開催されたコンテストだったのですが、うれしいことにLegendに到達でき、結果136位/6867人でした。

　まだプログラミングを初めて間もないのでまだまだ業界用語についてはところどころ間違っていたりすると思いますが、発見された方は優しくご指摘いただけると嬉しいです。

　前回書いたPostmortemはこちら

ゲーム概要

　ゲームルールにつきましては、英語の原文を日本語で読みやすく訳してくださっている方がいらっしゃるので引用します。

雑にいえば木を育てて得点を得るゲームです

最終提出AIの詳細（戦術、アルゴリズム）

言語:Go言語

　今回コンテストに提出したAIはGo言語を使用したものになります。元々私が書ける言語はPythonしかなかったのですが、今回後述するようなアルゴリズムを実装する際に実行速度の差が問題になるだろうと予想したため、かなり高速な言語を選びました。速度ならC++やRustもあるではないかといわれるとまさにその通りだと思いますが、単純に自分が苦手としていて知識も足りないので選べませんでした。

アルゴリズム:ビームサーチ

　注：先に言っておきますが、以下のアルゴリズムと評価方法の組み合わせは個人的には推奨しません。その理由を含め詳細な情報・検討内容は別記事にまとめる予定ですので、興味を持ってくださった方は気長にお待ちください。

　アルゴリズムはdepth1をSEED,GROW,COMPLETE,WAITのいずれかの行動一回分に相当させたビームサーチを行いました。ビームサーチは一手目がSEEDであるものとそうでないもので完全に別々の枠を用意し、それぞれの最大から評価値の高いほうを最後に選択するようにしました。以下、AIの概要です。

・深さ:10

・幅(一手目がSEEDであるもののみ) :50

・幅(一手目がSEEDでないもの):120

・盤面評価回数:10000前後

　上の方法で最初の45msで相手がとる行動をビームサーチで探索し、その探索で得た行動をとると仮定した状態で、40msで自分がとる行動をビームサーチで探索しています。

ビームサーチを機能させるために選択肢を絞る

　ビームサーチはできるだけ短い時間で高い効果を得たいので、以下の行動は排除しました。

必ず排除するもの

・種がすでにあるときのSEED

・自分の木に隣接したCellへSEED

・12日目以前のCOMPLETE

ビームサーチの一手目の検討時以外では排除するもの

・SEED後のCOMPLETE

・GROW後のCOMPLETE

・GROW後、それより大きい木に対するGROW

ゲーム情報・盤面の保持:BitBoard

　今回、初めてBitBoardによって盤面情報を保持してみました。主な理由はビームサーチ時に各手を試すごとに発生するスライスや配列のアロケート？が100msにできる盤面評価回数を少なくしていたからです。今回これに合わせてビット演算も学ぶことができました。盤面は10個のintを用いて

自分、相手のsize3,2,1,0の木の位置で4*2個

自分、相手それぞれでDormantであるかについてで2個

になります。（37bitを使って、対象の木が存在する場合、Dormantの場合に1を立てます）
　richnessについては、richnessは0のものを除くとindexから自動的に定まるので、richnessが0の場所に1を立てたintだけを用意しました。また、隣接情報は、あらかじめ各cellにおいてそのcellとその周囲六マスに1を立てたbitを用意しておき、それを参照して隣接しているかを高速に判定しています。

評価方法:盤面の評価値+各行動の評価値

　盤面の評価値はsunの値ベースで、

value=score*3+sun+(この盤面でDAY23までに得られるsun)

を基本としています。sizeが3の木に関しては順にcompleteした場合に得られるスコア*3を適度に小さくして盤面評価値に加算しています。

ただし、これだけで評価してしまうと相手の要素が少ないので、たいてい最後にまとめてCOMPLETEする

...→COMPLETE→COMPLETE

という実践的でない行動の列が完成してしまう上に、次の日の日光の向きなどを一切考慮しなくなるので、盤面評価のほかに、行動をする際にその行動の妥当性を考えて加点・減点するようにしました。加点・減点のポイントは

SEEDの場合

・SEEDした4日後、5日後、6日後は他の木を陰で隠せるcellか、それとも隠されるcellか

（隠しつつ隠されるようなcellもあります）

GROWの場合

・GROWすることによって一日後、二日後に相手が獲得するsunを減らせるか

COMPLETEの場合

・COMPLETEしたことによって一日後、二日後に相手が獲得するsunが増加してしまわないか

WAITの場合

・過度にSUNを余らせてWAITしていないか

になります。この行動評価の加点・減点ですが、良い行動、悪い行動の着眼点として直感的に正しいことはわかりますが、あまり各行動のバランスの取れるような採点方法ではないではないため、AIの強さはなかなか安定しません。まれに型にはまりそれなりに強くなります。

（なお、Visualizerでは、毎ターンその盤面を評価して評価値に合わせて五種類の表情を出力するようにしてあります。上で述べた盤面評価があまり妥当な評価になっていないことは彼の感情がジェットコースターであることからよくわかります）

最終提出までの失敗から得た教訓

1.Go言語のデフォルトはスライスは参照渡し、配列は値渡し

　Bronzeに到達してすぐはゲームのルールがあまりつかめず、硬直していました。

　とりあえず少し考えてみましたが、やはり何もわからなかったので、とりあえずCell,Treeといった各種classを作成し、入力データをそれらに格納しました。また、与えられるPossibleActionsに頼らず、盤面情報から可能な手を列挙する関数を用意しました。

　ところが、いざこれを使い一手全探索から試してみようとすると、まったく思うような結果になりませんでした。よく確認するとTreeをまとめたtreesというのがスライスで、各行動を試すたびにtreesが変わっているのが原因でした。

　なお、この後ビームサーチを実装したときも、今回ビームサーチは行動のスライスと評価値をセットにしたものを追加して、次の深さで評価値の高いものから順に取り出すという方法を採用していますが、この行動のスライスのアドレスを使いまわしていたことで、次の深さで取り出してみると同じ行動が何個も入っている事件が発生してしまいました。

2.ビームサーチ実装後は、一度正常に機能しているか試す

　ビームサーチを実装すると、それに評価関数をうまくつけてどれくらい通用するか試してみたくなりました。もちろん一度submitしてみるくらいなら問題ないのですが、私はビームサーチが正常に機能しているか試さずにその後評価関数の調整に移ってしまいました。結果、1で述べた同じ行動が何個も入っている事件も中盤まで気付きませんでしたし、なんとそもそもビームサーチ用関数は時間制限で打ち切った場合にちょうど検討していた手を最善として返していたということにも終了数日前まで気づきませんでした。おそらくまだバグが残っているのではないかとも思われますが、もうコンテストに充てられる時間もなかったので実装直後に誤った条件下で肉付けてしまった評価関数が邪魔をして上で紹介したような評価方法になってしまいました。

　私にはよくあることなのですが、土台がある程度形になるとついついその先へと焦ってしまいます。その気持ちを抑え、いま一度土台がしっかりとしているか確認して次へ進むようにしたいです。

3.ローカルでテストする環境を用意する

　今回のコンテストではローカルにコードを保存しつつテストはすべてIDEのみで終わらせていました（私は環境構築が苦手なこともあり今回はそれにかけられるほど時間がありませんでした）。これが原因で、Legend到達前後では自分のAIが強くなっているのかが分からず、サイトの「PLAY MY CODE」を押して一勝しては「強くなったんじゃないか」と期待し、一敗しては「ああ弱くなってるかも」と一喜一憂していました。

　ただし、これについては良かった点として、ゲームの結果が自動的にVisualizerで再生されるので、統計データに惑わされずゲーム内の動きでうまくいっていない動きを確認しやすかったという点もあります。今後はうまく組み合わせる（かVisualizerを含めてローカルで環境構築する）ようにできたらいいなと思いました。

おわりに

　ここまで読んでくださった方、ありがとうございます。この記事はSpringChallenge2021で自分以外の参加者がどんなAIだったのか確認して回っているような方にちらっと紹介する形で投稿いたしました。本記事とは別に、より詳細な情報と検討をまとめた記事を作成する予定ですので、もし興味を持ってくださった方がいらっしゃれば、そちらも見ていただけると幸いです。（投稿までしばらくお待ちください）

更新：投稿しました！

t.co

　今回は日程の都合があまり良くなかったので軽く書いてみるくらいのつもりでしたが、気づけばそれなりの時間をかけてしまいました。次回はより高順位（少し高めに目標をつけるなら賞品ラインくらい）を目指していきたいです。インターネット上ではありましたが、周りでたくさんの人が一緒に取り組んでいるような感じがして楽しかったです。