2017-12-02

ババ抜き、奇数枚の人勝ちやすい説を検証

UTAP advent calender 2日目の記事です。

当初は音声+ディープラーニング系でなにか書こうかなと思ってたんですが、面白いネタが思い浮かばなかったのと、気付いたら投稿日当日になっていて時間がヤバかったので、全く違う内容になりました。(現在12/2 1:30)

この記事の趣旨

ババ抜きというかの有名なトランプのゲームがあります。始めに参加者に均等に配り、一枚ずつ他者から抜き取り同じ札があれば捨て、最後にジョーカーを持っている人が負けという極めてシンプルなゲームです。

しかし、トランプの枚数は52 + 1枚で素数なため、均等に配るとはいえ全ての参加者に同じ枚数だけ配ることは不可能です。つまり最初の枚数で必ず1枚の差が生じます。

この時、奇数枚であれば最後は1枚になるので前の人に引かれれば無条件で上がれますが、偶数枚だと最後ペアが出来ないと上がれないので、奇数枚の方が有利なんじゃないかという気がします。ので実際にシミュレーションして奇数枚の人は本当に有利なのか？有利だとしてどれくらい勝率が変わるのか？というのを検証していきたいというのが今回の趣旨です。

もし奇数枚が本当に有利なのであれば、毎回トランプを配るという役を引き受けて、ランダムに配るフリをしてこっそり自分の手札は必ず奇数枚になるようにすれば勝率が上がることになります。トランプを配るのは普通面倒くさいので、率先して配る人がいてもきっと誰も文句を言わないでしょう。

ソースコードとその説明

シミュレーションに用いたコードについて説明します。python3で書かれています。興味ない人は読み飛ばしてください。

まず、トランプのカードのクラスを定義します。

class Card(object):
    suits = ['spade', 'club', 'heart', 'diam']

    def __init__(self, suit, number=1):
        self.suit = suit
        assert suit in self.suits or suit == 'JOKER'
        self.number = number
        assert 1 <= number <= 13 or number is None

    def __repr__(self):
        return '{}_{}'.format(self.suit, self.number) if self.suit != 'JOKER' else 'JOKER'

    def __eq__(self, other):
        return self.suit == other.suit and self.number == other.number

    def __hash__(self):
        return hash(self.number) + hash(self.suit)

__repr__や__eq__はpythonの特殊メソッドで、__repr__はprint関数によって呼び出した時の出力を指定でき、__eq__はインスタンス同士の比較演算子==の挙動を定義できます。 __ne__は!=です。通常セットで定義します。

次に、ババ抜きに参加するプレイヤーのクラスを定義します。

class Agent(object):

    def __init__(self, index):
        self.index = index
        self.cards = set()
        self.next_ = None
        self.prev_ = None

    def draw(self, card):
        for c in self.cards:
            if card.number == c.number:
                self.cards.remove(c)
                break
        else:
            self.cards.add(card)

    def drawn(self):
        assert len(self.cards)
        card_ = random.sample(self.cards, 1)
        card = card_[0]
        self.cards.remove(card)
        return card

    def empty(self):
        return len(self.cards) == 0

    def __repr__(self):
        return 'Player_{}'.format(self.index)

カードを引く動作、引かれる動作、などの関数を用意しています。next_, prev_にはカードを引く人と引かれる人のインスタンスが代入されます。便宜上ゲームに参加するプレイヤーには1人ずつ0から順にindexを割り当てます。

次に1ゲームを行うクラスを定義します。

class Game(object):

    __BEGIN__ = 0
    __PLAYING__ = 1
    __END__ = 2

    def __init__(self, n_people, verbose=False, serve_randomly=True, begin_randomly=True):
        """
        Parameters
        ----------
        n_people: 参加人数
        verbose
        serve_randomly : 配り始める位置をランダムにするか0からにするか
        begin_randomly : ターンを始める位置をランダムにするか0からにするか
        """
        self.n_people = n_people
        self.agents = [Agent(index=i) for i in range(n_people)]
        for i in range(n_people):
            if i == 0:
                self.agents[i].prev_ = self.agents[n_people - 1]
            else:
                self.agents[i].prev_ = self.agents[i - 1]

            if i == n_people - 1:
                self.agents[i].next_ = self.agents[0]
            else:
                self.agents[i].next_ = self.agents[i + 1]

        self.results = []
        self.now_agent = None
        self.status = self.__BEGIN__
        self.verbose = verbose
        self.serve_randomly = serve_randomly
        self.begin_randomly = begin_randomly

    def serve_cards(self):
        cards = []
        for suit in Card.suits:
            for number in range(1, 14):
                cards.append(Card(suit, number))
        cards.append(Card('JOKER'))

        random.shuffle(cards)

        if self.serve_randomly:
            now_agent = random.sample(self.agents, 1)[0]
        else:
            now_agent = self.agents[0]

        for card in cards:
            now_agent.draw(card)
            now_agent = now_agent.next_

        for i in range(self.n_people):
            if now_agent.empty():
                self.win_out(now_agent)
            now_agent = now_agent.next_

    def transaction(self):
        if len(self.agents) == 1:
            self.results.append(self.agents[0].index)
            self.status = self.__END__
            return

        card = self.now_agent.next_.drawn()
        if self.now_agent.next_.empty():
            self.win_out(self.now_agent.next_)

        self.now_agent.draw(card)
        if self.now_agent.empty():
            self.win_out(self.now_agent)

        self.now_agent = self.now_agent.next_

        self.status = self.__PLAYING__
        return

    def win_out(self, agent):
        if self.verbose:
            print('{} win!'.format(agent))
        agent.prev_.next_ = agent.next_
        agent.next_.prev_ = agent.prev_
        self.results.append(agent.index)
        self.agents.remove(agent)

    def play(self):
        self.serve_cards()

        # start!
        if self.begin_randomly:
            self.now_agent = random.sample(self.agents, 1)[0]
        else:
            self.now_agent = self.agents[0]

        self.status = self.__PLAYING__

        turn = 1
        while self.status != self.__END__:
            self.transaction()
            if self.verbose:
                print('turn:{} agent:{}'.format(turn, self.now_agent))
                self.dump_game_status()

            turn += 1

        self.dump_results()

    def dump_results(self):
        print('-'.join(map(str, self.results)))

    def dump_game_status(self):
        print('---------')
        for agent in self.agents:
            print('{}: {}'.format(agent, agent.cards))

まあまあ長い。配り方は1枚ずつ時計回りで配っていくと仮定しています。ここで、配り始めの人をplayer(index=0)に固定するかランダムにするか、カードを引き合うフェイズに入った時に最初にカードを引き始める人をplayer(index=0)に固定するかをパラメータとして与えることができます。

7人で配り始めを固定してゲームを行う例です。

game = Game(
    n_people=7,
    serve_randomly=False,
    begin_randomly=True
)
game.play()
print(game.result)

オブジェクト指向言語はこういうのが直感的に書けるので好きです。

結果

奇数枚有利説

参加人数を5人〜10人の場合についてそれぞれ10000ゲーム行い、奇数枚の人と偶数枚の人の1位抜け率とビリ率を算出しました。

参加人数	奇数枚	偶数枚	奇数枚の1位率平均	偶数枚の1位率平均	奇数枚のビリ率平均	偶数枚のビリ率平均
5人	3人	2人	0.2458	0.1313	0.1753	0.2369
6人	5人	1人	0.1833	0.0835	0.1579	0.2101
7人	3人	4人	0.2199	0.085	0.1029	0.1728
8人	5人	3人	0.157	0.0716	0.1045	0.1591
9人	1人	8人	0.2801	0.0899	0.0433	0.1195
10人	7人	3人	0.1273	0.0361	0.0832	0.1391

全ての人数において、1位率、ビリ率共に奇数枚が有利な結果になっているように見えます。特に奇数枚が1人である参加人数: 9人の場合においては、偶数枚の人に対して1位率が3倍ほどにもなっています。

プレイヤー $i$ の1位抜け数を $X_i$ 、ゲーム数を $k = 10000$ 、プレイヤー人数を $n$ とし、各プレイヤーの勝率 $p_i$ に対して

$\displaystyle H_0 : p_1 = p_2 = ... = \frac{1}{n}$

$\displaystyle H_1 : not \,\, p_1 = p_2 = ... = \frac{1}{n}$

として、有意水準5%で検定をします。

プレイヤーの勝率が $H_0$ に従うとすると

f:id:sumsum88:20171202131004p:plain:w150

とすると、この値は漸近的に自由度 ${n-1}$ のカイ二乗分布に従うので、これを検定統計量として、

f:id:sumsum88:20171202130334p:plain:w130

が成立すれば、帰無仮説 $H_0$ は棄却されます。

試しに $n = 5$ の場合でscipyのchisquareという関数を使って検定を行うと、

>>> from scipy.stats import chisquare

>>> x = [2546, 2428, 2400, 1285, 1341]

>>> k = 10000

>>> n = 5

>>> chisquare(f_obs=x, f_exp=[k/ n ] * n)
Power_divergenceResult(statistic=793.40300000000002, pvalue=2.0619817457860561e-170)

pvalue < 0.05であるので、 $H_0$ は棄却されます。同様にn = 6 ~ 10についても、棄却されます。茶番

n	pvalue
5	2.06e-170
6	3.60e-108
7	0.0
8	1.41e-233
9	0.0
10	0.0

少し細かくプレイヤーの順位分布を見てみます。下の図は10000回中の各プレイヤーの各順位の数をカラーマップ化したものです。明るいほど数が大きいことを表します。カードはプレイヤー1、プレイヤー2... の順に1枚ずつ配っていくとしています。カードを引くときはプレイヤーnがプレイヤーn+1の手札から引きます。縦軸がプレイヤー、横軸が順位です。

f:id:sumsum88:20171202110333p:plain

これを見ると、奇数枚プレイヤーの中でも、前の人が偶数枚プレイヤーであるプレイヤーはより有利になっていることが見て取れます(参加人数5人、7人の時に顕著)。前の人が上がると、そのターンはカード引いてもらえなくなるため、自分の手札の偶奇が入れ替わります。そのため、せっかく奇数枚でも前の人に上がられると偶数枚になってしまうのです。つまり奇数枚の場合は、前の人に早く上がられない方が強い = 前の人が偶数枚プレイヤーである奇数枚プレイヤーはより有利、と考えられます。逆に言えば、前の人が奇数枚プレイヤーである偶数枚プレイヤーは偶数枚プレイヤーの中では比較的有利であることが参加人数: 8人、10人の場合に現れています。

引き始めが早い人有利説

ついでに、引き始めの順番で勝率が変わるのかというのも検証しました。通常ここはじゃんけんなどで決まることが多いため、意図的な調整は厳しいですが、あくまで参考までに。同じく参加人数5人〜10人の場合についてそれぞれ10000ゲーム行っています。青線が1位、橙線がビリになった数です。 f:id:sumsum88:20171202120836p:plain

最初に引く人は単純に枚数が1枚多くなるので、不利になる傾向があります。最初に引かれる人が一番有利なようです。ただし9人の場合の時のみ、最初に引く人が圧倒的に勝率が高いという結果が得られました。これはおそらく、9人の場合はほとんどの人(8人)が偶数のため、初めに引くと奇数になって有利になるのではないでしょうか。

まとめ・展望

手札が奇数枚のプレイヤーは有利であることがわかった
友達とババ抜きをやるときは、積極的にカードを配る役に回ろう
引き始めの順番を決めるじゃんけんでは、自分の前の人に勝ってもらおう

人数や奇数枚 : 偶数枚の人数比と勝率の関係を時間的にあまり詳しく考察できなかったので、暇な時に考えたいと思います。ババ抜きはクソゲー。

ソースコードはgithubに上げてあります。

github.com

2017-09-21

ヌメロンのAI作った

ブログに慣れるのも兼ねて、以前作ったコマンドラインで遊べるヌメロンを紹介します。

・ヌメロンって何

簡単にいうと数当てゲームみたいな感じ。基本ルールは以下。

Numer0n - Wikipedia

それぞれのプレイヤーが、0-9までの数字が書かれた10枚のカードのうち3枚を使って、3桁の番号を作成する。カードに重複は無いので「550」「377」といった同じ数字を2つ以上使用した番号は作れない。
先攻のプレイヤーは相手の番号を推理してコールする。相手はコールされた番号と自分の番号を見比べ、コールされた番号がどの程度合っているかを発表する。数字と桁が合っていた場合は「EAT」（イート）、数字は合っているが桁は合っていない場合は「BITE」（バイト）となる。
- 例として相手の番号が「765」・コールされた番号が「746」であった場合は、3桁のうち「7」は桁の位置が合致しているためEAT、「6」は数字自体は合っているが桁の位置が違うためBITE。EATが1つ・BITEが1つなので、「1EAT-1BITE」となる。
これを先攻・後攻が繰り返して行い、先に相手の番号を完全に当てきった（3桁なら3EATを相手に発表させた）プレイヤーの勝利となる。

今回は多少一般化して、n文字の中からm文字を使って、m桁の文字列を作成できることにする。

例えば、16進数(0-9, A-F)から5文字選ぶとすると"369AF"のような文字列を当てるゲームになる。

・ゲーム例

ルール: 10進数、3桁

自分 (345) 相手 (157)

自分「129」相手「1E0B」

相手「035」自分「1E1B」

自分「567」相手「1E1B」

相手「024」自分「0E1B」

自分「256」相手「1E0B」

相手「532」自分「1E1B」

自分「157」相手「3E0B」

自分の勝利！！！

・CPU側のアルゴリズム

いかに早く答えの候補を絞り込めるかが重要となる。それにはいかに相手から情報を得るか、情報を得るための番号をコールするかが肝である。

自分が番号をコールすることで候補がp倍に絞られる時、このpの値が小さければ小さいほど良い情報が得られたことになる。ここで選択情報量という概念を考える。

情報量 - Wikipedia

$I(E)=\log {\frac {1}{P(E)}}=-\log P(E)$

選択情報量の平均（エントロピー）を考える。

$H(P)=-\sum _{A\in \Omega }P(A)\log P(A)$

ここでの $\Omega$ は考えられうる相手の発表の集合( ex. 0E0B, 0E1B, ...) で、 $A$ はその要素である。 $P(A)$ は現時点での解答の候補が同様に確からしいと考えた時に $A$ という発表が返ってくる確率である。

これを最大化するコールを考える。実装上は計算量の関係で解答候補が多すぎる場合のエントロピーの計算を簡略化しています。（もっとうまくやりたい）

・プログラム

まず、基本となる処理を記述。

CHARSで使う文字、DIGITで文字数を指定している。

common.py

#!/usr/bin/env python
# coding: utf-8


from collections import Counter
import numpy as np


CHARS = '1234567890'
DIGITS = 5


class Judge(object):

    eat = 0
    bite = 0

    def __repr__(self):
        return 'eat: {}, bite: {}'.format(self.eat, self.bite)

    def __eq__(self, other):
        return self.eat == other.eat and self.bite == other.bite

    def __ne__(self, other):
        return not (self.eat == other.eat and self.bite == other.bite)

    def __hash__(self):
        return self.eat * 1e4 + self.bite


def coincidence(n1, n2):
    """
    n1とn2の一致度を測る
    """
    j = Judge()
    for i, n in enumerate(n1):
        if n == n2[i]:
            j.eat += 1
        elif n in n2:
            j.bite += 1
    return j


def is_valid_number(number, digits, chars):
    if len(number) != digits:
        return False
    if len(number) != len(set(number)):
        return False
    for v in number:
        if not v in chars:
            return False
    else:
        return True


def entropy(num, num_list):
    """
    num_listが答えの候補である時にnumをcallすることで得られる情報量

    Parameters
    ----------
    num : list(str)
    num_list : list(list(str))

    Returns
    ----------
    entropy: list(int)

    """
    n = len(num_list)
    j_list = [coincidence(num_, num).__hash__() for num_ in num_list]
    counter = Counter(j_list)
    pr = [x * 1.0 / n for x in counter.values()]

    return sum(map(lambda p: p * -np.log2(p), pr))

AIの実装

agent.py

#!/usr/bin/env python
# coding: utf-8


from itertools import permutations
from numpy.random import shuffle
from random import choice
import copy
from common import *


class NumeronAgent(object):
    """
    Numeron Player(AI)
    """

    def __init__(self, number=None):
        self.candidate = [''.join(i) for i in permutations(CHARS, DIGITS)]
        if number is None:
            number = choice(self.candidate)

        if type(number) in [str, int]:
            number = list(str(number))

        self.number = number
        self.turn = 1
        assert len(number) == DIGITS
        self.all_candidate = copy.deepcopy(self.candidate)

    def reply_coincidence(self, opponent_call_number):
        """
        相手の宣言した数字に対し、eatとbiteの数を返す

        Parameters
        ----------
        opponent_call_number : list(str) 相手の宣言した数字

        Returns
        -------
        Judge eatとbiteの数

        """
        return coincidence(self.number, opponent_call_number)

    def decide_call_number(self, max_num=1000):
        """
        次の宣言する数字を決める

        Parameters
        ----------
        max_num : int 探索数

        Returns
        -------
        call_number : list(str) 最もエントロピーが高くなる数字

        """
        if self.turn > 1:
            shuffle(self.candidate)

            if len(self.candidate) <= max_num:
                array = self.candidate + self.all_candidate[:max_num - len(self.candidate)]
            else:
                shuffle(self.all_candidate)
                array = self.all_candidate[:max_num]

            entropy_list = map(lambda x: entropy(x, self.candidate[:max_num]), array)
            call_number = array[np.argmax(entropy_list)]

        else:
            call_number = choice(self.candidate)
        print('call number: {}'.format(call_number))
        return call_number

    def update_candidate(self, judge, call_number):
        """
        候補を更新

        Parameters
        ----------
        judge : Judge 今回のeatとbite
        call_number : list(str) 今回の宣言した数字

        """
        self.candidate = filter(lambda x: coincidence(
            x, call_number) == judge, self.candidate)

    def action(self, opponent):
        """
        1ターンの一連のアクションを行う

        Parameters
        ----------
        opponent : NumeronAgent

        """
        call_number = self.decide_call_number()
        j = opponent.reply_coincidence(call_number)
        print(j)
        if j.eat == DIGITS:
            print('WIN!!!')
            exit()
        self.update_candidate(j, call_number)
        print('candidate: {}'.format(len(self.candidate)))
        self.turn += 1


class NumeronHumanAgent(NumeronAgent):
    """
    Numeron Player(人間)
    """

    def __init__(self):
        number = self.input_number('please set your number (digits = {}): '.format(DIGITS))
        assert len(number) == DIGITS
        NumeronAgent.__init__(self, number)

    def input_number(self, message):
        while True:
            number = list(raw_input(message))
            if is_valid_number(number, DIGITS, CHARS):
                return number
            else:
                print('invalid number')

    def decide_call_number(self, max_num=1000):
        number = self.input_number('call number: ')
        assert len(number) == DIGITS
        return number

main.py

#!/usr/bin/env python
# coding: utf-8

from agent import NumeronAgent, NumeronHumanAgent


class Game(object):
    """
    Numeron対戦用クラス
    """

    def __init__(self, player1, player2):
        self.player1 = player1
        self.player2 = player2

    def main(self):
        nof_turns = 1
        while True:
            print('---------- Turn {} ----------'.format(nof_turns))
            print('---- pleyer1\'s turn ----')
            player1.action(player2)
            print('---- pleyer2\'s turn ----')
            player2.action(player1)
            nof_turns += 1


if __name__ == '__main__':
    player1 = NumeronHumanAgent()
    player2 = NumeronAgent()

    game = Game(player1, player2)
    game.main()

強さは自分と互角くらいでした。まあ運もあるのでわかんないですけど。桁数が多くなってくると叶わなくなります。

ただゲームの性質上これ以上強くなり得るのだろうか・・特殊ルールが入ってきたら変わってくるかも。

暇な人は試してみてください。