はじめに
「頭の良くなる推理カードゲーム」というキャッチコピーでおなじみのボードゲーム『アルゴ』を知っていますか？
アルゴは2人プレイの数字当てゲームです。先に相手のカードの数字を全て当てたら勝利というシンプルなルールです。
アルゴはキャッチコピーの通り、プレイすることで頭が良くなるのが想定されていますが、プログラミング、数学の題材としても学びのあるゲームだと思います。
本記事ではアルゴのルールを紹介した後、数字を当てるロジックとしてベースラインとなる手法を挙げ、手法の問題点について検討します。
次にその問題を解決するため、平均情報量を用いた指標を最大化するように行動選択を行うアルゴリズムを提案します。
最後に、各種手法を実装し対戦をシミュレーションした結果を紹介します。
アルゴとは
アルゴとは、論理的思考が問われる推理カードゲームです。
シンプルなルールなので、子どもからでも十分に楽しみつつ論理的思考を養うことができる良いゲームで、自分も小さい頃から好きでよく遊んでいました。
ルールは以下のとおりです。
(なるべくシンプルに書きましたが、面倒な方は飛ばして具体例を読んでイメージを掴んでもらえればと思います。)
基本情報とゲームスタートまでの手順：
- 2人プレイです
- カードが黒の0~11, 白の0~11の24枚あります
- カードの表に数字が書かれていて、裏は何も書かれておらず色だけわかる状態です
- 始めに4枚ずつ各プレイヤーは山札からドローし、数字を確認して裏向きに並べます
- 並べ方は、左から右へ数字が昇順になるように並べます。
- 同じ数字は黒より白の方が大きい(右側)になるように並べます
各ターンの進行：
- ゲームはターン制で進行します
- 自分のターンになったら、カードを山札からドローして数字を確認します
- 相手のカードのうち裏向きのカードを選び、数字を宣言します
- 数字が当たったらアタック成功で、相手は当てられたカードは表向きにします
- アタックに失敗した(数字が外れた)場合、ドローしたカードを表向きにして自分のカード列の正しい位置に挿入します
- 勝利条件は、相手のカードをすべて表にすることです
アタックが成功した後に関するルール：
- アタックに成功したプレイヤーは、引き続きアタックを続けるか、スキップを選択できます
- 各ターンの最初は必ずアタックしないといけません
- アタックせずにスキップを選択した場合、ドローしたカードは裏向きにして自分のカード列の正しい位置に挿入します
- アタックが失敗するか、スキップしたらターン終了で、相手のターンになります
ルールは以上です。
何をするゲームか一言で言うなら、
カードの並び方は昇順で色にも順序があること、同じ色、数字のカードは一枚しかないことなどを判断材料に、相手の裏になっているカードの数字を推理する
というゲームです。
例えば、
白1, 白?, 黒?, 白3
という相手のカード列の場合(?はカードが裏向きで数字がわからない状態です)、
- 白1と白3の間にある白は白2しかなく、
- 白2と白3の間にある黒は黒3しかない
という論理から
白1, 白2 黒3, 白3
と推理できるので、「左から2番目は白2！」とアタックする、といったイメージです。
この例では相手のカード列のみから特定できましたが、他にも自分のドローしたカードや、自分のカード列の情報も使うことができます。
自分の持っているカードは相手は持っていないので、候補を減らすことができます。
例えば、相手のカード列が
白1, 白?, 黒?, 白4
となっている場合を考えたとき、先ほどと違って一番大きいのが白3ではなく白4なので、真ん中の2枚の可能性は相手のカード列の情報だけでは1通りに絞り込めず、
白2, 黒3
白2, 黒4
白3, 黒4
の3通りあります。
ただ、自分が白2を持っている場合、同じカードは1枚しかないので、上の二つの可能性が消えて、
白3, 黒4
と一つに絞ることができる、といった具合です。
イメージが掴めてきたでしょうか？
数字当てゲームの一種ですが、アルゴの特徴的な点は、
- 連続でアタックするかスキップするかを選べる
- アタックの成否によって自分または相手のカード列にドローしたカードが追加される
という点です。
アタックに失敗してしまうとドローしたカードを表で自分のカード列に加えなければいけないので、相手がアタックする際に絞り込みやすくなってしまいます。
なるべく連続でアタックを成功させつつ、時にはアタックをスキップして相手のアタックを成功を阻止するのも戦略の一つです。
Baseline
次に、本記事におけるBaselineを紹介します。
Baselineでは、とりうるアタックをすべて列挙し、各アタックが成功する確率を計算したあと、成功確率が一番高いアタックを選択する、というロジックです。
2回目以降のアタックをスキップするかどうかの判定は、あらかじめ決めた確率$\epsilon$に従って選択することとします。
バンディッドアルゴリズムの$\epsilon$-greedy法のようなアルゴリズムなので、こちらでも$\epsilon$-greedyと呼ぶことにします。
$\epsilon=0$であればスキップはせずに失敗するまで成功確率が一番高いアタックをし続ける積極的な戦略となり、逆に$\epsilon=1$と設定すると一度アタックが成功すると2回目は必ずスキップするという保守的な戦略になります。
アタックの成功確率の計算
最終局面など場合の数が少ない場合を除いて、人間の頭でゲーム中に計算するのはほぼ無理でしょうが、コンピュータであればアタックの成功確率を全列挙することができます。
手順は以下の通りです。
- 自分が見えているカードと、これまでの失敗したアタックの履歴を使って相手のカード列の候補をすべて列挙する
- 列挙した候補を、裏側のカードの位置ごとに集計する
先ほど使った例で説明すると、
白1, 白?, 黒?, 白4
となっているとき
白2, 黒3
白2, 黒4
白3, 黒4
という候補を列挙し(手順1)
以下のように各ポジションごとに、確率を計算します(手順2)。
左の白のカードに対して白2というアタックは成功確率=2/3で、白3は1/3とわかります。
右の黒に対しては黒4が2/3で成功します。
このように、自分のカードやドローしたカード、これまでにアタックが失敗した履歴を使って相手のカード列の候補を列挙し、そこからとりうるアタックとその成功確率を算出することができます。
カード列候補の全列挙
ちなみに、手順1の「相手のカード列の候補を全て列挙する」の詳細については色々やりようはあると思いますが、
自分が今回の実装では、カード列の候補を求める前に、まず各位置の候補を次のように列挙します：
- 自分のカードやドローしたカード、これまでにアタックが失敗した履歴から可能性のないカードを除外
- 対象カードの左と右をみて数字の上限と下限を求める
- 上限と下限の間にある数字に絞る
各位置の候補のカードをこのように求めた後、全ての位置ごとの候補の組み合わせを全て試して、カード列として成立するもの(同じカードがない、カードの並び順が正しい)のみ返すことで全列挙を実現しています。
もっと賢い方法があるかもしれませんが、一旦これで不都合はなさそうなのでこの実装にしています。
提案手法
次に、Baselineとして提示した$\epsilon$-greedyの問題点を改善するための手法を提案します。
$\epsilon$-greedyの問題点として、確率的にスキップしてしまう点が挙げられます。
確率的にスキップすることの何が問題かというと、
自分のカード列にドローしたカードを加えた時の相手プレイヤーから見たときの候補の増加/減少量に無関係にスキップする/しないが選択されてしまうということです。
ドローしたカードを表で追加すると情報が増えて相手に有利になると書きましたが、状況によっては情報が増えない場合もあります。
例えば
白0, ...
というカード列を自分が持っていたとして、黒0をドローした場合、仮にアタックに成功してスキップしても
黒?, 白0, ...
となっても黒?は白0より小さいので黒0とわかってしまいます。つまり裏で追加してもメリットが0ということです。
逆に表で追加しても
黒0, 白0, ...
となっても他のカードの候補が減らないので、アタックに失敗してもデメリットがないと言えます。
この場合、スキップをするメリットがないのでアタックするのが得なわけですが、$\epsilon$-greedyではこれが考慮できません。
当然逆もあり得て、裏で追加すると候補の数が大きく増えるとか、表で追加すると候補の数が大きく絞られるようなドローをしてしまった場合、無理してアタックするよりスキップを選択するインセンティブが大きくなります。
このように、アタックとスキップからなるアクションの集合から一つのアクションを選ぶ際、そのアクションを取ることによって相手のカード列の候補が大きく減って、自分のカード列の候補は増えるようなアクションを取る戦略が賢そうと考えることができます。
詳細は次のセクションで説明しますが、実行したアクションによる相手と自分のカード列の候補数の増減を平均情報量を用いて表現し、アタックとスキップを同じ土俵で比較できるようにするのが提案手法のアイデアになります。
アルゴリズム
提案手法の具体的なアルゴリズムの説明をします。
本手法では、次の指標$I_k$を最大化するようにアクション$k \in A$を決めます。
I_k = p_k(-\log(p_k) + D_k) + (1-p_k)(-\log(1-p_k) - \hat S)
各文字の定義は以下の通りです。
- $A$ : とりうるアクション(各アタックと2回目以降はスキップも加えたもの)の集合
- $p_k$ : アクション$k$が成功する確率. (スキップの場合は$p_k=1$とします)
- $D_k$ : アクション$k$が成功した後の状況で次の行動で得られる平均情報量の最大値
- $\hat S$ : ドローしたカードを表で加えた時の相手から見た平均情報量の推定値
$D_k$の求め方は、アクション$k$がアタックかスキップかで異なります。
アクション$k$がアタックの場合、アタックが成功したと仮定して、候補を更新し取りうるアタックとその確率を再計算し、各アクションに対して$I$を計算し最大値を返します。
実装上は再帰関数を用いることで計算できますね。
アクション$k$がスキップの場合、$p_k=1$, $D_k=T$とします。ただし、$\hat T$はドローしたカードを裏で加えた時の相手から見た平均情報量の推定値です。
指標の意図
一般に平均情報量は確率$p$の行動をしたときに
-p\log(p) -(1-p)\log(1-p)
となりますが、
アルゴでは
- アタックが成功すると次の行動ができる
- アタックの失敗で相手からみた平均情報量も変化する
- スキップできる
といった点で工夫が必要になります。
アタックが成功した時、そのアタック自体以外に、その後の行動によって得られる平均情報量$D_k$を追加しています。
アタックが失敗した時、ドローしたカードを表で加える事による相手から見た平均情報量を$- S$としています。相手の平均情報量はこちらから見るとマイナスなので、マイナスをつけています。
スキップした時は次の行動はなく、代わりにドローカードを裏で追加する事による平均情報量の減少分を$T$としてスキップした際の平均情報量としています。
$S$と$T$は相手のカード列が完全にはわからないのと、次のドローカードが未知なので、真の値はわからないため、なんらか方法で推定する必要があります。
今回用いた推定方法は、相手のカード列としてありうる候補のリストを先述した方法で列挙し、そこからいくつかの候補をサンプリングし、サンプリングしたカード列で相手のカード列を固定した元で、ドローカードを追加する前後の場合の数を数えて平均情報量を計算し、それぞれ$S$と$T$の推定量$\hat S$, $\hat T$としました。
実装上では、$\hat T$を計算するときに愚直にドローカードを表にして加えて候補のリストを求めるのではなく、$\hat S$を先に計算する際に列挙したリストを再利用して求めています。
実装上のポイント
とりうる全てのアクションについて平均情報量を計算しようとすると計算が終わらないので、いくつか探索する範囲を狭めたりサンプリングしたりしています。(が、依然遅い。。)
具体的には、子ノードの平均情報量$D_i$を計算する再帰関数の部分では、深くなるにつれてrootの行動選択への影響は小さくなっていく(成功確率$p_i$がかかってくるため)ため、探索する深さを決めて打ち切っています。
また、探索するアクションの候補も全て試すのではなく、成功確率が高いN個 + スキップできる時はスキップも加えたリストに絞って探索するようにしています。
平均情報量の最大化部分のコードはこちらです。
def maximize_entropy(attacks_with_proba, candidate_hands_list, opponents, player,
opened_cards, new_card, history, phase1_max_num, depth=0, max_depth=2) -> Tuple[Optional[list[Tuple[Attack, float]]], float]:
if depth == max_depth:
print("> "*depth+"Recursion reached max_depth.")
return None, 0
max_gain = -10000000
max_attacks = []
entropy_opened, entropy_closed = estimate_self_entropy(candidate_hands_list=candidate_hands_list, opponents=opponents,
player=player, opened_cards=opened_cards, new_card=new_card,
history=history)
for attack, p in attacks_with_proba:
if attack is None:
print("> "*depth + "Skip")
# the case of skip
entropy_gain = - entropy_closed
else:
print("> "*depth + f"{attack}, {p}")
filtered = [
candidate_hands for candidate_hands in candidate_hands_list for opponent, hands in candidate_hands
if (opponent == attack.attacked_to) and (hands.cards[attack.position].get_content() == attack.card_content)]
# copy
opponents_sim = copy.deepcopy(opponents)
for opponent_sim in opponents_sim:
if opponent_sim.player_id == attack.attacked_to:
opponent_sim.open(position=attack.position)
next_attacks = transform_candidates_from_hand_to_attack(
candidate_hands_list=filtered, opponents=opponents_sim, player=player)
next_attacks = select_attacks_with_high_proba(
attacks_with_proba=next_attacks, phase1_max_num=phase1_max_num)
attacks_with_proba_equals_to_1 = [
(attack, proba) for attack, proba in next_attacks if proba == 1]
if len(next_attacks) == 0 or len(attacks_with_proba_equals_to_1) == len(next_attacks):
# How do we set gain for win?
descendant_entropy = 10
else:
# Skip can be chosen after success of attacks
next_attacks.append((None, None))
_, descendant_entropy = maximize_entropy(attacks_with_proba=next_attacks,
candidate_hands_list=filtered, opponents=opponents_sim,
player=player, opened_cards=opened_cards, new_card=new_card,
history=history, depth=depth+1, phase1_max_num=phase1_max_num)
entropy_gain = calculate_entropy_gain(
p=p, descendant_entropy=descendant_entropy, entropy_opened=entropy_opened)
if max_gain < entropy_gain:
max_gain = entropy_gain
max_attacks = [(attack, p)]
elif abs(max_gain-entropy_gain) < 0.0001:
max_attacks.append((attack, p))
print("> "*depth+f"{max_attacks} {max_gain} (depth={depth})")
return max_attacks, max_gain
def calculate_entropy_gain(p, descendant_entropy, entropy_opened):
if p == 1:
return descendant_entropy
return p * (- np.log(p) + descendant_entropy) + \
(1-p)*(-np.log(1-p) - entropy_opened)
実験
まずBaselineの$\epsilon$-greedyの$\epsilon$をによって勝率がどう変わるかを調べ、$\epsilon$の値を決めます。(Experiment 1)
次に、$\epsilon$-greedyと提案手法を複数回戦わせて勝率を出し、どちらが強いロジックかを検証します。(Experiment 2)
シミュレーションする際は、先手と後手による影響があると思うので、先手後手の割合は等しくなるように調整します。
結果
Experiment 1 (Baseline vs Baseline)
$\epsilon$の値は0, 0.1, 0.5, 1.0の4つから選ぶことにします。
小さい方に偏らせているのは、少し試した感じ小さい値の方が体感強かったからです。
ゲームのルールから言っても、基本的にアタックする方が得なことが多い気がします。
先手×後手の4通り×4通りの16通りに対して100回ずつ対戦させて、先手の勝率をまとめた表がこちらです。
| 先手\後手 | 0 | 0.1 | 0.5 | 1.0 | 平均 |
|---|---|---|---|---|---|
| 0 | 0.6 | 0.48 | 0.6 | 0.77 | 0.61 |
| 0.1 | 0.55 | 0.49 | 0.59 | 0.82 | 0.69 |
| 0.5 | 0.44 | 0.48 | 0.47 | 0.85 | 0.56 |
| 1.0 | 0.28 | 0.25 | 0.12 | 0.54 | 0.30 |
| 平均 | 0.47 | 0.43 | 0.45 | 0.75 |
先手でも後手でも、$\epsilon=0.1$のときが勝率が最大であるという結果になりました。
(わかりづらいですが、一番下の行は後手の(1-勝率)となっています)
わかりやすく書くと
| 0 | 0.1 | 0.5 | 1.0 | 平均 | |
|---|---|---|---|---|---|
| 先手 | 0.61 | 0.69 | 0.56 | 0.30 | 0.54 |
| 後手 | 0.53 | 0.57 | 0.55 | 0.25 | 0.48 |
全体的に先手の方が勝率が高いですが、先手の方が有利なんでしょうか？
同じ$\epsilon$同士で対戦している対角線上の勝率を見ても先手の勝率が0.6,0.49, 0.47, 0.54 と全体的に高めです。
というわけで、実験の結果から、全くスキップしないよりちょっとだけスキップするのが少なくとも$\epsilon$-greedy同士の対戦においては強いことがわかりました。Baselineの代表は$\epsilon$-greedy($\epsilon=0.1$)に決まりです。
Experiment 2 (Baseline vs 提案手法)
先ほどの実験で一番勝率の高かった$\epsilon$-greedy($\epsilon=0.1$)と、提案手法を、先手後手を入れ替えてそれぞれ50回ずつ対戦させて勝率を計算しました。
その結果がこちらです。
| $\epsilon$-greedy($\epsilon=0.1$) | 提案手法 | |
|---|---|---|
| 先手 | 0.46 | 0.54 |
| 後手 | 0.46 | 0.54 |
先手でも後手でも、変わらず提案手法の勝率が54%と$\epsilon$-greedyに勝ち越しています。
この差が有意な差なのかを検定してみます。
帰無仮説 $H0$：$P=P0 (=0.5)$
対立仮説 $H1$：$P\gt P0$
と設定すると、
$u0=\frac{r−P0}{\sqrt{\frac{P0(1−P0)}{n}}}$
が棄却域$R$に入っていれば帰無仮説$H0$は棄却され、対立仮説$H1$が採択されます。
ここで、$r$は勝率、$n$は対局数で、有意水準$\alpha=0.05$とすると
$u0=\frac{r−P0}{\sqrt{\frac{P0(1−P0)}{n}}}=0.8 \lt 1.64$
となって帰無仮説は棄却できませんでした。
もう少し勝率に差がないと統計的に有意とは言えないようです。
考察
軽く考察をすると、$\epsilon$-greedyも既にある程度いいアルゴリズムなので、運も大きく影響するアルゴでは勝率に統計的に有意なレベルで差が出る所までいかなかったのではと考えています。
提案手法がとったアクションと並行して確率最大化のアクション戦略($\epsilon$-greedyがアタックする時と同じ戦略)がとったアクションを見ると、スキップする以外はほぼ同じ行動を取っていることがわかり、提案手法と$\epsilon$-greedyはスキップするタイミングが大きな違いと言えます。
提案手法はスキップを一試合に一度するかしないかと言ったレベルで行っており、そこまで提案手法と取るアクションが変わる部分が少ないことからも、戦略が勝率に与える影響の限界が思ったより小さいのかも、と考えています。
そう考えると、100回の試行回数で少しですが勝ち越しているのは、有意とは言えないまでもある程度改善していると言えるのではないでしょうか。
おわりに
今回はアルゴにおける行動選択アルゴリズムを、平均情報量をベースにした指標を最大化するという方針で考案し、実装と実験を行いました。
勝率に統計的に有意な差までは見られませんでしたが、運が大きく絡むアルゴというゲームにおいて戦略の差が勝率に与える影響としてはこの程度でも十分かもしれません。
Future Workとしては、アルゴリズムの高速化まわりが課題です。
コードももう少し綺麗にできそうです。
とりあえず実装はGitHubで公開していますが、pyproject.tomlすら使わずに書き殴ったので、長期的に研究するならもう少し整備しないとですね。。。
作ったアルゴリズムと人間がCLIで対戦できるスクリプトも書けたので、定期的に遊べて楽しいです。普通に人間だとアタックの成功確率の計算すらしんどいので、Baselineの$\epsilon$-greedyにすらかなり負ける印象です。Baselineを強く設定しすぎましたね。
最後までお読みいただきありがとうございました！