本問題のソースコードを公開しています．このプログラムをローカルで実行して試行錯誤することができます． [https://github.com/opthub-org/eccomp2020](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](http://hdl.handle.net/10119/12991) この論文では，認知バイアスを表す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$ - $f_1(x) = E_1(x) + \cdots + E_7(x)$ - $f_2(x) = E_8(x) + \cdots + E_{15}(x)$ - $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$ - $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$ - $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)$ ここで， $\alpha_i, \beta_i, \gamma_i$ はプレイヤーのバイアスを表す非公開パラメータ， $p_i, P_i$ は自由度 $6^i - 1$ のカイ二乗分布の10%点と90%点を表す公開パラメータです．

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

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

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