بتل کد Battle Codeدارد باز می‌شود…

جواب «Step 6: The Learned Strategy» چالش 6 از جلسه‌ی 61

سؤال

قدم ۶: برای هر تعداد چوب از ۱ تا ۱۰، بهترین حرکت عامل (choose(s, 0.0)) را چاپ کن. اگر s مضرب ۴ بود بنویس 4 sticks: take 1 (no safe move)، وگرنه مثل 10 sticks: take 2 -> leaves 8، و بشمار چند حرکت مضربی از ۴ باقی می‌گذارند. خروجی، بعد از خط‌های قدم‌های قبل، باید این باشد:
1 sticks: take 1 -> leaves 0
2 sticks: take 2 -> leaves 0
3 sticks: take 3 -> leaves 0
4 sticks: take 1 (no safe move)
5 sticks: take 1 -> leaves 4
6 sticks: take 2 -> leaves 4
7 sticks: take 3 -> leaves 4
8 sticks: take 1 (no safe move)
9 sticks: take 1 -> leaves 8
10 sticks: take 2 -> leaves 8
leaves a multiple of 4: 8 of 8

راهنما

if s % 4 == 0: برای «no safe move»، وگرنه چاپ s - best و اگر (s - best) % 4 == 0 بود found += 1. صفر هم مضرب ۴ است!

یک جواب درست

import random

START = 10


def moves(sticks):
    return [t for t in (1, 2, 3) if t <= sticks]


def play_game(first, second):
    sticks = START
    players = [first, second]
    turn = 0
    while True:
        t = players[turn](sticks)
        sticks = sticks - t
        if sticks <= 0:
            return turn
        turn = 1 - turn


def take_one(sticks):
    return 1


def take_most(sticks):
    return max(moves(sticks))


print(moves(10), moves(2), moves(1))
print("winner:", play_game(take_one, take_most))


def random_player(sticks):
    return random.choice(moves(sticks))


random.seed(1)
wins = [0, 0]
for g in range(1000):
    wins[play_game(random_player, random_player)] += 1
print("random vs random:", wins)


Q = {}
for s in range(1, START + 1):
    for t in moves(s):
        Q[(s, t)] = 0.0


def choose(sticks, epsilon):
    if random.random() < epsilon:
        return random.choice(moves(sticks))
    best = moves(sticks)[0]
    for t in moves(sticks):
        if Q[(sticks, t)] > Q[(sticks, best)]:
            best = t
    return best


print("Q-table size:", len(Q))
Q[(7, 3)] = 0.8
print("greedy at 7:", choose(7, 0.0), "| greedy at 5:", choose(5, 0.0))
Q[(7, 3)] = 0.0


def play_episode(epsilon, agent_first):
    sticks = START
    history = []
    agent_turn = agent_first
    while True:
        if agent_turn:
            t = choose(sticks, epsilon)
            history.append((sticks, t))
        else:
            t = random_player(sticks)
        sticks = sticks - t
        if sticks == 0:
            reward = 1 if agent_turn else -1
            return reward, history
        agent_turn = not agent_turn


def learn(history, reward, lr):
    for key in history:
        Q[key] += lr * (reward - Q[key])


random.seed(4)
reward, history = play_episode(0.2, True)
print("reward:", reward, "| agent moves:", history)
learn(history, reward, 0.5)
print("after learning:", [Q[key] for key in history])


def win_rate(games):
    wins = 0
    for g in range(games):
        reward, history = play_episode(0.0, g % 2 == 0)
        if reward == 1:
            wins += 1
    return wins / games


for key in Q:
    Q[key] = 0.0
random.seed(3)
print("before training:", win_rate(1000))
for g in range(5000):
    reward, history = play_episode(0.3, g % 2 == 0)
    learn(history, reward, 0.05)
print("after training:", win_rate(1000))


found = 0
for s in range(1, START + 1):
    best = choose(s, 0.0)
    if s % 4 == 0:
        print(s, "sticks: take", best, "(no safe move)")
    else:
        print(s, "sticks: take", best, "-> leaves", s - best)
        if (s - best) % 4 == 0:
            found += 1
print("leaves a multiple of 4:", found, "of 8")

اول خودت امتحان کن؛ جواب‌های دیگر هم قبول است. برگرد و خودت حلش کن