FEAT:🚩 Daily-AlpacaHack 「RPS GAME」Medium

20260605-daily_alpaca-misc-medium-RPS_GAME

Summary

本問は，ソートアルゴリズムの出力の偏りを用いて，じゃんけんプログラムに対する自手の勝率を6割以上にする問題です．

• Category: Misc
• Description: ✊️️🖐️✌️
• Tools & TechStack:
  • Python
  • Pwntools
• Release: 2026/06/05

階層構造

.
├── compose.yaml
├── Dockerfile
└── game.py

1 directory, 3 files

---

ソースコードの調査

じゃんけんゲームで，ROUNDS = 1000 のうち，TARGET_WIN = ROUNDS * 0.6 = 600 回相手の手に勝てれば ROUND 終了後に FLAG が入手できるようです．

もし，相手が一般的な $\frac{1}{3}$ での完全ランダム手法であった場合，33.3% で手を出すため，こちらがどのような戦略を使用しても期待確率が収束します． そのため，勝率を6割にすることは，理論上は不可能です． しかし，CTFの問題になっているということは何らかの確率の偏りがあるものと考えました．

import random

FLAG = "Alpaca{REDACTED}"
HANDS = ["r", "p", "s"]
ROUNDS = 1000
TARGET_WIN = int(ROUNDS * 0.6)

def shuffle(items):
    return sorted(items, key=lambda _: random.getrandbits(1))

print("ROCK PAPER SCISSORS GAME")
print(f"Win {TARGET_WIN} times in {ROUNDS} rounds.")
print("Hands: r / p / s")

win = 0
hands = HANDS[:]
for i in range(ROUNDS):
    hands = shuffle(hands)
    opponent = hands[0]
    you = input(f"Round {i+1} > ").strip()
    assert you in HANDS, "Invalid hand."
    result = (HANDS.index(you) - HANDS.index(opponent)) % 3
    win += (result == 1)

    print(f"Opponent: {opponent}, You: {you}")
    print(["Draw", "Win!", "Lose..."][result])
    print(f"Win count: {win}\n")

if win >= TARGET_WIN:
    print(f"Wow, you broke the game ... Flag: {FLAG}")
else:
    print("Leave the game.")

sorted() の動作

shuffle() で使用されている sorted()¹ の動作を調べます． このスクリプトでは，サイズが3の配列の各要素に対して，0/1 を割り当て，各要素を比較し，インデックスの先頭から 0<1 となるように整列させます．

• 例: sorted([5, 2, 3, 1, 4]) -> [1, 2, 3, 4, 5]

確率分布の偏り

そこで，リストの一番前にいる要素 (hands[0]) が，ソート後も一番前に残る確率 (これに規則性があれば勝率を上げられるため) を考えました．

3bit サイズでのランダムなビットのパターン ($2^3=8$ 通り) を考えると，確率に偏りが生じていました． これは，sorted() が安定ソート (キーの値が同じ場合は，ソート後も配列が同じ順序を維持する) であることと，hands[] がラウンド毎にリセットされていないためです．

つまり，$\frac {5}{8} = 62.5\%$ の確率で，次のラウンドも r を出してきます． この偏りを加味して，相手の前回の手に勝つ手を出し続ければ，下振れはありますが期待値ベースで 625勝 以上はすることができるはずです．

r	p	s	ソート後	hands[0]
0	0	0	[r, p, s]	r
0	0	1	[r, p, s]	r
0	1	0	[r, s, p]	r
0	1	1	[r, p, s]	r
1	1	1	[r, p, s]	r
1	0	0	[p, s, r]	p
1	0	1	[p, r, s]	p
1	1	0	[s, r, p]	s

確率の偏りを加味したプログラム

solver.py

from pwn import *

# p = remote('34.170.146.252', 45243)
p = process(['python3', './game.py'])

WIN_HANDS = {'r': 'p', 'p': 's', 's': 'r'}

my_hand = 'r' 

for i in range(1000):
    if (i + 1) % 100 == 0:
        print(f"Processing... Round {i+1}/1000")

    p.sendlineafter(b"> ", my_hand.encode())

    # 実際の相手の手を取得 (Opponent: x, You: y)
    p.recvuntil(b"Opponent: ")
    opponent_actual_hand = p.recv(1).decode()

    # 前回の相手の手に勝つ手
    my_hand = WIN_HANDS[opponent_actual_hand]

print("Fetching the FLAG...")
print(p.recvall(timeout=2).decode())

$ python3 solver.py
Processing... Round 100/1000
#...
Processing... Round 1000/1000
Fetching the FLAG...
[+] Receiving all data: Done (84B)
, You: p
Lose...
Win count: 627

Wow, you broke the game ... Flag: Alpaca{REDACTED}

---

Post-Mortem & Dead ends

HackTheBoxのLuckyDiceっていう問題を思い出した…

References

1. Sorting Techniques — Python 3.14.5 documentation ↩︎