コンピュータ大貧民の研究報告を読む②
「大貧民における初期手札の不均等性を考慮したレーティングアルゴリズムの提案」では、コンピュータ大貧民のクライアント(プレイヤ)のレーティングを提案している。
http://id.nii.ac.jp/1001/00099271/
レーティングというのは、「プレイヤの強さ(レート)」を計算すること。
過去の対戦結果を使って、
その人の「強さ」を数値化していく作業のことをいう。
この研究では「イロレーティング」(elo rating)という手法を拡張している。
(読み方には「イェロ」とか諸説あるようだが、エロとは読まないらしい)
だた、この手法は、「2プレイヤ用」のアルゴリズムである。
また大貧民では手札の優劣があるので、
試合そのものの有利度に大きく差が出てしまう、
といった問題があるので、アルゴリズムをそのまま利用できない。
というところで、この研究報告がそこに取り組んでいる。
まずはそのイロレーティングを説明すると、
2人のプレイヤーAとBのレートが、だったとすると、
例えばAがBに勝つ確率は
と表される。
ここで試合をやって、Aが回勝った場合には、
として、レートを更新する。
というのはウィキペディアに書いてある。
イロレーティング - Wikipedia
この研究報告で述べられているのは
1. 手札の優劣により、勝率(上の式のE)を補正する
2. 多人数ゲームへ拡張する
まず1. についてだが、最初の手札の優劣度を、
なんらかの手段をもってとして決定する。
そして補正された勝率は
論文中ではの決定には、
簡易的なモンテカルロ法によって勝率を計算して使っている。
そのためのことを「初期盤面勝率」と呼んでいる。
2. の多人数への拡張だが、これは単に平均をとっている。
プレイヤー総数をとおくと、
プレイヤーがに対して勝ったとすると
次の式で更新を行う
それぞれのプレイヤーに対するレート更新を、
平均を取っただけ更新する。
補正の手法はあくまで一例として紹介されているだけで、
もっと単純に考えれば「手札の平均強さ」とかでも代用できそうである。
ただ大貧民は同じクライアントとも、結構多数回やってしまうので、
ある程度やっていたら補正がなくても
収束していくような感じもするが、どうなんだろう。
こうして考えると、
手札の優劣によって勝率がどの程度影響をうけるのだろね。
あとは何試合くらいやれば決まるかも調べないといけない。
大貧民のクライアントの強さ調査もしたかったりするのだけど、
以前はたくさんクライアントがダウンロードできるようだったのだが
今は優勝クライアントがメインである。
UECda-2016 コンピュータ大貧民大会
手始めにここいらから調査してみたいな。
こういう紹介系の記事をいくつも書いていこうと思っていたのだが、
なかなかどうして、まだ2本目である。