三目並べの全ての状態数とその遷移関係を数え上げるアルゴリズム

三目並べでとりうる盤面の状態数を数えてみた。

英語ではTicTacToeと言ってボードゲームAIの入門によく使われる題材だったりする。
ゲームの状態数はよく9マス×3状態で通りだとか最初は9通りで次の番は8通り…だから通りだとか言われるけれどどれも厳密な答えではない。
実は厳密な答えって探してもあんまり見つからない。そこでプログラムを組んで数え上げてみた。

# coding:utf-8
import numpy as np
from copy import deepcopy

BLANK = 0 # fix
BLACK = 1
WHITE = 2
SIMBOL = [" ","@","O",]


class Sanmoku():
    def __init__(self, n=3):
        self.graph = dict()
        self.value = dict()
        for i in range(pow(3,9)):
            self.graph[i] = []
            self.value[i] = 0
        self.make_graph()

    def display(self, number):
        board = self.num2board(number).reshape([3,3])
        for i in range(3):
            for j in range(3):
                print "|"+SIMBOL[board[i,j]],
            print "|\n"

    @staticmethod
    def num2board(number):
        if number < 0 or number > pow(3,9): return None
        number = int(number)
        map1d = np.zeros(9).astype(int)
        for i in range(9):
            map1d[i] = number%3
            number = number/3
        return map1d

    @staticmethod
    def board2num(board):
        return np.dot(board, pow(3 ,np.arange(9)))

    @staticmethod
    def is_over(board):
        """
        judge whether game is over : black wins 1 white wins -1
        """
        board2d = board.reshape([3,3])
        for i in range(3):
            if board2d[0,i] == board2d[1,i] and board2d[1,i] == board2d[2,i]:
                if board2d[0,i] == BLACK: return 1
                if board2d[0,i] == WHITE: return -1
            if board2d[i,0] == board2d[i,1] and board2d[i,1] == board2d[i,2]:
                if board2d[i,0] == BLACK: return 1
                if board2d[i,0] == WHITE: return -1
        if board2d[0,0] == board2d[1,1] and board2d[1,1] == board2d[2,2]:
            if board2d[0,0] == BLACK: return 1
            if board2d[0,0] == WHITE: return -1
        if board2d[2,0] == board2d[1,1] and board2d[1,1] == board2d[0,2]:
            if board2d[2,0] == BLACK: return 1
            if board2d[2,0] == WHITE: return -1
        return 0

    def make_graph(self):
        que = [[0,WHITE]]
        visited = dict()
        for i in self.graph.keys():
            visited[i] = False
        visited[0] = True
        while len(que) > 0:
            [number,turn] = que.pop(0)
            board = self.num2board(number)
            empty_index = [i for i, x in enumerate(board) if x == BLANK]
            if turn == BLACK: turn = WHITE
            else: turn = BLACK
            for i in empty_index:
                vboard = deepcopy(board)
                vboard[i] = turn
                new_num = self.board2num(vboard)
                self.graph[number].append(new_num)
                if not visited[new_num]:
                    visited[new_num] = True
                    reward = self.is_over(vboard)
                    if reward:
                        self.value[new_num] = reward
                        continue
                    que.append([new_num , turn])

        for i in self.graph.keys():
            if not visited[i]:
                self.graph.pop(i)
                self.value.pop(i)


if __name__=="__main__":
    import time
    start = time.time()
    sm = Sanmoku()
    end = time.time()
    print("%d [s]"%(end-start))
    print(len(sm.value))

`Sanmoku.graph`は辞書型で今の状態に対して次に遷移しうる状態が入る。
`Sanmoku.value`は辞書型で今の状態は白が勝ちか(-1)黒が勝ちか(1)が入る。

0 [s]
5478

結果として何も置いてない状態も含めて5478通りあることがわかりました！（黒先番は固定）

引数のあるコマンドをエイリアスに登録する方法（シェルスクリプト）

引数のあるコマンドをエイリアスに登録したい時、調べたのでメモ
例えば、複数のサーバーが用意されていてSSHするサーバーを使い分けるみたいな時。

ssh USER@SERVER1.com -p 8888
ssh USER@SERVER2.com -p 8888
ssh USER@SERVER3.com -p 8888
...

みたいなコマンドを一つにまとめたい。

そんな時はこう書く

function entercommand() { ssh USER@SERVER$1.com -p 8888 ; }

これで、

entercommand 1

でSERVER1.comを指定して入ることができる

余談

シェルのワンライナーで変数を使いたい

シェルのワンライナーで変数を使いたい時、例えば入出力のファイルの名前を揃えたい時などに便利。
書き方としてはこんな感じ

f() { ls ${1}; }; f ~/Documents/

入出力を揃える

f() { ffmpeg -ss 00:01:00 -i ${1}.mp4 -c copy -to 00:05:00 ${1}_cut.mp4; }; f sample

sample.mp4という動画ファイルを1:00から5:00までトリミングしsample_cut.mp4という名前で保存するワンライナー

粘菌に迷路を解かせるシミュレーション

粘菌は凄い！なぜかって、脳がないのに餌までの最短経路を見つけることができる。
これが神経細胞の始まりだとか言われていたり言われていなかったりする

以前から知ってはいたが、調べているとニコ動でこんな動画があった。ちゃんとできている！しかもエクセルで！

おおなんだ、これはすごい！自分でも再現したい！
ということで、自分で作ってみることにした。

アルゴリズムは人工生命的なセルオートマトン的な何かだろうと推測される。
映像を参考にしながら試行錯誤していこう。

まず単純な規則から考えてみる。
セルの状態として考えられるのは、

• エサ
• 粘菌
• かべ
• 空白

そして、基本的な事は

1. 道幅は1セル分のみ
2. 初期値ではすべての道に粘菌が存在する
3. ある規則に基づいて粘菌セルが空白セルに変わる、それ以外は不変

ということだろう。
そして恐らくある規則というのは、
「両隣が粘菌セルかエサであれば粘菌セルは生き残り、それ以外は隣の粘菌セルに吸収される。」
じゃないだろうか。

…なんとなくできそうだ、さっそく実装してみよう。

• ameba.py

import sys
import numpy as np
import matplotlib.pyplot as plt
import matplotlib.animation as animation
from copy import deepcopy

colors = {
    "empty":(1, 1, 1),
    "wall":(0, 0, 0),
    "feed":(1, 0, 0),
    "ameba":(1, 0.8, 0.2),
}
symbols = {
    "$":"wall",
    " ":"ameba",
    "s":"feed",
    "t":"feed",
}
stagefile = "stage.txt"


def stage2colors(stage):
    colormap = deepcopy(stage)
    for i in range(len(stage)):
        for j in range(len(stage[0])):
            colormap[i][j] = colors[stage[i][j]]
    return colormap

def update(stage):
    next_stage = deepcopy(stage)
    for i in range(1,len(stage)-1):
        for j in range(1,len(stage)-1):
            next_stage[i][j] = cell_rule(stage, i, j)
    return next_stage

def cell_rule(stage, i, j):
    result = stage[i][j]
    if stage[i][j] == "ameba":
        around_cells = 0
        for x,y in [(-1,0),(1,0),(0,-1),(0,1)]:
            if stage[i+x][j+y] in ["ameba","feed"]:
                around_cells += 1
        result = "ameba" if around_cells > 1 else "empty"
    return result

f = open(stagefile,"r")
lines = f.readlines()
stage = []
for line in lines:
    line = line.replace("\n","")
    line = line.replace("\r","")
    stage.append([symbols[i] for i in line])

ims = []
fig = plt.figure()
plt.axis('off')
for t in range(40):
    stage = update(stage)
    im = plt.imshow(stage2colors(stage), interpolation='none')
    ims.append([im])
ani = animation.ArtistAnimation(fig,ims)
plt.show()

• stage.txt

$$$$$$$$$$$$$$$$$
$   $   $       $
$ $ $ $ $ $$$$$ $
$ $ $ $ $ $   $ $
$ $ $ $$$ $ $ $ $
$ $ $   $ $ $   $
$ $ $ $ $ $ $$$$$
$ $ $ $ $t$   $ $
$ $$$ $ $$$ $ $ $
$     $  $  $ $ $
$ $$$ $ $$$ $ $ $
$ $   $ $   $   $
$$$ $$$$$ $$$ $ $
$   $         $ $
$ $$$ $$$$$$$$$ $
$   s           $
$$$$$$$$$$$$$$$$$

予想通りそれっぽいのができたぞ。
ただ、粘菌は環状になってる経路は最短距離で辿り着くようになってるよね。
実際の粘菌に近づけるにはもっと考えるところがありそう。