3章　やりたいことをプログラムにする

3章 やりたいことをプログラムにする

第2部までで、CHaserのプログラムを書くための道具（移動・繰り返し・条件分岐・探査・変数・関数）は一通りそろいました。ところが、いざ「こう動かしたい」というアイデアが浮かんでも、それをどうやってプログラムにすればよいのかが分からず、手が止まってしまうことがあります。

この章では、アイデアを、動くプログラムにするまでの考え方の手順を学びます。教材には、CHaserの対戦で使える動き（斜めにいる敵への対応、遠くの様子を先に見る、いちばん近い場所を探す、など）を取り上げます。ただ、ねらいは動きそのものではなく、「どうやってプログラムにしたか」を、順を追って見ていくことです。

この章のプログラムは、Pythonで書きます。入門編の第3部3章に、ブロックで組める部分（斜めの敵への対応、いつlookするか、など）を、Blocklyで組んだ図があります。ブロックと見比べたいときは、そちらを見てください。第2部（特に5章の関数）を読んでから進んでください。辞書・タプル・globalのように、第2部で扱っていないPythonの書き方は、初めて使う場面で説明します。この章のコードは、簡易版ではなく、正式な本番用の書き方（命令にplayer.を付ける）です。チュートリアルのPython画面で試すときは、player.を外してください。

また、この章は、答えを一つに決めるものではありません。同じ「やりたいこと」でも、プログラムにする方法は何通りもあります。どれを採用するかは、自分のプログラムで試しながら決めてください。

考え方：やりたいことを、プログラムにする4ステップ

「こう動かしたい」というアイデアは、日本語で浮かびます。ところが、コンピューターは日本語をそのままでは理解してくれません。日本語から、動くコードまでの間には、次の4つのステップがあります。この章のどの例でも、この順番で考えています。

1. やりたいことを1文で書く

   例：「覚えているアイテムのうち、近いものを取りに行きたい」

2. あいまいな言葉を、数えられるものに直す

   「近い」は何マス離れているか、「最近」は何ターン前か、というように、数えたり比べたりできるものに置き換えます。

3. 日本語のまま、小さな手順に分ける

   「①覚えているマスを全部見る」「②アイテムだけ選ぶ」「③いちばん近いものを決める」…と、1つの手順が1〜数行のコードになる大きさまで分けます。

4. 手順を1つずつ、コードの部品に置き換える

   下の表のように、手順の形ごとに使う「型」がだいたい決まっています。

うまく作るコツは、最初から全部を作ろうとせず、手順①だけを書いて動かし、確かめてから次の手順を足していくことです。第2部6章の総合演習と同じ進め方です。

やってみよう：「隣に敵がいたら攻撃する」

いちばん簡単な例で、4つのステップを一通りやってみましょう。

ステップ1：やりたいことを1文で書く

隣に敵がいたら、ブロックを置いて攻撃したい。

ステップ2：あいまいな言葉を、数えられるものに直す

• 「隣」→ 上・下・左・右のどれか
• 「敵がいる」→ map_info[方向] == Enemy（第2部2章で学んだ書き方）
• 「攻撃する」→ その方向にplayer.put(方向)

ステップ3：日本語のまま、小さな手順に分ける

1. 上・下・左・右を、1つずつ見る
2. その方向に敵がいるか、確かめる
3. いたら、その方向にブロックを置く
4. 置いたら、この仕事は終わり（あとで使うので、Trueを返す）
5. どの方向にもいなければ、何もしない（Falseを返す）

ステップ4：手順を1つずつ、コードの部品に置き換える

手順1は「候補を全部、順番に調べる」なのでfor、手順2は「条件に合うものだけ選ぶ」なのでif、手順4と5は「終わったことを知らせる」のでreturnです。

def attack_adjacent_enemy():
    for direction in (Up, Down, Left, Right):   # 手順1：4方向を順に
        if map_info[direction] == Enemy:        # 手順2：敵がいるか
            player.put(direction)               # 手順3：ブロックを置く
            return True                         # 手順4：行動した
    return False                                # 手順5：何もしなかった

手順の番号とコードの行が、1対1で対応していることを確かめてください。日本語の手順が細かく書けていれば、コードは自然に決まります。反対に、コードが書けなくて手が止まったときは、手順の分け方が足りていないことがほとんどです。手順を、もっと細かく分けてみましょう。

この章の以降の例は、どれも、この4ステップで組み立てていきます。

部品を組み合わせる：判断を優先順位で並べる

CHaserでは、1ターンに行動できるのは1回だけです。ある行動をしたら、そのターンはもう終わりです。この性質を使うと、前の節で作ったような関数（「やりたいこと」1つぶんの部品）を、次のような形で組み合わせられます。

1. 「こういう状況なら、こう動く」という判断を、関数として1つずつ用意する。
2. それぞれの関数は、行動したらTrue、当てはまらなくて何もしなかったらFalseを返す。
3. 優先したい順に上から呼び出し、Trueが返ってきたらそのターンを終える。

def take_turn():
    if attack_adjacent_enemy():   # 1. 隣に敵がいたら攻撃
        return
    if grab_visible_item():       # 2. 見えているアイテムを取る
        return
    random_walk()                 # 3. なければランダムに歩く

while True:
    map_info = player.get_ready()
    take_turn()

returnは第2部5章で学んだとおり、関数をそこで終わらせる命令です。if attack_adjacent_enemy():の中でreturnすれば、それより下の判断は実行されません。つまり、上に書いた判断ほど優先されるということです。プログラム全体の動きは、この「並べる順番」と「各関数の中身」で決まります。

attack_adjacent_enemyは、前の節で作ったものです。ほかの2つも、同じ4ステップで作れます。どれも第2部までに学んだ書き方だけでできています。

def attack_adjacent_enemy():
    for direction in (Up, Down, Left, Right):
        if map_info[direction] == Enemy:
            player.put(direction)        # 敵のマスにブロックを置く
            return True
    return False


def grab_visible_item():
    for direction in (Up, Down, Left, Right):
        if map_info[direction] == Item:
            player.walk(direction)
            return True
    return False


def random_walk():
    free_directions = []
    for direction in (Up, Down, Left, Right):
        if map_info[direction] != Block:
            free_directions.append(direction)
    if free_directions:
        player.walk(random.choice(free_directions))
    else:
        player.look(Up)     # 四方が塞がったときの保険

for direction in (Up, Down, Left, Right):は、括弧の中の方向を1つずつdirectionに入れて繰り返す書き方です。map_infoとplayerは、第2部でも使ったものと同じです。

ここで覚えておきたい約束：1つの関数の中でplayer.walk・player.put・player.look・player.searchを呼ぶのは、多くても1回にしましょう。1ターンに行動できるのは1回だけなので、2回呼ぶと2回目は次のターンにずれ込み、思ったとおりに動かなくなります。

以降の節では、このtake_turnの中に並べる部品を、「やりたいこと」ごとに1つずつ作っていきます。

例1 同じ「やりたいこと」を、3通りのプログラムにする（斜めに敵がいたら）

この例で身につく考え方：同じ「やりたいこと」でも、プログラムにする方法は1つとは限りません。複数の書き方を作って、比べて選びます。

map_infoを見ると、敵が斜め（UpLeft・UpRight・DownLeft・DownRight）にいることがあります。このときの動き方は、勝敗に直結する重要な場面です。まず、何が問題になるのかを整理しましょう。

敵が斜めにいるとき、次に縦か横に隣り合う形を作った側は、その直後に相手の手番が来ます。相手は隣にいる自分にブロックを置いてアタックできるので、自分から隣り合いを作るのは危険です。逆に、相手が隣り合いを作ってくれたなら、次は自分の手番なので、こちらがアタックできます。

ここから、斜めに敵がいるときの動き方が3通り考えられます。どれも「自分から隣り合いを作らない」という点は共通です。

手順に分けてみよう

やりたいこと：敵が斜めにいるときに、自分から隣り合いを作らないように動く。

この文を、次の5つの手順に分けると、プログラムにできます。3つの選択肢は、④だけが違い、ほかの手順は共通です。

③で使うのが、次の「表」（辞書）です。

選択肢A：動かずに待つ（wait）

相手が近づいてくるのを待つ作戦です。ただし、CHaserに「何もしない」という命令はありません。動かずに1ターンを使える行動は、look・search・putのいずれかです。ここでは、敵のいる側をlookして待つことにします。lookなら情報も手に入り、なおかつ何も壊しません。

# 斜めの方向ごとに、「敵に近づく2つの方向」を用意しておく
APPROACH = {
    UpLeft: (Up, Left),
    UpRight: (Up, Right),
    DownLeft: (Down, Left),
    DownRight: (Down, Right),
}

def wait_diagonal_enemy():
    for diagonal in APPROACH:
        if map_info[diagonal] == Enemy:
            player.look(APPROACH[diagonal][0])  # 動かず敵の側を見る
            return True
    return False

APPROACHは「辞書」と呼ばれるもので、{キー: 値, ...}の形で書き、APPROACH[UpLeft]のようにキーを指定して値を取り出します。ここでは、斜めの方向をキー、その斜めに近づくための2つの方向（縦と横）をまとめた組を値にしています。for diagonal in APPROACH:とすると、キー（4つの斜め方向）が1つずつ取り出されます。

この表の意味（座標で考える）

自分を(0, 0)、右がxの＋、下がyの＋とします。右上（UpRight）の敵は(1, -1)にいます。この敵が自分と縦か横に隣り合うには、(0, -1)（自分の上）か(1, 0)（自分の右）のどちらかのマスに入る必要があります。この2マスは、自分にも敵にも隣り合っています。

つまり、APPROACH[UpRight] = (Up, Right)の2方向は、「敵が隣り合うために入ってくるマス」であり、同時に「自分がそこへ歩くと隣り合いができてしまうマス」です。ほかの3つの斜めも、同じ考え方で決まっています。

wait_diagonal_enemyでAPPROACH[diagonal][0]の方向をlookするのは、そこが敵の側だからです。右上の敵ならlook(Up)となり、上方向のx = -1〜1、y = -3〜-1のマスが見えます。敵がいま立っている(1, -1)も、その範囲に入っています。

選択肢B：反対側に離れる（evade）

隣り合いを作らないように、敵から遠ざかる作戦です。

# 斜めの方向ごとに、「敵から離れる2つの方向」
ESCAPE = {
    UpLeft: (Down, Right),
    UpRight: (Down, Left),
    DownLeft: (Up, Right),
    DownRight: (Up, Left),
}

def evade_diagonal_enemy():
    for diagonal in ESCAPE:
        if map_info[diagonal] == Enemy:
            for direction in ESCAPE[diagonal]:
                if map_info[direction] != Block:
                    player.walk(direction)
                    return True
    return False

離れる方向が2つあるのは、片方がブロックで塞がっていることもあるからです。通れる方を先に見つけたほうへ進みます。

選択肢C：敵の近づく道を塞ぐ（block）

敵が近づくために通るマスにブロックを置いて、隣り合えなくする作戦です。

def block_diagonal_enemy():
    for diagonal in APPROACH:
        if map_info[diagonal] == Enemy:
            for direction in APPROACH[diagonal]:
                if map_info[direction] != Block:
                    player.put(direction)  # 接近路を塞ぐ
                    return True
    return False

1回に塞げるのは、2つの接近路のうち1マスだけです。もう1マスは空いたままなので、敵がそちらから隣り合ってくる可能性は残ります。

3つを比べて、選ぶ

3つとも、take_turnに並べる位置は同じ（attack_adjacent_enemyの直後）で、関数名を差し替えるだけで切り替えられます。

def take_turn():
    if attack_adjacent_enemy():
        return
    if wait_diagonal_enemy():     # ← evade_… や block_… に替えられる
        return
    ...

それぞれに長所と短所があります。

どれが向いているかは、相手のプログラムや、マップの形によっても変わります。3つを全部書いて、自分のプログラム同士や、CPU対戦で試してみましょう。

例2 あいまいな言葉を、数字にする（いつlookするか）

この例で身につく考え方：「近く」「最近」のようなあいまいな言葉は、何かを数えて、数字を比べる式に直せば、プログラムにできます。

前の節では、lookを「動かずに1ターンを使う行動」として使いました。lookのもう1つの使い方は、遠くの様子を先に知ることです。

get_ready()が返すmap_infoは、自分のすぐ周りの9マスだけです。その外側にいる敵は見えません。そこで、lookを使って、進む先の様子を先に確かめます。

lookは、指定した方向の2マス先を中心とする周囲9マスを教えてくれます。たとえばplayer.look(Up)を実行すると、上方向の1〜3マス先の範囲が、次の形でlook_infoに入ります。

lookを使うと、ちょうどmap_infoの外側にいる敵を先に見つけられます。ただし、lookは1ターンを使うので、その間は移動もアイテム取得もできません。むやみに撃つと、アイテムを集める速さが落ちます。そこで、「いつ撃つか」が考えどころになります。

ここでは、敵を見た直後の数ターンだけ、進行方向をlookするという作戦を作ります。敵がすぐ近くにいたなら、また近くにいる可能性が高いからです。

やりたいこと：敵が近くにいそうなときだけ、進行方向をlookする。

このままでは、プログラムにできません。「近くにいそう」「撃ちすぎない」といったあいまいな言葉を、コンピューターが計算できる形に直す必要があるからです。コツは、「何を数えれば言えるか」を考えることです。

「4ターン以内」「3ターン以上」の数字は、この作戦の調整つまみです。そして、この式を計算するために、次の3つを覚えておく必要があります。

• いま何ターン目か（turn_counter）
• 最後に敵を見たのは何ターン目か（last_enemy_turn）
• 最後にlookしたのは何ターン目か（last_look_turn）

さらに、「進行方向」を覚えるために、player.walkを包む関数moveを作ります。

turn_counter = 0          # 何ターン目か（メインループで1ずつ増やす）
last_enemy_turn = -999    # 最後に敵を見たターン（-999は「まだ」）
last_look_turn = -999     # 最後にlookしたターン
current_dir = Left        # 直前に進んだ方向


def move(direction):
    global current_dir
    player.walk(direction)
    current_dir = direction


def look_toward(direction):
    global last_look_turn, last_enemy_turn
    look_info = player.look(direction)
    last_look_turn = turn_counter
    if look_info is not None and Enemy in look_info:  # 敵が見えたか
        last_enemy_turn = turn_counter


def look_ahead_if_enemy_nearby():
    # 直近4ターン以内に敵を見た？
    saw_enemy_recently = turn_counter - last_enemy_turn <= 4
    # 前回のlookから3ターン以上あいた？
    looked_long_ago = turn_counter - last_look_turn >= 3
    if saw_enemy_recently and looked_long_ago:
        look_toward(current_dir)
        return True
    return False

globalは、関数の外にある変数を、関数の中で書き換えるときに必要な宣言です。関数の中で読むだけなら不要（map_infoのように）ですが、current_dir = directionのように新しい値を代入するときは、global current_dirと先に書かないと、関数の中だけの別の変数になってしまい、外の変数は変わりません。

Enemy in look_infoは、「look_infoのリストの中にEnemyが含まれているか」を調べる書き方です。look_info is not Noneを先に確認しているのは、試合が終わった直後などで情報が取れなかったときに、エラーで止まらないようにするためです。

条件の計算例

look_ahead_if_enemy_nearbyの2つの条件は、ターン数の引き算だけで決まります。いまturn_counterが10だとします。

last_enemy_turnの最初の値を-999にしておくと、「まだ一度も敵を見ていない」ときは引き算の結果が大きくなり、1つ目の条件が成り立ちません。2つの条件が両方成り立ったときだけ、lookします。

メインループでは、ターンごとにturn_counterを1つ増やし、map_infoに敵がいたらlast_enemy_turnを更新します。

while True:
    map_info = player.get_ready()
    turn_counter += 1
    if Enemy in map_info:
        last_enemy_turn = turn_counter
    take_turn()

骨組みに貼るときの注意：このwhile True:を、第2部0章の骨組みのmainの中に置く場合は、ここで代入しているturn_counterとlast_enemy_turnを、mainの先頭のglobalにも付け足します（global player, map_info, turn_counter, last_enemy_turn）。付け足さないと、mainの中だけの別の変数になってしまい、エラーになります。

take_turnの中には、アイテム取得より下、探索より上にlook_ahead_if_enemy_nearby()を置きます。アイテムを取れるときは取り、取れなくて敵が近くにいそうなときだけ先を見る、という順番です。

なお、moveを使うときは、これまでのplayer.walk(direction)をすべてmove(direction)に書き換えておきましょう。そうしないと、current_dirが更新されず、進行方向が古いままになります。

例3 情報を覚えておく（自分の位置と地図）

この例で身につく考え方：プログラムは、前のターンに見たことを勝手には覚えていません。あとで使いたい情報は、変数や辞書に、自分で書き込んでおきます。

次の2つの節（探索とアイテム追跡）では、見たことのあるマスを覚えておくことが必要になります。map_infoは毎ターン作り直されるので、そのままでは前のターンに見た情報は残りません。そこで、自分で「地図」を作って持ち続けます。

やりたいこと：見たことのあるマスの中身を覚えておいて、あとで使えるようにする。

これも、いくつかの疑問に分けて考えます。

1. 何を覚える？ 「どこのマスが」「何だったか」の組です。「場所から中身を引く」ので、辞書がぴったりです。
2. 場所をどう表す？ マスに番号を振るための座標が必要です。ところが、map_infoには「自分の周り」しか入っていないので、絶対的な位置は教えてくれません。そこで、スタート地点を(0, 0)と決め、歩いた分だけ自分の座標を数えて更新します。
3. 周りのマスの座標は？ 「自分の座標 ＋ 方角ごとのずれ」で求められます。右隣なら(+1, 0)、左上なら(-1, -1)です。このずれを、方角ごとにまとめた表がOFFSETです。

この3つを、次のコードにしていきます。

座標を決める

地図に書き込むには、マスを区別するための座標が必要です。自分が最初にいた場所を(0, 0)とし、右に進むとxが増え、下に進むとyが増えるものとします。自分がいまどこにいるかは、歩くたびに数えて更新します。前の節で作ったmoveを、位置の記録も行うように書き直します。

my_x, my_y = 0, 0    # 自分の位置（スタート地点が(0, 0)）

# 方角ごとの、座標のずれ（x は右が +、y は下が +）
OFFSET = {
    UpLeft: (-1, -1), Up: (0, -1), UpRight: (1, -1),
    Left: (-1, 0),                  Right: (1, 0),
    DownLeft: (-1, 1), Down: (0, 1), DownRight: (1, 1),
}


def move(direction):
    global my_x, my_y, current_dir
    player.walk(direction)
    dx, dy = OFFSET[direction]
    my_x += dx                     # 歩いた分だけ自分の座標を更新
    my_y += dy
    current_dir = direction
    # 立っているマスは床（アイテムがあっても、もう取ったので）
    memory[(my_x, my_y)] = Floor

(0, -1)のように、かっこで囲んで並べたものをタプルと呼びます。リストと似ていますが、中身を後から変えられない点が違い、「2つの値のセット」を1つの値として扱いたいときに便利です。ここでは(x, y)の座標をひとまとめにするのに使います。

dx, dy = OFFSET[direction]は、タプルの2つの値を、それぞれdxとdyに一度に代入する書き方です。

計算の例：自分が(4, 3)にいてmove(Right)を実行すると、OFFSET[Right]は(1, 0)なので、my_xは4 + 1 = 5、my_yは3 + 0 = 3になり、自分の座標は(5, 3)に変わります。上に歩けばOFFSET[Up]は(0, -1)なので、yが1減ります。

見たことのあるマスを覚える

見えたマスの中身は、座標をキーにした辞書に書き込んでいきます。

memory = {}    # 座標(x, y) → そのマスの中身（Floor / Block / Item）


def remember_surroundings():
    for direction in OFFSET:
        dx, dy = OFFSET[direction]
        if map_info[direction] != Enemy:  # 敵は動くので書かない
            memory[(my_x + dx, my_y + dy)] = map_info[direction]

計算の例：自分が(4, 3)にいて、map_info[UpRight]がItemだったとします。OFFSET[UpRight]は(1, -1)なので、書き込む座標は(4 + 1, 3 + (-1)) = (5, 2)です。つまりmemory[(5, 2)] = Itemと書かれます。この計算を8方向すべてについて繰り返しているのがremember_surroundingsです。

memory[(3, 5)] = Blockのように書くと、「座標(3, 5)はブロック」と覚えます。あとでmemory.get((3, 5))とすれば、覚えていればその値、まだ見ていなければNoneが返ります。この「まだ見ていない」を判定できることが、次の節で役に立ちます。

毎ターンの最初にremember_surroundings()を呼ぶようにします。take_turnの1行目に置くのがよいでしょう。

def take_turn():
    remember_surroundings()          # まず見えたものを地図に書き込む
    if attack_adjacent_enemy():
        return
    ...

同じように、lookで見えた9マスも地図に書き込めます。前の節のlook_towardを、見えた内容をmemoryに書き込むように書き直しましょう。lookの中心は「2マス先」なので、位置の計算に注意が必要です。

def look_toward(direction):
    global last_look_turn, last_enemy_turn
    look_info = player.look(direction)
    last_look_turn = turn_counter
    if look_info is not None:
        dx, dy = OFFSET[direction]
        center_x = my_x + dx * 2       # lookの中心（2マス先）の座標
        center_y = my_y + dy * 2
        if Enemy in look_info:
            last_enemy_turn = turn_counter
        for around in OFFSET:
            ox, oy = OFFSET[around]
            if look_info[around] != Enemy:
                cell = (center_x + ox, center_y + oy)
                memory[cell] = look_info[around]
        if look_info[Center] != Enemy:
            memory[(center_x, center_y)] = look_info[Center]

計算の例：自分が(4, 3)にいてlook(Up)を実行したとします。OFFSET[Up]は(0, -1)なので、lookの中心は(4 + 0 × 2, 3 + (-1) × 2) = (4, 1)です。あとは、中心からOFFSET[around]だけずらした座標に、look_info[around]を書き込みます。たとえばlook_info[UpLeft]は(4 - 1, 1 - 1) = (3, 0)、look_info[Right]は(4 + 1, 1 + 0) = (5, 1)です。見えた9マスの座標は次のとおりです。

例4 「いちばん近い」を探す（探索の道順）

この例で身につく考え方：一見簡単そうな「やりたいこと」でも、実現するには考えることが多い場合があります。そんなときは、疑問を1つずつ解いていくことで、手順に分けられます。

アイテムが見つからないとき、どこへ進むかも、プログラムで決める大事な部分です。第2部5章のランダム移動は、同じ場所を行ったり来たりしやすい欠点があります。そこで、まだ見ていないマスのうち、いちばん近いところを目指す方法を作ります。

やりたいこと：まだ見ていないマスのうち、いちばん近いところへ向かう「最初の一歩」の方向を知りたい。

これをプログラムにするには、いくつかの疑問を順番に解いていく必要があります。

1. まっすぐ向かえばよいのでは？

   間にブロックがあると、そこでつっかえてしまいます。memoryという地図を使って、ブロックを避けた道順を調べる必要があります。

2. 「いちばん近い」をどうやって見つける？

   自分から1歩で行けるマスをすべて調べ、次にそこから1歩で行ける（自分から2歩の）マスをすべて調べ、その次は3歩のマス…と、池に石を投げたときの波紋のように、近いほうから順に広げていきます。最初に見つかった「まだ見ていないマス」が、いちばん近いマスです。この探し方を幅優先探索（BFS）と呼びます。

3. 調べる順番をどう管理する？

   これから調べるマスを、見つけた順に1列に並べた順番待ちの列（queue）に入れます。先頭から順に取り出せば、先に見つけた（＝近い）マスから調べられるので、近い順が自然に保たれます。

4. 同じマスを二度調べたくない。

   調べ始めたマスは、辞書first_dirに登録します。next_cell not in first_dir（登録されていない）なら、初めて来たマスだと分かります。

5. 知りたいのは道順の全部ではなく、最初の一歩だけ。

   実際に歩くのは1ターンに1歩で、次のターンには新しい情報でまた計算し直します。そこで、各マスに「そのマスへ行くときの最初の一歩」を持たせておき、隣のマスへ広げるときに引き継ぎます（自分から直接出る隣のマスだけは、その方向を新しく決めます）。

6. どこで終わる？

   「まだ見ていないマス」にたどり着いたら、そのマスに引き継がれていた最初の一歩を答えにして終わります。全部調べても見つからなければNoneです。まだ見ていないマスは通れるかどうか分からないので、終点にはしても、そこから先へは広げません。

以上を、順番に手順に並べ直すと、次のようになります。コードの各行にも、対応する番号をコメントで付けてあります。

def first_step_to_unknown(max_nodes=600):
    """未知のマスへの最初の一歩の方向を返す。なければ None"""
    start = (my_x, my_y)                  # ① 出発点
    first_dir = {start: None}             # ① 各マスへの「最初の一歩」
    queue = [start]                       # ① 順番待ちの列
    head = 0                              # ① 何番目まで調べたか
    while head < len(queue) and head < max_nodes:    # ② 残っている間
        x, y = queue[head]                # ③ 先頭を取り出す
        head += 1
        for direction in (Up, Down, Left, Right):    # ④ 隣を調べる
            dx, dy = OFFSET[direction]
            next_cell = (x + dx, y + dy)
            if next_cell not in first_dir:    # ⑤ 初めて来たマスなら
                step = first_dir[(x, y)]
                if step is None:
                    step = direction          # ⑤ 出発点から出る一歩
                cell = memory.get(next_cell)
                if cell is None:
                    return step               # ⑥ 未知のマス：終了
                if cell != Block:
                    first_dir[next_cell] = step   # ⑥ 通れる：広げる
                    queue.append(next_cell)
    return None                           # ⑦ 見つからなかった

読み解くポイントは3つです。

• queueは、調べるマスを先に見つけた順に並べたリストです。headで、そのどこまで調べ終わったかを持ち、前から順に取り出します。これで、近いマスが必ず先に調べられます。
• first_dirには、そのマスへ行くときの最初の一歩を覚えさせます。これを次のマスへ受け渡していくので、遠いマスに着いたときでも、「最初にどちらへ歩けばよいか」が分かります。
• memory.get(next_cell)がNoneのマスは「まだ見ていない」マスです。通れるかどうかは分からないので、途中の道には使わず、たどり着いた時点で探索を終えるようにしています。

max_nodesは、調べるマスの数の上限です。広いマップで探索に時間がかかりすぎないようにしています。

途中経過を追ってみよう

次の小さな地図で、first_step_to_unknownが実際にどう動くかを追ってみます。#はブロック、.は通れるマス、?はまだ見ていないマス（memoryにない）、Sは自分の位置(1, 1)です。

      x=0  1  2  3  4
y=0     #  #  #  #  #
y=1     #  S  .  .  ?
y=2     #  .  #  .  #
y=3     #  #  #  #  #

whileの繰り返し1回ごとに、queueの先頭のマスを取り出し、上・下・左・右の順に隣を調べます。

4回目に、(4, 1)がmemoryにない（memory.getがNone）ので、return stepで終わります。このときのstepは、(3, 1)に着いたときに引き継いでいた「最初の一歩」で、右です。自分から見て(4, 1)は右に3マス先ですが、この関数が返すのは、そこへ向かう最初の一歩の方向だけです。

ここで大事なのは、2回目の(1, 2)のように、行き止まりの枝も先に調べられていることです。近いマスから順に広げるので、遠回りの道を選んでしまうことはありません。

exploreは、この結果がRightなら、map_info[Right]がブロックでないことを確かめてからmove(Right)で1歩だけ歩きます。次のターンにはまた新しいmemoryで、最初から計算し直します。

この関数を使って、探索を次のように書き換えます。

def explore():
    step = first_step_to_unknown()
    if step is not None and map_info[step] != Block:
        move(step)
    else:
        random_walk()     # 道がなければランダム移動

take_turnの最後を、random_walk()からexplore()に置き換えます。

例5 小さな部品を足して、動きを整える

この例で身につく考え方：できあがった部品に、小さな関数を足したり、数字を変えたりするだけで、動きを調整できます。調整したい数字は、名前を付けた変数（調整つまみ）にしておくと、あとから変えやすくなります。

ここまでのプログラムに、さらに2つの小さな工夫を足してみましょう。どちらも、数行の関数と数字1つで作れます。

覚えているアイテムを追う（範囲を決める）

アイテムは、いったん見えたあとで視界から外れることがあります。たとえば、通りすがりに斜め前のアイテムが見えたのに、別のことを優先して取り損ねた場合です。そのままでは、そのアイテムの場所を忘れてしまいます。

でも、「準備」の節で作ったmemoryには、見えたマスの中身が残っています。そこで、memoryの中からItemと書かれたマスを探し出し、そこへ向かうことができます。ただし、あまり遠いアイテムを追いかけていると、その間に探索が進みません。追いかける距離の上限を決めておくのがポイントです。

やりたいこと：覚えているアイテムのうち、近いものを取りに行きたい。

先ほどの4ステップで、順番に考えてみましょう。

（ステップ2）あいまいな言葉を数えられるものに直す

• 「覚えているアイテム」→ memoryの中で、値がItemのマス
• 「近い」→ 自分からそのマスまで、あと何歩で行けるか。歩くのは縦と横だけなので、横に離れたマス数 ＋ 縦に離れたマス数で見積もれる（間にブロックがない場合）
• 「遠すぎるものは追わない」→ その歩数が、上限MEMORY_PURSUIT_RANGE以下

（ステップ3・4）手順に分けて、コードにする

MEMORY_PURSUIT_RANGE = 2    # 何マス以内のアイテムまで追いかけるか


def pursue_remembered_item():
    nearest = None                                # ③ いちばん近い候補
    nearest_distance = MEMORY_PURSUIT_RANGE + 1   # ③ 上限＋1から始める
    for cell in memory:                           # ① 覚えている全マスを
        if memory[cell] == Item:                  # ① アイテムだけ選ぶ
            # ② 縦横に合わせて何マス離れているか
            distance = abs(cell[0] - my_x) + abs(cell[1] - my_y)
            if distance < nearest_distance:       # ③ いままでより近い
                nearest = cell
                nearest_distance = distance
    if nearest is None:
        return False                              # ⑤ 追う相手がいない
    return step_toward(nearest)                   # ④ 近づく


def step_toward(target):
    dx = target[0] - my_x                # ④ 目標との差（右が＋）
    dy = target[1] - my_y                # ④ 目標との差（下が＋）
    directions = []
    if dx != 0:
        directions.append(Right if dx > 0 else Left)
    if dy != 0:
        directions.append(Down if dy > 0 else Up)
    if abs(dy) > abs(dx):
        directions.reverse()  # 離れている軸を先に試す
    for direction in directions:
        if map_info[direction] in (Floor, Item):
            move(direction)
            return True
    return False

補足：コードの細かい部分

上限より遠いアイテムを除くしくみ（pursue_remembered_item）

for cell in memory:は、辞書memoryのキー、つまり覚えているすべてのマスの座標(x, y)を1つずつ取り出す書き方です。memory[cell] == Itemで、そのマスがアイテムだと覚えているものだけに絞ります。

自分との距離は、abs(cell[0] - my_x) + abs(cell[1] - my_y)で求めています。absは絶対値（マイナスを外した値）を返す命令で、これは「横に何マス、縦に何マス離れているか」を足した値です。歩くのは縦と横だけなので、この値がそのまま「あと何歩かかるか」の目安になります（間にブロックがない場合）。

nearest_distanceは、はじめにMEMORY_PURSUIT_RANGE + 1にしておきます。すると、distance < nearest_distanceという比較は、「上限以内で、いままで見つけたどれよりも近い」という意味になり、上限より遠いアイテムは最初から候補に入りません。候補が1つも見つからなければnearestはNoneのままなので、return Falseで何もせず終わります。

近づく向きの決め方（step_toward）

目標との差dx・dyを求めると、どちらへ進めば近づけるかが分かります。dxが正なら目標は右、負なら左にあります。dyが正なら下、負なら上です。Right if dx > 0 else Leftは、「dx > 0ならRight、そうでなければLeft」を1行で書く形です。

dxまたはdyが0のとき、その方向へは進む必要がないので、if dx != 0:のように0でないときだけ候補に加えます。候補は、離れているほうの方向を先に並べます（abs(dy) > abs(dx)のときは並びを逆にします）。

たとえば、自分が(4, 3)にいて、次のようなアイテムを覚えているとします。上限は2です。

(6, 3)と(5, 4)はどちらも距離2で、memoryに先に書き込まれたほうが選ばれます。仮に(6, 3)が選ばれたとすると、dx = 2、dy = 0なので、進む候補はRightだけです。(5, 4)が選ばれたとすると、dx = 1、dy = 1で、RightとDownが候補になり、Rightから先に試します。

候補の方向はmap_info[direction] in (Floor, Item)で、いま実際に見えている情報で歩けるかを確かめます。ブロックなら次の候補を試し、どの候補も歩けなければFalseを返します。

うまくいかないとき

次のような場面では、pursue_remembered_itemはFalseを返し、take_turnは次の判断（lookや探索）に進みます。

• 上限の範囲内にアイテムを覚えていない
• 近づく方向がブロックで塞がっている

このstep_towardは、間のブロックを避けて回り込むことまではしません。壁の向こうにあるアイテムは追えず、Falseを返して次の判断に任せます。近いアイテムほど間にブロックが入りにくいので、上限を小さくしておくと、こうした「近づけない」場面は起きにくくなります。

なお、覚えているアイテムは、すでに誰かに取られていることもあります。ただ、そのアイテムが自分の周りの9マスに入れば、次のターンのremember_surroundings()でmemoryが最新の内容に書き換わり、もう追わなくなります。

take_turnのどこに置くか

「見えているアイテム」（grab_visible_item）の直後に置きます。見えているものを先に取り、見えていないものは覚えているものを追う、という順番です。

    if grab_visible_item():
        return
    if pursue_remembered_item():     # ← ここ
        return

MEMORY_PURSUIT_RANGEの数字を2、5、10と変えると、追いかけ方がどう変わるかを試せます。

行き止まりを避ける（脱出口を数える）

アイテムを取ると、取る前に立っていたマス（元のマス）にブロックが出現するのでした（第1部4章）。ブロックに囲まれた場所にアイテムがあると、取った瞬間に自分の背後が塞がって逃げ道がなくなり、自縛してしまうことがあります。

やりたいこと：取ったあとに閉じ込められそうなアイテムは、取らない。

「閉じ込められそう」も、そのままではプログラムにできません。数えられる形に直していきます。

1. 「閉じ込められる」を数字にする：進んだ先から、次に歩ける方向がいくつあるか（出口の数）を数えます。0なら閉じ込められ、少ないほど危険です。
2. 出口をどう数える？：進んだ先の上下左右の4マスのうち、ブロックでないものを数えます。
3. 見ていないマスは？：通れるかもしれないので、出口として数えます（memory.get(cell) != Blockは、Noneのときも成り立ちます）。
4. 特別扱いするマスがある：進んだ先から見て「いま自分が立っているマス」は、普通は床なので通れます。ただし、アイテムを取る動きのときだけは、そこがブロックになるので、出口に数えません。

この4つを、そのままコードにしたのが次の関数です。

def count_exits(direction):
    """direction へ進んだあと、そこから出られる方向の数"""
    dx, dy = OFFSET[direction]
    new_x, new_y = my_x + dx, my_y + dy
    picks_item = map_info[direction] == Item  # アイテムを取る動きか
    exits = 0
    for side in (Up, Down, Left, Right):
        sx, sy = OFFSET[side]
        cell = (new_x + sx, new_y + sy)
        if cell == (my_x, my_y):
            if not picks_item:  # 取ると元のマスは塞がる
                exits += 1
        elif memory.get(cell) != Block:  # 未知のマスは通れる扱い
            exits += 1
    return exits

計算の例：自分が(4, 3)にいて、右の(5, 3)にアイテムがあるとします。覚えている周りは、(5, 2)がブロック、(5, 4)が床、(6, 3)がブロックです。count_exits(Right)は、進んだ先(5, 3)から見た上下左右を調べます。

合計は1です。もしこれがアイテムではなく床なら、元のマスも通れるので合計は2になります。この関数は、「取ると出口が1つ減る」ことまで数えに入れています。

この関数をgrab_visible_itemに組み込みます。「出口が2つ以上残る取り方」を先に探し、なければ「1つ以上」、それでもなければ見送ります。

def grab_visible_item():
    for min_exits in (2, 1):  # 出口が多い取り方を優先
        for direction in (Up, Down, Left, Right):
            if map_info[direction] == Item:
                if count_exits(direction) >= min_exits:
                    move(direction)
                    return True
    return False

出口が0になる取り方は、どの条件でも選ばれません。目先のアイテムより、自分が生き残ることを優先する考え方です。

先ほどの例（合計1）では、min_exitsが2のときは見送られ、次のmin_exitsが1のときに、1 >= 1となって取られます。ほかに取れるアイテムがあれば、そちらが先に選ばれます。

全部をつなげると

ここまで作った部品を、優先順位の連鎖に並べ直すと、次のようになります。

def take_turn():
    remember_surroundings()              # 見えたものを地図に書く
    if attack_adjacent_enemy():          # 1. 隣の敵を攻撃
        return
    if wait_diagonal_enemy():            # 2. 斜めの敵への対応
        return
    if grab_visible_item():              # 3. 見えているアイテム
        return
    if pursue_remembered_item():         # 4. 覚えているアイテム
        return
    if look_ahead_if_enemy_nearby():     # 5. 敵が近ければ先を見る
        return
    explore()                            # 6. 未踏のマスを探す


while True:
    map_info = player.get_ready()
    turn_counter += 1
    if Enemy in map_info:
        last_enemy_turn = turn_counter
    take_turn()

順番を入れ替えたり、一部を抜いたりして、動きがどう変わるかを見てみましょう。優先順位の連鎖は、「部品を足す」「順番を変える」「条件の数字を変える」という3つの操作だけで、プログラムの動きを組み替えられる形になっています。

注意したいこと

• 「やりたいこと」が大きすぎて、手が止まる：無理にコードを書こうとせず、日本語の手順を、1つが数行のコードになる大きさまで細かく分けましょう。分けた手順を、1つずつ書いて動かして確かめると、途中でどこが違うかも見つけやすくなります。
• あいまいな言葉のまま、コードに書こうとする：「近い」「最近」「多い」などは、何を数えて、いくつと比べるのかを決めてから書きます。
• globalを書き忘れる：関数の中でmy_x += dxのように代入する変数には、その関数の先頭でglobal my_xと宣言が必要です。忘れると、エラーになるか、外の変数が更新されません。
• player.walkを直接呼んでしまう：自分の位置と進行方向を覚えるには、歩くときは必ずmoveを通します。途中で直接player.walkを呼ぶと、記録している位置が実際の位置とずれ、地図が使い物にならなくなります。
• 1つの関数で行動を2回呼ぶ：player.walk・put・look・searchは、1ターンに1回だけです。行動したらreturn Trueで終わらせましょう。
• 同じ座標系で数える：memoryのキーやfirst_dirのキーは、すべて(x, y)のタプルです。(y, x)の順で書いたり、リストで書いたりすると、辞書の中で別のキーとして扱われ、見つからなくなります。
• map_infoの内容を、過去のものと取り違える：map_infoは毎ターン新しくなります。前のターンの情報を残したいときは、memoryに書き込んでおく必要があります。

演習問題

1. 「斜めに敵がいたら」の3つの関数（wait_…・evade_…・block_…）を、すべて自分のプログラムに書いてみましょう。1つずつtake_turnに差し替え、CPU対戦や友達との対戦で、結果や動き方にどんな違いが出るか記録してみましょう。
2. 選択肢A（待つ）では、相手も待つタイプだった場合、お互いに動かなくなる可能性があります。「同じ場所で連続して待った回数を数え、上限を超えたら別の行動に切り替える」という工夫を、変数を使って書いてみましょう。
3. look_ahead_if_enemy_nearbyの<= 4と>= 3の数字を変えると、lookを撃つ頻度がどう変わるか、考えてみましょう。撃ちすぎると、どんな困ったことが起きるでしょうか。
4. MEMORY_PURSUIT_RANGEを2、5、10と変えて動かし、アイテムの集まり方にどんな違いが出るか観察してみましょう。
5. first_step_to_unknownでは、「まだ見ていないマス」を目指しました。「覚えているアイテム」を目標にするには、どこをどう書き換えればよいでしょうか。
6. 「途中経過を追ってみよう」の地図で、(3, 1)がブロックだったら、first_step_to_unknownは何を返しますか。queueがどう変わるかを、表のように書き出して考えてみましょう。
7. 脱出口の計算例で、(5, 4)もブロックだったら、count_exits(Right)はいくつになりますか。そのアイテムは取られるでしょうか。
8. 自分で「やりたいこと」を1つ考え、この章の4ステップ（1文で書く → あいまいな言葉を数えられるものに → 手順に分ける → コードにする）で、プログラムにしてみましょう。（例：直前に進んだ方向とは、反対には進まないようにしたい）

第3部のまとめ、そして本書の締めくくり

これで、CHaserのルールを理解し（第1部）、Pythonで命令を書く力を身につけ（第2部）、実際の対戦の準備の仕方と、やりたいことをプログラムにする考え方（第3部）まで、ひととおり学び終えました。

CHaserは、覚える命令の種類こそ多くありませんが、「今の状況をどう読み取り、どう判断するか」を突き詰めていくと、驚くほど奥の深いゲームです。本書で学んだ移動・繰り返し・条件分岐・情報の取得・変数・関数という道具は、CHaserだけでなく、これからあなたが出会う他のプログラミングの課題でも、きっと役に立つはずです。

第3部 確認クイズ

1章 Pythonの画面の使い方

1. 自分のプログラムを書くとき、書き換えてよいのは、骨組みのどの部分ですか。
2. 実行結果がうまくいかないとき、まずどこを確認するとよいでしょうか。

2章 対戦ルームの使い方

1. 対戦を始める前に選べる2種類の対戦方法は何ですか。
2. Pythonのプログラムを対戦ルームで使うには、どのファイルを、どこから読み込みますか。

3章 やりたいことをプログラムにする

1. 「やりたいこと」をプログラムにするときの、4つのステップを順に答えてください。
2. 「近くにいる」のようなあいまいな言葉は、プログラムにするために、どのように直しますか。
3. take_turnの中で、ifとreturnを並べて判断を書くと、上に書いた判断ほど優先されるのはなぜですか。
4. look(Up)を実行したとき、look_info[Center]はどのマスの情報を表しますか。
5. 関数の中で、関数の外にある変数my_xに新しい値を代入したいとき、関数の先頭に何を書く必要がありますか。

（解答は付録1「確認クイズ・演習問題の解答」を参照してください。）

まずは自分のプログラムを実際に動かし、勝ったり負けたりしながら、次はどう直せばもっと強くなるかを考えてみてください。そうやって試行錯誤を重ねることこそが、プログラミングの一番の練習方法です。