« ^ »

クッキーを探す

所要時間: 約 7分

諸事情により簡単なゲームを実装する機会を得た。ゲームは強化学習の練習用に扱う事ができる題材であれば、どんなものでもいい。だから単純であればあるほど良い。また必要なライブラリは少なければ少ないほど良い。そこでPythonと標準ライブラリである curses を使って宝探しをするゲームを作る事にした。

https://res.cloudinary.com/symdon/image/upload/v1683452994/blog.symdon.info/1683444176/game_dwesnm.gif

cursesでhello world

まずは curses の使い方をおさらいするために、ターミナルエミュレータ上に「😃 < Hello, world!」を表示するプログラムを書く。

import curses


stdscr = curses.initscr()                # 画面を初期化する
stdscr.addch(0, 0, "😃")                 # 1文字表示する
stdscr.addstr(0, 2, " < Hello, world!")  # 文字列を表示する
stdscr.refresh()                         # 画面の変更を反映する
stdscr.getch()                           # 入力を待ち受ける
curses.endwin()                          # cursesを終了する

まず stdscr = curses.initscr() により画面を初期化する。そして画面全体を表すウィンドウオブジェクトが返される。画面の操作はウィンドウオブジェクト stdscr を経由して行う。次に stdscr.addch() と stdscr.addstr() により文字の表示を行う。ただし、これだけでは表示は更新されない。 表示を更新する場合は stdscr.refresh() を呼び出す。表示を目で確認する時間を作るために stdscr.getch() で入力待ちをする。何かキーを入力すると処理が進行し、 curses.endwin() によって画面の状態が curses のものから元に戻る。出力は次のようになる。

https://res.cloudinary.com/symdon/image/upload/v1684062918/blog.symdon.info/1683444176/screen-2023-05-14_20.14.47_xmo7us.png

ここで紹介した機能は少しだが、他にもたくさんの機能はある1。しかし、この記事では基本的には、この機能だけで実装する。

クッキーを探す

それでは宝探しを始めることにしよう。まずは宝とは何かを考える。宝とは価値のあるもので、それを入手するとハッピーになるはずだ。ハッピーになれるもの、そんなものはこの世に1つしかない。それはクッキーだ。クッキーは小麦粉アレルギーを持っていない限り、食べるとハッピーになれる。そしてチョコチップが入っていたら、テンション爆アゲ間違いなしだ。何が言いたいかというと、良い感じの絵文字があったので今回はクッキー🍪を宝物として探し回ることにする。同じ理由で😃にクッキーを探してもらうことにする。😃はエージェントと呼ぶことにする。エージェントはハッピーになると😍になる。

🍪
ゴール。入手するとハッピーになる。
😃
エージェント。ゴールを探して動き回る。ハッピーになると😍になる。

クッキーと人生

ただ1つだけの道を進めば必ずゴールに辿りつく

世界が常にそうだったら、どんなに楽だろう。常に1つの道を真っ直ぐ進むだけで、欲しいものが手に入る。

import time
import curses
import itertools


stdscr = curses.initscr()

goal = [1, 80]
stdscr.addch(goal[0], goal[1], "🍪")

current = [1, 0]
stdscr.addch(current[0], current[1], "😃")

i = 0
stdscr.addstr(0, 0, f"age: {i:>4}")
stdscr.refresh()
stdscr.getch()

for i in itertools.count(start=1):
    stdscr.addstr(0, 0, f"age: {i:>4}")
    stdscr.addch(current[0], current[1], " ")
    current[1] = i
    if current == goal:
        stdscr.addch(current[0], current[1], "😍")
        stdscr.refresh()
        break
    
    stdscr.addch(current[0], current[1], "😃")
    stdscr.refresh()
    time.sleep(0.1)

stdscr.getch()
curses.endwin()

画面の右の方に表示されたゴールに向かって、左側から一直線でエージェントが移動する。ゴールに到達するとエージェントは停止する。

ただ、こんな都合が良い世界なんてものは存在しない。もしもゴールが別の行にあったら、右に真っ直ぐ進むだけでは、エージェントはゴールに辿りつけない。これを無限クッキー探し地獄と言う。

import time
import curses
import itertools


stdscr = curses.initscr()

goal = [30, 80]
stdscr.addch(goal[0], goal[1], "🍪")

current = [1, 0]
stdscr.addch(current[0], current[1], "😃")

i = 0
stdscr.addstr(0, 0, f"age: {i:>4}")
stdscr.refresh()
stdscr.getch()

for i in itertools.count(start=1):
    stdscr.addstr(0, 0, f"age: {i:>4}")
    stdscr.addch(current[0], current[1], " ")
    current[1] = i
    if current == goal:
        stdscr.addch(current[0], current[1], "😍")
        stdscr.refresh()
        break

    stdscr.addch(current[0], current[1], "😃")
    stdscr.refresh()
    time.sleep(0.1)

stdscr.getch()
curses.endwin()

引かれたレールの上だけを歩くだけでは、欲しいものなんて手に入らないのだ。現実は甘くない。

https://res.cloudinary.com/symdon/image/upload/v1684063106/blog.symdon.info/1683444176/game_gilu5s.gif

暗闇の中を手探りで進む

世界の外から俯瞰して、その世界を観測できれば、欲しいものがどこにあるかなんてすぐにわかるのかもしれない。でも、世界の中にいながらにして、その世界を外から俯瞰して観測するという事はできない。人生は暗闇の中を手探りで進むようなもので、たとえ適当に動き回っていたとしても探し続けれいたら、運が良ければ答えが見つかるかもしれない。ゴールに辿りつきたいなら、自ら動いてゴールを探さなければならない。

import random
import time
import curses
import itertools


stdscr = curses.initscr()

goal = [12, 20]
stdscr.addch(goal[0], goal[1], "🍪")

current = [10, 10]
stdscr.addch(current[0], current[1], "😃")

i = 0
stdscr.addstr(0, 0, f"age: {i:>4}")
stdscr.refresh()
stdscr.getch()

for i in itertools.count(start=1):
    stdscr.addstr(0, 0, f"age: {i:>4}")
    stdscr.addch(current[0], current[1], " ")
    
    axis = random.choice([0, 1])
    move = random.choice([-1, 1])

    # 画面外への移動を制限    
    if current[axis] + move >= 1:  
        current[axis] += move
    
    if current == goal:
        stdscr.addch(current[0], current[1], "😍")
        stdscr.refresh()
        break
    
    stdscr.addch(current[0], current[1], "😃")
    stdscr.refresh()
    time.sleep(0.1)

stdscr.getch()
curses.endwin()

決められる事はエージェントが動く方向だけで、必ず1ターン毎に縦か横に1マス移動する。ここでは移動の方向はランダムに移動するようにする。つまりランダムウォークする。ただしマイナスの座標の場合は、画面の外となりエラーが発生するために、そこには移動させないことにする。

https://res.cloudinary.com/symdon/image/upload/v1684063253/blog.symdon.info/1683444176/game_y3bida.gif

死ぬも生きるも天任せよ、恐れた奴が負けなのさ2。

誰しもいつかは死ぬ

人には寿命があり、いつかは死ぬ。これまでのエージェントは寿命の概念がないため、ゲームオーバーになるか、ハードウェアが壊れるまでクッキーを探し続けた。それではあまりに救いがない。だから寿命を設け安らかに眠れるようにする。日本の平均寿命はだいたい85歳前後だから、エージェントの寿命の85とする。寿命が尽きたエージェントは👽になり活動を停止する。

🍪
ゴール。入手するとハッピーになる。
😃
エージェント。ゴールを探して動き回る。ハッピーになると😍になる。寿命が尽きると👽になる。
import random
import time
import curses
import itertools


stdscr = curses.initscr()

goal = [12, 20]
stdscr.addch(goal[0], goal[1], "🍪")

current = [10, 10]
stdscr.addch(current[0], current[1], "😃")

i = 0
stdscr.addstr(0, 0, f"age: {i:>4}")
stdscr.refresh()
stdscr.getch()

for i in itertools.count(start=1):
    stdscr.addstr(0, 0, f"age: {i:>4}")
    stdscr.addch(current[0], current[1], " ")
    
    if i > 85:
        stdscr.addch(current[0], current[1], "👽")
        stdscr.refresh()
        break

    axis = random.choice([0, 1])
    move = random.choice([-1, 1])
    
    # 画面外への移動を制限    
    if current[axis] + move >= 1:  
        current[axis] += move
    
    if current == goal:
        stdscr.addch(current[0], current[1], "😍")
        stdscr.refresh()
        break
    
    stdscr.addch(current[0], current[1], "😃")
    stdscr.refresh()
    time.sleep(0.1)

stdscr.getch()
curses.endwin()

実行してみるとわかるが、ほとんどの場合でクッキーを見つけられずに天寿を全うしてしまうだろう。人生がいかに短いかという事がわかる。

https://res.cloudinary.com/symdon/image/upload/v1684063340/blog.symdon.info/1683444176/game_tqvchw.gif

後退りしない

臆病風に吹かれて後退りしていては、活路を見出す事はできない。後退りしてる暇なんてない。1つ前の座標に戻る事はやめて、前か右か左を向いて進もう。

import copy
import random
import time
import curses
import itertools


stdscr = curses.initscr()

goal = [12, 20]
stdscr.addch(goal[0], goal[1], "🍪")

current = [10, 10]
stdscr.addch(current[0], current[1], "😃")

i = 0
stdscr.addstr(0, 0, f"age: {i:>4}")
stdscr.refresh()
stdscr.getch()

history = []

for i in itertools.count(start=1):
    stdscr.addstr(0, 0, f"age: {i:>4}")
    stdscr.addch(current[0], current[1], " ")
    
    if i > 85:
        stdscr.addch(current[0], current[1], "👽")
        stdscr.refresh()
        break
    
    history.append(copy.deepcopy(current))
    while True:
        candidate = copy.deepcopy(current)
        move = random.choice([
            [  0,  1],
            [  0, -1],
            [  1,  0],
            [ -1,  0],
        ])
        candidate[0] += move[0]
        candidate[1] += move[1]
        
        # 画面外への移動を制限
        if candidate[0] <= 1 or candidate[1] <= 1:
            continue
        
        # さっき来た道には引き返さない
        if len(history) >= 2 and history[-2] == candidate:
            continue  

        current = candidate
        break
    
    if current == goal:
        stdscr.addch(current[0], current[1], "😍")
        stdscr.refresh()
        break
    
    stdscr.addch(current[0], current[1], "😃")
    stdscr.refresh()
    time.sleep(0.1)

stdscr.getch()
curses.endwin()

移動してきた履歴を保持しておき、1つ前の座標が移動先と同じ場合、それはさっき来た道だ。だからもう一度移動先の決定をやり直す。そうする事で今までよりも効率的な動きができる。

https://res.cloudinary.com/symdon/image/upload/v1684063482/blog.symdon.info/1683444176/game_a31njk.gif

諦めない心で寿命の限界を突破する

これまで、無限クッキー探し地獄から開放されるため寿命を導入した。そして寿命が尽きたらクッキーを諦めてきた。しかし本当に諦められるのか、諦められないものもあるのではないか、という疑問が湧いてくる。

諦められるはずがない。だから諦めないという強い心で寿命の限界を突破する。ただし無限クッキー探し地獄はやっぱり嫌なので、無限寿命ではない方法で突破する。

寿命が尽きても再生する

寿命が尽きても、もう一度誕生して、またクッキーを探せばいいさ。

import copy
import random
import time
import curses
import itertools


while True:
    stdscr = curses.initscr()
    
    goal = [12, 20]
    stdscr.addch(goal[0], goal[1], "🍪")
    
    current = [10, 10]
    stdscr.addch(current[0], current[1], "😃")
    
    i = 0
    stdscr.addstr(0, 0, f"age: {i:>4}")
    stdscr.refresh()
    stdscr.getch()
    
    history = []
    
    for i in itertools.count(start=1):
        stdscr.addstr(0, 0, f"age: {i:>4}")
        stdscr.addch(current[0], current[1], " ")
        
        if i > 85:
            stdscr.addch(current[0], current[1], "👽")
            stdscr.refresh()
            break
        
        history.append(copy.deepcopy(current))
        while True:
            candidate = copy.deepcopy(current)
            move = random.choice([
                [  0,  1],
                [  0, -1],
                [  1,  0],
                [ -1,  0],
            ])
            candidate[0] += move[0]
            candidate[1] += move[1]
            
            # 画面外への移動を制限
            if candidate[0] <= 1 or candidate[1] <= 1:
                continue
            
            # さっき来た道には引き返さない
            if len(history) >= 2 and history[-2] == candidate:
                continue  
    
            current = candidate
            break
        
        if current == goal:
            stdscr.addch(current[0], current[1], "😍")
            stdscr.refresh()
            break
        
        stdscr.addch(current[0], current[1], "😃")
        stdscr.refresh()
        time.sleep(0.1)
    
    stdscr.getch()
    curses.endwin()

無限クッキー探し地獄と違うところは、無限クッキー探し地獄は遠く離れた地に行ってしまったら戻ってくる事がとても大変だ。きっともう戻ってこれない。そこにクッキーがなくても戻ってこれない。再生は、寿命が尽きたら最初の座標からやり直せる。

https://res.cloudinary.com/symdon/image/upload/v1684063594/blog.symdon.info/1683444176/game_fdxx9l.gif

優秀な個体が次の世代に遺伝子を残す

生き物は進化する。その進化の仕組みを応用したアルゴリズムは遺伝的アルゴリズムと呼ばれる。この遺伝的アルゴリズムを使ってニューラルネットワークの構造に変化を与える手法にNEATというものがある。この手法を使ってクッキーを探す事もできるはずだ。それについては、別のサイトに掲載させていただける事になった3。

1

https://docs.python.org/ja/3/library/curses.html

2

https://one-piece.com/character/Marshall_D_Teech/index.html

3

https://oreilly-japan.github.io/OpenEndedCodebook/app1/