進化計算コンペティション2024年　無事終了したけど当日気づいたナンプレの罠

昨年末に2024年進化計算コンペティションを開催し、なんとか無事終了しました。
関係者の皆様に感謝いたします。
今回は進化計算コンペティションについて説明します。

https://www.headwaters.co.jp/news/competitions_eccomp2024_support_hws.html

進化計算コンペティションのながれ

進化計算コンペティションというのは前回もお話しした通り、
最適化のコンペティションです。
毎年テーマが決まっていて、今年のテーマはナンプレの問題作成でした。
進化計算コンペティションは１１月から１か月ほどかけて開催され、１２月２１日の進化計算シンポジウムでプレゼンを経て表彰されます。
プレゼンはポスター発表です。各自A0のポスターを貼り、その前で説明をします。
オンライン参加もできます。その場合はオンラインでプレゼンをすることになります。

部門としては単目的部門と多目的部門があります。
多目的というのは多目的最適化のことです。
多目的最適化がどういうものかという点についてはここでは説明しませんが、
簡単に言うと、最適化の分野では目的が複数ある場合も研究対象で、多くの研究がなされています。
興味がある方は調べてみてください。

進化計算コンペページ

実際の出題された課題

下の図のように、実際、コンペティションで出題された課題はヒント数２０と２４の対称な配置が制約でした。
図の緑部分に初期配置の数字が入ります。その初期配置の数字を埋めることが課題です。
単目的の場合で出題者の決めた目的関数値が評価値として返されます。

この問題、実は解ける組み合わせを探すだけで難しい問題です。
ランダムに２０または２４の数字を選ぶ組み合わせは$9^{20}=1.2\times 10^{19}$, $9^{24}=8.0\times 10^{22}$ですが、条件に合う組み合わせが少ないらしく、試しにランダムに組み合わせを探してみましたが1日かけても一つも見つかりませんでした。

「良いナンプレ」とは？

何とか組み合わせが見つかったとして、見つかってからが重要です。
今回面白さを示す指標として専門家と議論し、下に示す２つの要素があると考えました。

• 難易度の山場の緩急があること　＝　緊張感の観点からの面白さ(f1)
• 難易度の高いテクニックの後は、連鎖的に簡単な手法で解けるカタルシスが存在すること　＝　連鎖的なマス目の決定に関する面白さ(f2)

f1を計算するためには盤面の難易度を計算しなければなりません。
ゲーム全体の難易度は解法テクニックによって決まるという考えが一般的です。
しかし、解いている途中の盤面の難易度を計算するのはどうしたらいいでしょうか。

盤面にはたいていヒントを元に数字を埋められる場所があり、その一つ一つを手筋と呼びます。
ある盤面には一つの手筋しかないということの方が稀で、いくつもの手があり得ます。
それらの手には解法テクニックに依存しているので、それらの手の解法テクニック難易度の調和平均を取ります。

$$d(t) = \frac{1}{\sum_a{1/L(a)}}$$

Lは一つの手筋の各解法テクニックに割り当てられた値です。
ここから下の指揮で難易度ピーク値を計算します。

$$p(t)= \sum_i{\frac{d(t)-d(i)}{|t-i|^2}}$$

緊張度はこの上位２つのピーク間の距離が離れていることとしました。

$$f_1 = \frac{|t_1 - t_2|}{T}$$

これが目的関数の一つ目のf1の計算式です。
これはプロの意見を聞き、何度も議論して決めたものです。

詳しい関数形はコンペの問題ページに説明を載せていますので、興味ある方はご一読ください。

しかし、このf1が思わぬ事態を招くことに．．．

意図しない結果に

目的関数の$f_1$は難易度のピークが離れていることを数式化しましたが、
そのためか、生成されてきたナンプレは、初手の難易度が高いものが多く出てしまいました。
確かに、初回の難易度を高くして、後半に難易度の高い盤面を作ればピーク間は確かに開きます。

つまり、初めから解けない．．．(*´Д｀)
という、初心者の心を折る問題が続出しました。

最初は簡単な方がいい。このナンプレは初めからやる気を失ってしまう．．．

ということを当日会場でナンプレを自分で解いてみて気づきました。