1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@ngktakanobu(Takanobu Saito)

横棒の数が少なくても公平なあみだくじを作る in Python

1
Posted at

あみだくじの偏りの原因

　「ホンマでっか!?TV」というフジテレビの番組で、あみだくじで「一番当たる確率が高いのは当たりの真上である」という説が開陳されていました。
　確かに人間が作るあみだくじは視覚的・心理的な理由で、当たりの確率に大きな偏りがあるようです。
　ところが「あみだくじ　確率」などと検索すると、プログラムで生成したあみだくじにも偏りがあるという主張やサンプルプログラムがあふれています。生成AIに聞いても同じように主張してきます。

『ホンマでっか！？』

と深掘りしたところ、そうしたプログラムは偏ったあみだくじを生成するアルゴリズムを使っているので偏っている(当たり前)ということが判明しました。それなら偏らないあみだくじを生成するプログラムを作ってみましょう。

偏ったあみだくじを作るプログラム

　偏ったあみだくじを作るプログラムは巷にあふれています。基本的に縦棒の間に横棒をランダムに配置するというアルゴリズムを使っています。普通に考えればそうなりますね。典型的なPythonプログラムは以下のようになります。

偏ったあみだくじを作るプログラム(▶をクリック) 
import random

def makeamida(numcolumn: int, numbar: int, p=0.5):
    '''
    Args
    ----------
    numcolumn:int 縦線の数
    numbar:int 横線の数、必ず縦線の数より大きい

    Returns
    ----------
    縦線の左側をx座標(0～numcolumn-2)、横線をｙ座標(0～numbar-1)で表す横線の座標のtupleのリスト。
    (x,y)から(x+1,y)に横線が引かれる。
    見た目が悪いので同じy座標に横線が複数あっても良いが、必ずｘ座標は異なっていること。
    縦線の間には必ず一つは横線があること。
    同じ横線が重複しない(x,y座標が同じ線は却下)。
    '''
    bars = []

    for y in range(numbar):
        xs = []
        x = 0

        while x < numcolumn - 1:
            if random.random() < p:
                xs.append(x)
                x += 2  # 隣接禁止
            else:
                x += 1

        # 1本も無い場合はランダムに1本追加
        if not xs:
            xs.append(random.randint(0, numcolumn - 2))

        for x in xs:
            bars.append((x, y))

    return bars

def goal(amida, hit: int, numcolumn: int):
    '''
    hit(0～numcolumn-1)を指定すると、hitに至るstart位置を返す。
    Args
    ----------
    amida:  tupleのリスト(あみだくじデータ)
    hit:int 当たりのx座標

    Return
    ----------
     当たりのスタートx座標
    '''
    if not (0 <= hit < numcolumn):
        raise ValueError("hit must be in 0 <= hit < numcolumn")

    bars_by_y = {}

    for x, y in amida:
        bars_by_y.setdefault(y, set()).add(x)

    for start in range(numcolumn):
        x = start

        for y in sorted(bars_by_y.keys()):
            xs = bars_by_y[y]

            if x in xs:
                x += 1
            elif x - 1 in xs:
                x -= 1

        if x == hit:
            return start

    raise RuntimeError("No start position reaches hit")

def evalamida(numcolumn: int, hit: int, trynum: int):
    '''
    Args
    ----------
    numcolumn:int 縦線の数
    hit:int 当たりのx座標
    trynum:int 試行数

    Return
    ----------
     当たりのスタートx座標
    '''
    if numcolumn < 2:
        raise ValueError("numcolumn must be >= 2")
    if not (0 <= hit < numcolumn):
        raise ValueError("hit must be in 0 <= hit < numcolumn")
    if trynum <= 0:
        raise ValueError("trynum must be >= 1")

    count = [0] * numcolumn

    for _ in range(trynum):
        numbar = random.randint(numcolumn + 1, numcolumn * 5)
        amida = makeamida(numcolumn, numbar)

        start = goal(amida, hit, numcolumn)
        count[start] += 1

    return [c / trynum for c in count]


if __name__ == "__main__":
    result = evalamida(numcolumn=8, hit=0, trynum=10000)

    for start, p in enumerate(result):
        print(f"start {start}: {p:.4f}")

　実行している"evalamida(numcolumn=8, hit=0, trynum=10000)"は、縦棒が8本あるあみだくじをランダムに生成して、当たりが一番左"0"の時の、縦棒(0～numcolumn-1)の当たる確率を計算したものです。これで計算すると最も当たる確率が高いのは、確かに当たりの真上の"0"になります。

start 0: 0.2070
start 1: 0.1903
start 2: 0.1626
start 3: 0.1387
start 4: 0.1024
start 5: 0.0813
start 6: 0.0627
start 7: 0.0550

横棒の数が少なくても公平なあみだくじを作るプログラム

　次は、縦棒の位置による確率の偏りも横棒の数も少ないあみだくじの生成プログラムです。ランダムな置換を繰り返すアルゴリズムです。
　縦棒の間には必ず１本の横棒があるバージョンです。素のアルゴリズムでは横棒のない個所の存在するバージョンとなりますが見た目が不自然です。

横棒の数が少ない公平なあみだくじを作るプログラム(▶をクリック) 
import random

def makeamida_uniform_full(numcolumn: int):
    """
    完全ランダムな置換を作り、
    さらに各隣接列の間 x=0～numcolumn-2 に
    最低1本以上の横線が出るようにする。
    """
    if numcolumn < 2:
        raise ValueError("numcolumn must be >= 2")

    # 1. 完全ランダムな置換を作る
    perm = list(range(numcolumn))
    random.shuffle(perm)

    arr = list(range(numcolumn))
    bars = []
    y = 0

    # 2. 隣接交換でその置換を実現する
    for i in range(numcolumn):
        target = perm[i]
        j = arr.index(target)

        while j > i:
            arr[j - 1], arr[j] = arr[j], arr[j - 1]
            bars.append((j - 1, y))
            y += 1
            j -= 1

    # 3. 横線が一度も出ていない「隣接列の間」を調べる
    used_x = {x for x, _ in bars}

    # 4. 足りない x に対して、結果を変えない往復横線を追加
    for x in range(numcolumn - 1):
        if x not in used_x:
            bars.append((x, y))
            y += 1
            bars.append((x, y))
            y += 1

    return bars

def goal(amida, hit: int, numcolumn: int):
    '''
    hit(0～numcolumn-1)を指定すると、hitに至るstart位置を返す。
    Args
    ----------
    amida:  tupleのリスト(あみだくじデータ)
    hit:int 当たりのx座標

    Return
    ----------
     当たりのスタートx座標
    '''
    if not (0 <= hit < numcolumn):
        raise ValueError("hit must be in 0 <= hit < numcolumn")

    bars_by_y = {}

    for x, y in amida:
        bars_by_y.setdefault(y, set()).add(x)

    for start in range(numcolumn):
        x = start

        for y in sorted(bars_by_y.keys()):
            xs = bars_by_y[y]

            if x in xs:
                x += 1
            elif x - 1 in xs:
                x -= 1

        if x == hit:
            return start

    raise RuntimeError("No start position reaches hit")

def evalamida(numcolumn: int, hit: int, trynum: int):
    '''
    Args
    ----------
    numcolumn:int 縦線の数
    hit:int 当たりのx座標
    trynum:int 試行数

    Return
    ----------
     当たりのスタートx座標
    '''
    if numcolumn < 2:
        raise ValueError("numcolumn must be >= 2")
    if not (0 <= hit < numcolumn):
        raise ValueError("hit must be in 0 <= hit < numcolumn")
    if trynum <= 0:
        raise ValueError("trynum must be >= 1")

    count = [0] * numcolumn

    for _ in range(trynum):
        amida = makeamida_uniform_full(numcolumn)

        start = goal(amida, hit, numcolumn)
        count[start] += 1

    return [c / trynum for c in count]


if __name__ == "__main__":
    result = evalamida(numcolumn=8, hit=0, trynum=10000)

    for start, p in enumerate(result):
        print(f"start {start}: {p:.4f}")

　"makeamida_uniform_full"で計算してみると、あみだくじの偏りがなくなります。
　ランダムに横棒を配置するアルゴリズムでは偏ったあみだくじができて、ランダムに置換を生成するアルゴリズムでは公平なあみだくじができるという訳です。

start 0: 0.1313
start 1: 0.1218
start 2: 0.1255
start 3: 0.1282
start 4: 0.1227
start 5: 0.1202
start 6: 0.1243
start 7: 0.1260

目視で確認

　最初の偏りありのアルゴリズムでも横棒が多いと偏りは少なくなります。不自然に横棒の数が多くないかなどを目視で確認してみます。あみだくじのpritty printプログラムを今までのプログラムと合わせて実行します。

あみだくじのpretty print(▶をクリック) 
def print_amida(amida, numcolumn: int):
    """
    あみだくじをASCIIで表示する

    例：
    |   |---|   |
    |---|   |---|
    |   |   |   |
    """

    # yごとの横線を整理
    bars_by_y = {}
    max_y = 0

    for x, y in amida:
        bars_by_y.setdefault(y, set()).add(x)
        max_y = max(max_y, y)

    # 上から順に描画
    for y in range(max_y + 1):
        xs = bars_by_y.get(y, set())

        line = ""
        for col in range(numcolumn):
            line += "|"

            if col < numcolumn - 1:
                if col in xs:
                    line += "---"
                else:
                    line += "   "

        print(line)

    # 下に番号表示
    print(" ".join(f"{i:^3}" for i in range(numcolumn)))

    
if __name__ == "__main__":
    numcolumn = 6

    print("=== makeamida (偏りあり) ===")
    amida1 = makeamida(numcolumn, 10)
    print_amida(amida1, numcolumn)

    print("\n=== makeamida_uniform_full (完全ランダム置換) ===")
    amida2 = makeamida_uniform_full(numcolumn)
    print(amida2)
    print_amida(amida2, numcolumn)

　以下のようにmakeamida_uniform_fullで作られるあみだくじの横棒の数は少ないことが分かります。繰り返して実行するたびに別のあみだくじを見ることができます。

=== makeamida (偏りあり) ===
|---|   |   |---|   |
|   |---|   |   |   |
|---|   |---|   |   |
|---|   |   |   |   |
|   |---|   |---|   |
|   |---|   |---|   |
|---|   |   |---|   |
|---|   |   |---|   |
|   |---|   |---|   |
|---|   |---|   |---|
 0   1   2   3   4   5 

=== makeamida_uniform_full (完全ランダム置換) ===
[(1, 0), (0, 1), (2, 2), (1, 3), (4, 4), (3, 5), (2, 6), (4, 7), (3, 8), (4, 9)]
|   |---|   |   |   |
|---|   |   |   |   |
|   |   |---|   |   |
|   |---|   |   |   |
|   |   |   |   |---|
|   |   |   |---|   |
|   |   |---|   |   |
|   |   |   |   |---|
|   |   |   |---|   |
|   |   |   |   |---|
 0   1   2   3   4   5

公平で横棒の数も少ないあみだくじをプログラムで作ることができました。横棒の数を節約しすぎと思える場合、もう少し横棒の本数を増やしてもいいかもしれません。

1
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?