Marathon Match 99 BrokenSlotMachines 参加記録

問題文:

https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=17092&pm=14853

順位表:

https://community.topcoder.com/longcontest/?module=ViewStandings&rd=17092

 

問題概要

numMachines台のスロットマシーンがある。一つのスロットは3つの回転胴からなり、それぞれに’A’から’G’で表される図柄が一周するようにいくつか描かれている。スロットを回すと、3つのリールは回転し、それぞれ独立ランダムな位置で停止する。このとき、正面に見える3つの図柄が一致すれば、図柄に応じた数のコインを獲得できる。また、正面の図柄以外にも、リールごとに正面の前後1つずつの図柄が見える状態になる。スロットをプレイするときは、以下の2種類の方法を選べる。

quickPlay: 1枚のコインと1単位時間を消費。何の図柄が見えているかを知ることができず、リターンのみが知らされる。

notePlay: 1枚のコインとnoteTime時間を消費。何の図柄が見えているか知ることができる。

最初にcoins枚のコインとmaxTime時間が与えられるので。うまい順番でプレイして、最終的なコインの枚数を最大化しよう。

 やったこと

概要

最初にnotePlayでスロットの中身を見て期待リターンを予測し、一番良いと思ったものを(期待リターン1以上ならば)時間いっぱいquickPlayする。

期待リターンの予測

リールごとの連続する3文字が1回のnotePlayで得られる情報である。

まず、各リールについて独立に考えることにする。リールがある特定の文字列である確率の比は、事前確率×尤度で計算できる。すべての組み合わせでこの確率を計算すれば、各文字が含まれている割合の期待値が計算でき、スロットとしての期待リターンを求めることができる。実際には、すべての文字列について計算することはできないが、ほとんどの場合で尤度が0もしくは相対的に小さな値になることに注意し、尤度の大きいものだけをサンプリングする。

得られた3文字のうち、登場しないものが存在すれば、尤度は0である。また、試行回数が十分大きいとき、長い文字列ほど尤度は小さくなる。

そこで、得られた3文字集合を連結し、できるだけ短い文字列を作る。作り方は貪欲+スワップベースの探索とした。サンプリングしたいだけなのである程度雑にやっていいい気がする。

各リールごとに独立に考えていたが、1つのスロットのすべてのリールは長さが同じことは利用できる。他のリールより短い文字列が得られた場合、実際より短すぎるのかもしれないので、適当に文字列をのばしたりしたものもサンプリングする。

どのような順番でプレイするか

多腕バンディット問題におけるUCBの式を参考に、期待リターンが高いほど、試行回数が少ないほど選ばれやすいように評価関数を書いた。

台iの評価 = (台iの予測期待リターン) + (定数)×sqrt(log(総試行回数)/(台iの試行回数))

また、quickPlayに切り替えるタイミングは、上式の第二項がある値を下回る時とした。

性能評価

実行結果のよさは、期待リターン最大の台を選び続けたときの最終的なコインの期待値との相対スコアによって測った。3000ケースを使ってプログラムとしての性能を測った。これをもとにパラメータの調整を行った。これでも結果のばらつきは大きく、調整が大変だった。

やりたかったこと

評価関数に、リールの長さが長いほど予測の不確実さが大きいなど要素を取り入れたかった。

実行時間があまり大きくならないようにしていたので、サンプリングの方法が雑になったのを何とかしたかった。実行時間がかかるとパラメータ調整が大変になるので、このトレードオフが難しかった。