2

私は仮想都市コマースゲーム（Urbien.com）のトーナメントモデルを開発しており、アルゴリズムの提案をいくつか入手したいと思っています。シナリオと現在の「基本的な」実装は次のとおりです。

シナリオ

  • エントリは、元のFacemashやPixoto.comのように、デュエルスタイルでペアになっています。
  • 「プレーヤー」は、決闘ペアのストリームを取得し、各ペアの勝者を選択する必要があるジャッジです。
  • トーナメントは決して終わらない。人々はいつでも新しいエントリーを提出することができ、その日のデータに基づいて日/週/月/ミレニアムの勝者が選ばれる。

解決すべき問題

  • 評価アルゴリズム-トーナメントエントリーを評価する方法と、各試合後に評価を調整する方法は？
  • ペアリングアルゴリズム-プレーヤーにフィードする次のペアを選択する方法は？

現在のソリューション

  • レーティングアルゴリズム-チェスやその他のトーナメントで現在使用されているEloレーティングシステム。
  • ペアリングアルゴリズム-現在のアルゴリズムは2つの命令を認識します。
    1. これまでの決闘が少なかったエントリーに、より多くの決闘を与える
    2. 同様の評価を持つ人々をより高い確率で一致させる

与えられたもの：
N=トーナメントのエントリーの総数
D=すべてのプレーヤーがこれまでにトーナメントでプレイした決闘の総数
Dx=プレーヤーxがこれまでに持っていた決闘の数

決闘のためにプレーヤーxとyを選択するには、最初に確率でプレーヤーxを選択します。

p（x）=（1-（Dx / D））/ N

次に、次の方法でプレーヤーyを選択します。評価によってプレーヤーを並べ替えます並べ替えられたリストのインデックスjIdxでプレーヤーjを選択する確率を次のようにします。p（j）= ... 0、if（j == x）n * r ^それ以外の場合はabs（jIdx-xIdx）

ここで、0 <r <1は選択する係数であり、nは正規化係数です。

基本的に、xからのいずれかの方向の確率は、合計が1になるように正規化された幾何学的系列を形成します。

懸念

  • 決闘の情報価値を最大化する-最低評価のエントリと最高評価のエントリを組み合わせても、有用な情報が得られる可能性はほとんどありません。
  • 速度-1つのペアを選択するためだけに大量の計算を実行する必要はありません。1つの代替方法は、新しい決闘を一度に1つずつ選択するのではなく、スイスのペアリングシステムのようなものを使用して、すべてのエントリを一度にペアリングすることです。これには、特定の時間枠で送信されたすべてのエントリがほぼ同じ量の決闘を経験するという欠点（？）があり、これは望ましい場合と望ましくない場合があります。
  • 平衡-PixotoのImageDuelアルゴリズムは、エントリが評価をさらに向上させる可能性が低い場合を検出し、それ以降の決闘を減らします。このような検出の利点については議論の余地があります。一方では、エントリの半分を「一時停止」すると、計算を節約できます。一方、評価が確立されたエントリは、初心者の評価を確立するために、新しいエントリと完全に一致する場合があります。
  • エントリの数-エントリが数個、たとえば10個しかない場合は、おそらくより単純なアルゴリズムを使用する必要があります。
  • 勝ち/負け-プレーヤーの勝ち/負けの比率は、もしあったとしても、次のペアリングにどのように影響しますか？
  • ストレージ-各エントリーとトーナメント自体について何を保存しますか？現在保存されているもの：トーナメントエントリー：＃これまでの決闘、＃勝ち、＃負け、レーティングトーナメント：＃これまでの決闘、＃エントリー
4

1 に答える 1

4

ELOとアドホック確率式を投入する代わりに、最尤法に基づく標準的なアプローチを使用できます。

最尤法はパラメータ推定の方法であり、このように機能します（例）。すべての競技者（プレーヤー）には、そのプレーヤーの強さまたはスキルを測定するパラメーターs [i]（1 <= i <= N、ここでNは競技者の総数）が割り当てられます。2人のプレーヤーの強みを、最初のプレーヤーが勝つ確率にマッピングする式を選択します。例えば、

P(i, j) = 1/(1 + exp(s[j] - s[i]))

これはロジスティック曲線です（http://en.wikipedia.org/wiki/Sigmoid_functionを参照）。次に、ユーザー間の実際の結果を示すテーブルができたら、グローバル最適化（最急降下法など）を使用して、実際に観測された一致結果の確率を最大化する強度パラメーターs [1] ..s[N]を見つけます。たとえば、3人の出場者がいて、2つの結果を観察した場合：

  • プレーヤー1がプレーヤー2に勝ちました
  • プレーヤー2がプレーヤー3に勝ちました

次に、製品の価値を最大化するパラメーターs [1]、s [2]、s[3]を見つけます。

 P(1, 2) * P(2, 3)

ちなみに、最大化する方が簡単な場合があります

 log P(1, 2) + log P(2, 3)

ロジスティック曲線のようなものを使用する場合、重要なのは強度パラメータの違いだけなので、値をどこかに固定する必要があることに注意してください。たとえば、任意に選択します。

 s[1] = 0

最近の試合の「重み」を上げるために、年齢に基づいて試合結果の重要度を調整できます。tが一致が発生してからの時間を（一部の時間単位で）測定する場合、合計の値を最大化できます（例を使用）

 e^-t log P(1, 2) + e^-t' log P(2, 3)

ここで、tとt'は試合1-2と2-3の年齢であるため、最近発生したゲームの方が重くなります。

このアプローチの興味深い点は、強度パラメーターに値がある場合、P（...）式をすぐに使用して、将来の試合の勝ち負けの確率を計算できることです。出場者をペアリングするには、P（...）値が0.5に近いものをペアリングし、時間調整された一致数（e ^ -t1 + e ^ -t2 +..の合計）を持つ出場者を優先します。 ）一致年齢t1、t2、...の場合は低いです。最善の方法は、世界中の2人のプレーヤー間の勝ち負けの合計の影響を計算し、評価に最大の影響を与えると予想される試合を優先することですが、多くの計算が必要になる可能性があります。

最尤推定/大域最適化アルゴリズムを常に実行する必要はありません。たとえば、1日1回バッチ実行として実行し、その結果を翌日の結果を使用して、人を一致させることができます。時間調整されたマッチマスは、とにかくリアルタイムで更新できます。

アルゴリズム側では、sパラメータに基づいて最尤法の実行後にプレーヤーを並べ替えることができるため、同じ強度のプレーヤーをすばやく見つけるのは非常に簡単です。

于 2012-05-10T05:57:30.240 に答える