jpnsec

ゲームを楽しくする乱数の設計問題

2020年進化計算コンペの問題

rngbias

Abstract

通常，ゲームに使われる乱数はメルセンヌ・ツイスターやXorshiftなどのごく一般的な方法で生成します．しかし，これらの数学的には偏りの小さいはずの乱数が，ゲームのプレイヤーにとっては偏っているように（時には恣意的に操作されているようにさえ）感じられ，強い不満をもたらすことがしばしばあります．人間は確率的な事象に対して様々なバイアスをもっていることが知られており，偏りのない乱数は人間にとってむしろ偏っているように感じられるのです．そこで，プレイヤーにとって偏りのないように感じられる（実際には偏った）乱数を設計する問題を考えます．

ゲームをより楽しくするためには，乱数にはプレイヤーにとって認知的に偏りがないことが望まれます．後述する先行研究では，被験者実験を行って乱数列の「認知バイアス」を15個の指標で定量化しています．被験者実験で得られた指標値に近い指標値をもつ乱数列を生成することで，プレイヤーの不満が軽減されることが示されました．一方でその実験では，認知バイアスには個人差が大きいことも判明しました．したがって，開発者は自身のゲームのプレイヤー層に応じた乱数列を生成する必要があります．ゲームに用いた乱数列がプレイヤーにどのような印象を与えたかは，プレイ後のアンケート等から推測することになります．

一方で，ゲームの公平性を保つためには，乱数には統計的に偏りがないことも求められます．乱数に手を加えたことで，プレイヤー間に有利不利が生じたり，乱数の長期的な振舞いがみだれて戦略が立てられなくなったりしてはゲームになりません．もちろん，乱数に手を加える以上は，何らかの偏りが生じることは避けられません．しかしそうであっても，少なくとも基本的な統計量に関しては乱数が偏っていないことを保証する必要があります．統計量をもとにして定義される「統計的バイアス」の指標は，認知バイアスとは異なり，乱数列さえあれば計算することができます．

したがって，本問題では，統計的バイアスを表すホワイトボックス制約関数が閾値以下となる数列の中から認知バイアスを表すブラックボックス目的関数ができるだけ小さい値をとる数列を見つけ出す組合せ最適化問題を考えます．

本問題のソースコードを公開しています．このプログラムをローカルで実行して試行錯誤することができます．
https://github.com/opthub-org/eccomp2020

1. 定義

本問題の一般形は以下のように定式化されます．

\begin{array}{rl} \text{minimize } & f(x) = (f_1(x),\ldots,f_M(x))\\ \\ \text{subject to } & x \in \{1,\ldots,6\}^{N},\\ & g_l(x) \le 0 \quad (l=1,\ldots,L),\\ \\ \text{where } & f_m(x) = \sum_{i \in I_m} E_i(x),\\ & g_l(x) = e_{d_l}(x). \end{array}

ここで， $E_{i}$ は1.1節で定義される認知バイアスに関する誤差， $e_{i}$ は1.2節で定義される統計的バイアスに関する誤差です．上式に現れる $L,M,N\in \mathbb N$ と $I_1,\ldots,I_M \subseteq \{1,\ldots,15\}$ ，および後述する $E_{i}$ と $e_{i}$ の定義に現れるパラメータを設定することで，具体的な問題が作られます．

1.1. 認知バイアス

以下の論文で，乱数に対する認知バイアスが研究されています．

野村久光, テンシリリックンシラ, 池田心: 標準的なゲームプレイヤにとって自然に見える疑似乱数列の生成法，第18回ゲームプログラミングワークショップ，pp.27-34, 2013-11 JAIST Repository

この論文では，認知バイアスを表す15種類の特徴量が提案されています．

$F_{1}$ : 全体で出た目の回数の $χ^{2}$ 値
$F_2,\ldots,F_5$ : 系列の約4分の1のそれぞれにおける出た目の回数の $χ^{2}$ 値
$F_{6}$ : 偶数と奇数が並ぶ部分の数
$F_{7}$ : 同じ目が2連続する部分の数
$F_{8}$ : 同じ目が3連続する部分の数
$F_{9}$ : 同じ目が4連続する部分の数
$F_{10}$ : XXYY, XYXY, XYYX など、2つの目が2つずつ登場する部分の数。ツーペア
$F_{11}$ : XXYYYなど、2つの目が2つと3つ登場する部分の数。フルハウス
$F_{12}$ : XYXXなど、両端を含め4つ中3つが同じ目である部分の数
$F_{13}$ : XYXZXなど、5つ中3つの場合
$F_{14}$ : XYXZXXなど、6つ中4つの場合
$F_{15}$ : XXYXZWXなど、7つ中4つの場合

この論文では，乱数列 $x\in \{1,\ldots,6\}^N$ の特徴量を $F_{i} (x)$ としたとき，プレイヤーが自然に感じる値との誤差を以下のように定義しています．

\begin{array}{rl} E_i(x) &= \begin{cases} \gamma_i \times (\alpha_i - F_i(x)) & (F_i(x) < \alpha_i)\\ \gamma_i \times (F_i(x) - \beta_i) & (F_i(x) > \beta_i)\\ 0 & (\text{otherwise}) \end{cases}\\ \text{where } &\alpha_i \le \beta_i, \quad \gamma_i > 0. \end{array}

直感的に言えば，特徴量 $F_{i}$ がプレイヤーにとって自然に感じられる許容範囲 $(\alpha_i \le F_i \le \beta_i)$ から外れると，外れ具合に比例した強さの不満をもつ，というモデルです．この論文では，すべての特徴量が許容範囲に収まった乱数列を用いることで，通常のサイコロを用いるよりもプレイヤーの不満を軽減できることを実証しています．

1.2. 統計的バイアス

ゲームでは「サイコロを3つ振る」など，同時に複数の乱数を用いることがよくあります．その際に出目が偏ることは好ましくありません．そこで本コンペティションでは，乱数列 $x \in \{1,\ldots,6\}^N$ に対して，以下で定義される $d$ 次元部分列のカイ二乗値 を用いて偏りがないか評価します．

\begin{array}{rl} &\chi^2_d(x) = \sum_{s\in \{1,\ldots,6\}^d} \frac{(c_s(x) -m_s)^2}{m_s},\\ \text{where } &m_s = \frac{\lfloor N/d \rfloor}{6^d},\\ &c_s(x) = \text{系列 $v_1(x),\ldots,v_{\lfloor N/d \rfloor}(x)$ における $s$ の出現回数},\\ &v_n(x) = (x_{(n-1)d+1},\ldots,x_{nd}) \quad (n=1,\ldots,\lfloor N/d \rfloor).\\ \end{array}

直感的に言えば， $\chi^2_d$ とは乱数列1周期を先頭から $d$ 個ずつに区切って $d$ 次元ベクトルを作ったときの出目のばらつきを表すもので，値が小さいほど出目は均等で，値が大きいほど出目は偏っていることを意味します．これは $N$ が十分大きいとき近似的に自由度 $6^{d} - 1$ のカイ二乗分布にしたがいます．

そこで，自由度 $6^{d} - 1$ のカイ二乗分布の累積分布関数の値が $p$ となる点を $q_{d} (p)$ とするとき，与えられた $0 \le p_d \le P_d \le 1$ について $q_d(p_d) \le \chi^2_d(x) \le q_d(P_d)$ であることを制約とします．つまり，乱数列 $x$ を区切って作った $d$ 次元ベクトルの出目は，確率 $p_{d}$ 未満でしか生じないほど極端に均等ではないし，確率 $1 - P_{d}$ 未満でしか生じないほど極端に偏ってもいないということです．制約を違反したときに値が正となるように以下の誤差関数を定義します．

\begin{array}{rl} e_d(x) &= \begin{cases} q_d(p_d) - \chi^2_d(x) & (\chi^2_d(x) < q_d(p_d))\\ \chi^2_d(x) - q_d(P_d) & (\chi^2_d(x) > q_d(P_d))\\ 0 & (\text{otherwise}) \end{cases}\\ \text{where } & 0 \le p_d \le P_d \le 1. \end{array}

1.3 問題定義

1.3.1 単目的の場合

単目的の場合は，先行研究の定式化に上記の制約関数を加えた問題を最適化します．

\begin{array}{rl} \text{minimize } & f(x) = \sum_{i=1}^{15} E_i(x)\\ \\ \text{subject to } & x \in \{1,\ldots,6\}^{N},\\ & g_i(x) \le 0 \quad (i=1,\ldots,12),\\ \\ \text{where } & E_i(x) = \begin{cases} \gamma_i \times (\alpha_i - F_i(x)) & (F_i(x) < \alpha_i)\\ \gamma_i \times (F_i(x) - \beta_i) & (F_i(x) > \beta_i)\\ 0 & (\text{otherwise}) \end{cases}\\ & g_i(x) = \begin{cases} p_i - \chi^2_i(x) & (\chi^2_i(x) < p_i)\\ \chi^2_i(x) - P_i & (\chi^2_i(x) > P_i)\\ 0 & (\text{otherwise}) \end{cases} \end{array}

ここで， $\alpha_i, \beta_i, \gamma_i$ はプレイヤーのバイアスを表す非公開パラメータ， $p_{i}, P_{i}$ は自由度 $6^{i} - 1$ のカイ二乗分布の10%点と90%点を表す公開パラメータです．

1.3.2 多目的の場合

多目的の場合は，認知バイアスの特徴量を個別の目的関数とした問題を最適化します．どの特徴量を加算するかを変えることで， $M = 2, 3, 5, 7$ 目的問題を考えます．

\begin{array}{rl} \text{minimize } & f(x) = (f_1(x),\ldots,f_M(x))\\ \\ \text{subject to } & x \in \{1,\ldots,6\}^{N},\\ & g_i(x) \le 0 \quad (i=1,\ldots,12),\\ \\ \text{where } & E_i(x) = \begin{cases} \gamma_i \times (\alpha_i - F_i(x)) & (F_i(x) < \alpha_i)\\ \gamma_i \times (F_i(x) - \beta_i) & (F_i(x) > \beta_i)\\ 0 & (\text{otherwise}) \end{cases}\\ & g_i(x) = \begin{cases} p_i - \chi^2_i(x) & (\chi^2_i(x) < p_i)\\ \chi^2_i(x) - P_i & (\chi^2_i(x) > P_i)\\ 0 & (\text{otherwise}) \end{cases} \end{array}

目的関数は以下のように定義されます．

$M = 2$ $M = 2$
- $f_1(x) = E_1(x) + \cdots + E_7(x)$
- $f_2(x) = E_8(x) + \cdots + E_{15}(x)$
$M = 3$ $M = 3$
- $f_1(x) = E_1(x) + \cdots + E_5(x)$
- $f_2(x) = E_6(x) + \cdots + E_{10}(x)$
- $f_3(x) = E_{11}(x) + \cdots + E_{15}(x)$
$M = 5$ $M = 5$
- $f_{1} (x) = E_{1} (x) + E_{2} (x) + E_{3} (x)$
- $f_{2} (x) = E_{4} (x) + E_{5} (x) + E_{6} (x)$
- $f_{3} (x) = E_{7} (x) + E_{8} (x) + E_{9} (x)$
- $f_4(x) = E_{10}(x) + E_{11}(x) + E_{12}(x)$
- $f_5(x) = E_{13}(x) + E_{14}(x) + E_{15}(x)$
$M = 7$ $M = 7$
- $f_i(x) = E_{2i-1}(x) + E_{2i} (x)\quad (i=1,\ldots,6)$
- $f_7(x) = E_{13}(x) + E_{14}(x) + E_{15}(x)$