前回:Pythonで座標とリストの番号を変換する!divmodとクリック位置の計算|ゲームで学ぶアルゴリズム 第2回

「パズルゲームに『1手もどす』ボタンを付けたいけど、どう作ればいいの?」「もどしたら、取ったはずのコインが消えたままになった…」

動かすところまではできても、もどす処理で手が止まること、ありますよね。この記事は連載「ゲームで学ぶアルゴリズム」の第3回です。今回はスタックというデータの持ち方を使って、1手もどす機能(undo)を作ります。

対象は、リストの append() を使ったことがある初心者〜初級者の方です。動作確認は Python 3.13 で行いました。一緒に見ていきましょう! 😊

スタックとは:最後に積んだものから取り出す

stack of plates
stack of plates / Photo by Ryutaro Tsukata via Pexels

スタックは、最後に入れたものを最初に取り出す入れ物です。イメージとしては、机に積んだお皿の山。上に重ねたお皿から順に取りますよね。

ゲームの「1手もどす」も同じです。もどしたいのはいちばん最後の手で、もう一度もどすと、その1つ前の手。だから手の記録をスタックに積んでおけば、そのまま undo になります。

Python では、ふつうのリストがそのままスタックとして使えます(公式チュートリアルのリストをスタックとして使うでも紹介されています)。

サンプル1:append で積んで、pop で取り出す

まずはスタックの操作だけを確かめます。動いた向きを積んでいくだけのコードです。

# 動いた向きを、スタック(ただのリスト)に積んでいく
history = []

history.append("右")  # 積む(push)
history.append("右")
history.append("下")
print("積んだあと:", history)

last = history.pop()  # いちばん上(最後に積んだもの)を取り出す(pop)
print("取り出した:", last)
print("残り:", history)

print("取り出さずに上をのぞく:", history[-1])
print("積んである数:", len(history))

# 空になるまで取り出すと、積んだのと逆の順番で出てくる
history.append("左")
while history:
    print("取り出した:", history.pop())

print("空になった:", history)
history.pop()  # 空のスタックから取り出すと?
サンプル1の実行結果:appendで積んでpopで取り出す
サンプル1の実行結果:appendで積んでpopで取り出す
積んだあと: ['右', '右', '下']
取り出した: 下
残り: ['右', '右']
取り出さずに上をのぞく: 右
積んである数: 2
取り出した: 左
取り出した: 右
取り出した: 右
空になった: []
Traceback (most recent call last):
  File "C:\...\s1_stack.py", line 22, in <module>
    history.pop()  # 空のスタックから取り出すと?
    ~~~~~~~~~~~^^
IndexError: pop from empty list

ここが重要です👇

  • append() で積む(リストの末尾に足す)、pop() で取り出す(末尾を取り出して、リストからは消える)
  • 取り出さずに上を見たいときは history[-1]。pop() と違って、リストの中身は減りません
  • 「左」を足してから全部取り出すと、左 → 右 → 右と、積んだのと逆の順番で出てきました

⚠️ 最後の行のように、空のリストに pop() すると IndexError: pop from empty list で止まります。ゲームなら、1手も動いていないのに「もどす」を押されたときがこれです。while history: のように「空でないか」を確かめてから取り出しましょう。空のリストは False 扱いになるので、この1行で判定できます。

サンプル2:コインを集める盤面に「1手もどす」を付ける

第1回の二次元リストの盤面で、P(プレイヤー)を動かしてコイン $ を集めます。R・L・U・D で動かして、undo() で1手ずつもどします。

ポイントは、何を積むかです。今回は1手ごとに「動く前の位置」と「その手でコインを取ったか」を積みます。

MAP = [
    "#######",
    "#..$..#",
    "#.#.$.#",
    "#######",
]
board = [list(row) for row in MAP]  # 文字列のままだと書きかえられないのでリストに
DIRS = {"R": (1, 0), "L": (-1, 0), "U": (0, -1), "D": (0, 1)}

player = {"x": 1, "y": 1, "coins": 0}
history = []  # 1手ごとに「もどすのに必要な情報」を積むスタック


def show(label):
    print(f"--- {label}(コイン {player['coins']}枚・履歴 {len(history)}手)")
    for y, row in enumerate(board):
        line = ""
        for x, cell in enumerate(row):
            line += "P" if (x, y) == (player["x"], player["y"]) else cell
        print(line)


def move(key):
    dx, dy = DIRS[key]
    nx, ny = player["x"] + dx, player["y"] + dy
    if board[ny][nx] == "#":
        print(f"{key}: 壁なので動けない(履歴には積まない)")
        return
    got = board[ny][nx] == "$"
    # 動く「前」の位置と、この手でコインを取ったかどうかを積む
    history.append((player["x"], player["y"], got))
    if got:
        board[ny][nx] = "."
        player["coins"] += 1
    player["x"], player["y"] = nx, ny


def undo():
    if not history:  # 空なら pop しない
        print("undo: これ以上もどせません")
        return
    old_x, old_y, got = history.pop()
    if got:
        board[player["y"]][player["x"]] = "$"  # 取ったコインを今いるマスに置き直す
        player["coins"] -= 1
    player["x"], player["y"] = old_x, old_y


show("スタート")
for key in "RRDRUU":
    move(key)
show("RRDRUU と動いたあと")

undo()
show("1手もどす")
undo()
undo()
show("さらに2手もどす")
undo()
undo()
undo()
show("全部もどしたあと")
サンプル2の実行結果:コインを集めて1手ずつもどす
サンプル2の実行結果:コインを集めて1手ずつもどす
--- スタート(コイン 0枚・履歴 0手)
#######
#P.$..#
#.#.$.#
#######
U: 壁なので動けない(履歴には積まない)
--- RRDRUU と動いたあと(コイン 2枚・履歴 5手)
#######
#...P.#
#.#...#
#######
--- 1手もどす(コイン 2枚・履歴 4手)
#######
#.....#
#.#.P.#
#######
--- さらに2手もどす(コイン 1枚・履歴 2手)
#######
#..P..#
#.#.$.#
#######
undo: これ以上もどせません
--- 全部もどしたあと(コイン 0枚・履歴 0手)
#######
#P.$..#
#.#.$.#
#######

ポイントをまとめるとこんな感じです👇

  • RRDRUU と6回動かしましたが、最後の U は壁で動けませんでした。動けなかった手は積まないので、履歴は5手。コインは2枚取れています
  • 1手もどすと、P は U で上がる前のマスへ。この手ではコインを取っていないので、2枚のままです
  • さらに2手もどすと、R で取ったコインが盤面に復活して1枚に。もどすときは位置だけでなく、その手で変わったものを全部もとにもどす必要があります
  • 履歴が空になったら if not history: で止めているので、何回押されてもエラーになりません
  • 壁で動けなかった手まで積んでしまうと、もどしても見た目が変わらない「空振りの1手」ができてしまいます

試しに got を積まずに(いつも False にして)同じ手順を動かすと、全部もどしたあとも P はスタート地点にもどるのに、コインは盤面から消えたまま、枚数も2枚のままでした。冒頭の「コインが消えたまま」は、このパターンです。

サンプル3:盤面ごと積むときの落とし穴

「何が変わったかを考えるのが面倒。動く前の盤面をまるごと積めばいいのでは?」と思いますよね。それも1つの方法です。ただし、積み方を間違えると、もどしても何も変わりません。これ、実行せずに答えられますか? 3通りのうち、コイン $ がもどるのはどれでしょう。

board = [list("..$"), list("...")]


def run(label, save):
    """コインを取る → 1手もどす、を試す"""
    board[0][2] = "$"  # 試すたびに盤面を最初の形に戻しておく
    history = []
    history.append(save(board))  # 動く前の盤面を積む
    board[0][2] = "."            # コインを取る
    before = history.pop()       # 1手もどす
    print(f"{label:<30} もどした盤面の右上: {before[0][2]!r}")


run("history.append(board)", lambda b: b)
run("history.append(board.copy())", lambda b: b.copy())
run("[row[:] for row in board]", lambda b: [row[:] for row in b])
history.append(board)          もどした盤面の右上: '.'
history.append(board.copy())   もどした盤面の右上: '.'
[row[:] for row in board]      もどした盤面の右上: '$'

ここが重要です👇

  • history.append(board) は、盤面のコピーではなく同じリストそのものを積んでいます。そのあとコインを取ると、積んだはずの盤面も一緒に変わり、もどしても '.' のままでした
  • board.copy() でもだめでした。コピーされるのは外側のリストだけで、中の行(内側のリスト)は同じものを指したままだからです
  • 行ごとに row[:] でコピーした3つ目だけが、'$' にもどりました

盤面ごと積む方法は書くのが楽な反面、1手ごとに盤面全体のコピーが増えていきます。小さな盤面ならこれで十分ですが、大きな盤面や手数の多いゲームでは、サンプル2のように「変わったところだけ」を積むほうが軽くすみます。

まとめ

  • スタックは最後に積んだものから取り出す入れ物。Python ではリストの append() と pop() で使える
  • 空のリストに pop() すると IndexError。if not history: で空かどうかを確かめてから取り出す
  • 1手もどすには、動く前の位置に加えて、その手で変わったもの(取ったコインなど)も積んでおく
  • 盤面ごと積むなら [row[:] for row in board]。board そのままや board.copy() では、もどらない

次回の第4回は、スタックとよく比べられるキューを取り上げます。サンプル2の "RRDRUU" を書きかえて、もう1枚のコインも取ってから全部もどせるか試してみてください。ぜひ試してみてください! 🚀

\ Pythonでゲームを作りたい方へ /

筆者は、入門を終えた人向けに、画面の中でキャラクターが動き、キーボードで操作するゲームを7本作る講座を公開しています。最短の手数を自動で探すパズルや、歩数の地図を見て追いかけてくるねこを、自分の手で書きながら「答えにたどり着く手順の考え方(アルゴリズム)」を身につけます。完成版の7本は、パソコンのブラウザでそのまま遊べます。

→ 作って学ぶPythonゲームプログラミング(完成した7本を遊んでみる)

基礎の文法に不安がある方は、先に無料の入門コース「作って学ぶPythonプログラミング入門」(全7章52レッスン)からどうぞ。
→ 無料の入門コースを見る

📚 関連商品・おすすめ書籍

スッキリわかるPython入門 第2版 (スッキリわかる入門シリーズ)

もしも

スッキリわかるPython入門 第2版 (スッキリわかる入門シリーズ)

初心者に定番のPython入門書

Amazonで見る
徹底攻略! 電子工作&プログラミング Arduinoで学ぶ電子工作完全ガイド

もしも

徹底攻略! 電子工作&プログラミング Arduinoで学ぶ電子工作完全ガイド

電子工作とプログラミングを同時に学べる

Amazonで見る
実践Claude Code入門―現場で活用するためのAIコーディングの思考法

もしも

実践Claude Code入門―現場で活用するためのAIコーディングの思考法

AIコーディングの現場活用法を学ぶ一冊

Amazonで見る

※本記事にはアフィリエイトリンクが含まれます。

ABOUT ME
やまちゃん
これまで学生と社会人を合わせて5000人以上にプログラミング学習を指導。 ゼロからイチをわかりやすく解説する専門家として活動しており、本業ではArduinoを用いたIoT開発とロボットプログラミングが専門。 Pythonを用いたアプリ開発、ウェブアプリケーションの開発で業務の効率化をサポートしています。