Pythonのスタックで「1手もどす」を作る!appendとpopで手の履歴を管理|ゲームで学ぶアルゴリズム 第3回
前回:Pythonで座標とリストの番号を変換する!divmodとクリック位置の計算|ゲームで学ぶアルゴリズム 第2回
「パズルゲームに『1手もどす』ボタンを付けたいけど、どう作ればいいの?」「もどしたら、取ったはずのコインが消えたままになった…」
動かすところまではできても、もどす処理で手が止まること、ありますよね。この記事は連載「ゲームで学ぶアルゴリズム」の第3回です。今回はスタックというデータの持ち方を使って、1手もどす機能(undo)を作ります。
対象は、リストの append() を使ったことがある初心者〜初級者の方です。動作確認は Python 3.13 で行いました。一緒に見ていきましょう! 😊
スタックとは:最後に積んだものから取り出す

スタックは、最後に入れたものを最初に取り出す入れ物です。イメージとしては、机に積んだお皿の山。上に重ねたお皿から順に取りますよね。
ゲームの「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() # 空のスタックから取り出すと?

積んだあと: ['右', '右', '下']
取り出した: 下
残り: ['右', '右']
取り出さずに上をのぞく: 右
積んである数: 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("全部もどしたあと")

--- スタート(コイン 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レッスン)からどうぞ。
→ 無料の入門コースを見る
こちらも読まれています
📚 関連商品・おすすめ書籍
※本記事にはアフィリエイトリンクが含まれます。




