TCO21Final に参加してきました。

問題

下の画像のようなトーラス状の N * N フィールドが存在しており、コインを 1つ取ると 100 point、棘を踏むとスコアが半分になります。コインは取得すると消えますが、棘は踏んでも消えません。

f:id:simanman:20211119225829p:plain:w400

プレイヤーは自由に移動できるというわけではなく移動用のサイコロを複数保持しています。(2 ~ 6 個）サイコロの種類は全部で 12種類存在しています。

0 が出るサイコロ (STAY)
1 が出るサイコロ (ONE)
2 が出るサイコロ (TWO)
3 が出るサイコロ (THREE)
4 が出るサイコロ (FOUR)
5 が出るサイコロ (FIVE)
6 が出るサイコロ (SIX)
1 or 3 or 5 が出るサイコロ (ODD)
2 or 4 or 6 が出るサイコロ (EVEN)
1 or 2 or 3 が出るサイコロ (LOW)
4 or 5 or 6 が出るサイコロ (HIGH)
1 or 2 or 3 or 4 or 5 or 6 が出るサイコロ (RANDOM)

1 度サイコロを使用すると、そのサイコロは消費され新たなサイコロを補充します。このとき補充されるサイコロの確率は各サイコロの出目の種類数に比例します。（なので、例えば RANDOM は ONE のサイコロよりも 6倍出やすく、ODD よりも 2倍出やすいといった感じです）

N * N ターンの間でより多くのスコアを取得するように頑張りましょうという問題です。（N * N ターンの経過を待たずとも途中で辞めることも可能です）

方針

最初は効率的にコインを集める方法で最初考えていたのですが、棘が密集している画像を見て「いかに棘を踏まないようにサイコロを振るか」に方針を変えました。

f:id:simanman:20211119232321p:plain:w400

基本方針は貪欲で現時点で保持しているサイコロを振ってみて止まる可能性のあるマスをすべて試して、その後の盤面の評価値の合計が高いものを採用していきます。

評価値としては主に以下のような内容になってます（一部）

コインに止まる [+100]
棘に止まる [-score / 2]
RANDOM サイコロを消費する [+1000]
RANDOM サイコロを安全に消費できるマスに移動する [+100]
棘以外のマスで STAY サイコロを振る [+1000000]

ある程度ゲームを回してみたところ、手持ちが RANDOM サイコロだけになり棘を踏むリスクが高まってゲームを中止するといった流れが多く見られたので、とにかく RANDOM を捨てることに比重を置きました。STAY サイコロは実質手札交換みたいなものなので振れるタイミングでは必ず振るようにしています。

あとは、実際にジャッジ側に投げる前にどの程度のスコアが取れるのかを事前にシミュレーションをしておき、そのシミュレーションの平均スコアを基準にゲームをやめるかどうかの判断を行いました。

やめる基準としては 事前計算した平均スコア * 0.8 のスコアを保持している状態で棘を踏む可能性が発生した際に、ローカルでシミューレーションを複数回してそのスコアの平均値が今よりも大きいのであればゲームを続行、そうでないなら終了という判断をしています。