コンピュータ囲碁の作成 原始モンテカルロ囲碁の実装

#コンピュータ囲碁
・コンピュータ囲碁の作成メモ。
・原始モンテカルロ囲碁の実装

今回もかなり苦戦しています。
原始モンテカルロ囲碁が作成できたと思いますが，かなり遅いです。

##参考記事
原始モンテカルロ囲碁

##関連記事
コンピュータ囲碁の作成
コンピュータ囲碁の作成　ランダム打ちの実装
コンピュータ囲碁の作成　ルールの実装

#ソースコード

# -*- coding:utf-8 -*-
import random
import time
import copy
# 碁盤
BOARD_SIZE = 9				# 碁盤の大きさ

KOMI = 6.5

# 盤上の種類
SPACE,BLACK,WHITE,WALL = 0,1,2,3
VISUAL = ("・","🔴 ","⚪️ ", "　")
DIR4 = (-1,0),(1,0),(0,-1),(0,1)
# 石を打ったときの処理
SUCCESS = 0 		# 打てる
KILL 	= 1 		# 自殺手
KO 		= 2 		# 劫
ME 		= 3 		# 眼
MISS 	= 4 		# すでに石がある
PASS 	= 5 		# パス

# 戦略
RANDOM = 1
MONTE_CARLO = 2

ERROR_MESSAGE = {KILL:	"自殺手",
				 KO: 	"劫",
				 ME:	"眼",
				 MISS:	"すでに石がある",
				 PASS:	"パス",
				 }

'''
時間計測テンプレート
start = time.time()
elapsed_time = time.time() - start
print ("elapsed_time:{0}".format(elapsed_time)) + "[sec]"
'''

# 碁盤　
class Board(object):
	# 碁盤作成
	def __init__(self,size):
		self.size = size + 2 	# 上下左右に外枠を含めた碁盤
		self.data = data = [[SPACE]*self.size for i in range(self.size)]
		# 外枠の作成
		for i in range(self.size):
			data[0][i] = data[-1][i] = data[i][0] = data[i][-1] = WALL
		# 直前に取った劫の位置
		self.ko = None

	def get(self,position):
		y,x = position
		return self.data[y][x]

	def set(self,position,stone):
		y,x = position
		self.data[y][x] = stone
	# 石を取り除く
	def remove(self,position):
		self.set(position,SPACE)

	# 碁盤描画
	def draw(self):
		print "  ", " ".join("%2d"%x for x in range(1,self.size-1))
		for y in range(1,self.size-1):
			print "%2d"%y, " ".join(VISUAL[data] for data in self.data[y][1:-1])

	# 盤上の空の場所を配列で取得
	def getNonePositions(self):
		return [(y, x)
				for y in range(1, self.size-1)
				for x in range(1, self.size-1)
				if self.data[y][x] == SPACE]


class JoinedLibertyCounter(object):
	def __init__(self,board):
		self.board = board

	def count(self,position,stone):
		return self.count_sub(position,stone,[])

	def  count_sub(self,position,stone,checked,joined=0,liberty=0):
		checked.append(position)
		joined += 1
		y,x = position
		for dy,dx in DIR4:
			adjacent = (y+dy,x+dx)
			if adjacent in checked:
				continue
			if self.board.get(adjacent) == SPACE:
				checked.append(adjacent)
				liberty+=1
			elif self.board.get(adjacent) == stone:
				joined, liberty = self.count_sub(adjacent,stone,checked,joined,liberty)
		return joined, liberty

class Player(object):

	def __init__(self,color,tact):
		self.color = color
		self.un_color = WHITE if color == BLACK else BLACK
		self.tact = tact

	# 戦術を選択
	def tactics(self,board,positions):
		if self.tact == RANDOM:
			return random_choice(self,board,positions)
		if self.tact == MONTE_CARLO:
			return monte_carlo(self,board,positions)

	# 相手の石を取る
	def capture(self,board, position):
		board.remove(position)
		y,x = position
		for dy,dx in DIR4:
			around = (y+dy,x+dx)
			if board.get(around) == self.un_color:
				self.capture(board,around)
	# 石を打つ
	def move(self,board,position):
		if position == (0,0):
			return PASS
		# すでに石がある場合
		if board.get(position) != SPACE:
			return MISS

		# positionに対して4方向の[連石の数，呼吸点の数，色]
		joineds	 = [0]*4
		libertys = [0]*4
		colors 	 = [0]*4

		space = 0 		# 4方向の空白の数
		wall  = 0 		# 4方向の壁の数
		mikata_safe = 0 # 呼吸点が2以上の味方の数
		take_sum = 0 	# 取れる石の合計
		ko = None 		# 劫の候補

		# 打つ前に4方向を調べる
		joined_liberty = JoinedLibertyCounter(board)
		y,x = position
		for i, (dy,dx) in enumerate(DIR4): 	# enumerate:インデックスとともにループ
			around = (y+dy,x+dx)
			colors[i] = c = board.get(around)
			if c == SPACE:
				space += 1
				continue
			if c == WALL:
				wall += 1
				continue

			# 連石と呼吸点の数を数える
			joineds[i],libertys[i] = joined_liberty.count(around,c)
			# 相手の石が取れるなら，劫の可能性があるので保持
			if c == self.un_color and libertys[i] == 1:
				take_sum += joineds[i]
				ko = around
			# 味方の石があって呼吸点が2つ以上あるなら眼の可能性
			if c == self.color and libertys[i] >= 2:
				mikata_safe += 1

		# ルール違反の処理
		# 敵の石に４方を囲まれている
		if take_sum == 0 and space == 0 and mikata_safe == 0:
			return KILL
		# 劫
		if position == board.ko:
			return KO
		# 眼には置かない (ルール違反ではない)
		if wall + mikata_safe == 4:
			return ME

		# 石を取る
		for i, (dy,dx) in enumerate(DIR4):
			if colors[i] == self.un_color and libertys[i] == 1:
				self.capture(board,(y+dy,x+dx))

		# 石を打つ
		board.set(position,self.color)

		# 劫を取った直後は相手が取り返せないようにする
		joined,liberty = joined_liberty.count(position,self.color)
		if take_sum == 1 and joined == 1 and liberty == 1:
			board.ko = ko 		# 碁盤に劫の目印をつけておく
		else:
			board.ko = None 	# 劫の目印を消す

		return SUCCESS

	# 置ける場所を配列で取得
	def getSuccessPositions(self,board):
		# 石を置ける場所を探すために，deepcopyした碁盤に石を置いて確認する
		return [(y,x)
				for y in xrange(1,board.size-1)
				for x in xrange(1,board.size-1)
				#if self.move(copy.deepcopy(board),(y,x)) == SUCCESS
				if board.get((y,x)) == SPACE
				and self.move(copy.deepcopy(board),(y,x)) == SUCCESS
				]
# turn_colorが打つところから終局まで打ち，勝敗を返す
def playout(color,board,positions):
	playout_start = time.time()

	turn_player = Player(color,RANDOM) 					# ターンプレイヤー
	wait_player = Player(turn_player.un_color,RANDOM)	# 待機プレイヤー
	turn  = {turn_player:wait_player, wait_player:turn_player}
	board_copy = copy.deepcopy(board) 					# 試し打ち用ボード
	start1 = time.time()

	# 空点取得　試し打ち候補
	positions_copy = copy.deepcopy(positions) 			
	# 先手
	player = turn_player
	# 対局開始
	passed = 0

	elapsed_time1 = time.time() - start1
	
	# print ("elapsed_time1:{0}".format(elapsed_time1)) + "[sec]"
	start2 = time.time()

	while passed < 2:
		while True:
			# 手がないならパス
			if len(positions_copy) == 0:
				result = PASS
			else:
				# 手があるなら取得する 
				position = random.choice(positions_copy)
				result = player.move(board_copy,position) 		# 石を打つ
			if result == SUCCESS:
				#print VISUAL[player.color],position
				passed = 0
				break
			elif result == PASS:
				#print VISUAL[player.color],ERROR_MESSAGE[result]
				passed += 1
				break
			else:
				positions_copy.remove(position) 			# 候補から外す
				#print VISUAL[player.color],ERROR_MESSAGE[result],position
		elapsed_time2 = time.time() - start2
		#board_copy.draw()
		# プレイヤー交代
		player = turn[player]
	# 終局
	#time.sleep(3)
	# 勝敗を返す
	score = score_counter(turn_player.color,board_copy)
	playout_elapsed_time = time.time() - playout_start
	#print ("playout_elapsed_time:{0}".format(playout_elapsed_time)) + "[sec]"
	#print ("elapsed_time2:{0}".format(elapsed_time2)) + "[sec]"
	# time.sleep(0)
	return score
def random_choice(player,board,positions):
	board_copy = copy.deepcopy(board)
	positions_copy = copy.deepcopy(positions)
	random.shuffle(positions_copy)
	position = (0,0)
	for p in positions_copy:
		result = player.move(board_copy,p) 	# 石を打つ
		if result == SUCCESS: 						# 違反したら次
			position = p
			break
	return position

def monte_carlo(player,board,positions):
	monte_start = time.time()
	playout_count = 0

	TRY_GAMES = 30
	best_value = -999
	board_copy = copy.deepcopy(board)
	positions_copy = copy.deepcopy(positions)

	best_position = (0,0)
	count = 0

	random.shuffle(positions_copy)
	# すべての手に対して1手打ってみる
	for position in positions_copy:
		win_sum = 0
		result = player.move(board_copy,position) 	# 石を打つ
		positions_copy.remove(position) 			# 候補から外す
		if result != SUCCESS: 						# 違反したら次
			continue

		# (相手の手から)playoutをTRY_GAMES回繰り返す
		for i in range(TRY_GAMES):
			win_sum -= playout(player.un_color,board_copy,positions_copy)
			count += 1

		# 勝率が最も高いものを選ぶ
		win_rate = win_sum/TRY_GAMES
		if win_rate > best_value:
			best_value = win_rate
			best_position = position
	
	monte_elapsed_time = time.time() - monte_start
	print count
	print ("monte_elapsed_time:{0}".format(monte_elapsed_time)) + "[sec]"
	#time.sleep(2)
	return best_position


# 終局のスコアを計算 1:黒の勝ち -1:白勝ち　　AIは空点があれば打つので空点の4方向を調べればよい
def score_counter(turn_color,board):
	score = 0
	# 盤上の[空点,黒石，白石]の数を取得
	kind = [0,0,0]
	for y in xrange(1,board.size-1):
		for x in xrange(1,board.size-1):
			col = board.data[y][x]
			kind[col] += 1
			# 空点は4方向の石の種類を調べる
			if col != SPACE:
				continue
			# mk[0] 空，[1] 黒，[2] 白，[3] 盤外
			mk = [0]*4
			for (dy,dx) in DIR4:
				mk[board.data[y+dy][x+dx]]+=1
			# 黒だけに囲まれていれば黒地
			if mk[1] > 0 and mk[2] == 0:
				score += 1
			# 白だけに囲まれていれば白地
			if mk[2] > 0 and mk[1] == 0:
				score -= 1
	# 地+盤上の石数
	score += kind[1] - kind[2]

	# コミを考慮した結果
	final_score = score - KOMI
	win = 0
	# turn_colorが黒で黒が勝っていれば1　負けていれば0
	if final_score > 0 :
		win = 1
	# turn_colorが白で白が勝っていれば0　負けていれば-1
	if turn_color == WHITE:
		win = -1
	return win

def judge(score):
	if score == 1:
		print VISUAL[BLACK],"勝ち"
	else:
		print VISUAL[WHITE],"勝ち"


def main():
	main_start = time.time()

	# 碁盤
	board = Board(BOARD_SIZE)

	# プレイヤー
	black = Player(BLACK,MONTE_CARLO)
	white = Player(WHITE,RANDOM)
	turn  = {black:white, white:black}

	# 先手
	player = black

	# 対局開始
	passed = 0
	while passed < 2:
		# 盤上の空点を取得	
		positions = board.getNonePositions()
		if len(positions) == 0:		# 打てないならパス
			result = PASS
		elif player == black:
			# 原始モンテカルロで打つ場所を取得
			position = player.tactics(board,positions)
			result = player.move(board,position) 	# 打ってみる
		elif player == white:
			# ランダムに打つ場所を取得
			position = player.tactics(board,positions)
			result = player.move(board,position) 	# 打ってみる

		if result == SUCCESS: 			# 打てたら描画 選択終了
			passed = 0
			print VISUAL[player.color],position
			board.draw()
			print
		elif result == PASS:
			passed += 1
			print VISUAL[player.color],ERROR_MESSAGE[result]
		else: 							# 違反ならもう一度探す
			print VISUAL[player.color],ERROR_MESSAGE[result],position
			player = turn[player]
		# プレイヤー交代
		player = turn[player]
		#time.sleep(0)

	board.draw()
	print "対局終了"	
	judge(score_counter(BLACK,board))

	main_elapsed_time = time.time() - main_start
	print ("main_elapsed_time:{0}".format(main_elapsed_time)) + "[sec]"


if __name__ == '__main__':
	main()

##github
https://github.com/Tsunehiko511/python_Go_origin
master：１次元配列
branch：２次元配列
#参考図書
コンピュータ囲碁 ―モンテカルロ法の理論と実践―