Solving "Canterbury Puzzles" by Python (2)
続き。今回は、ターン制ゲームの実装。
109. 三目並べ
三目並べ、先手が勝つか、後手が勝つか、それとも引き分けになるか、を分析する問題。
#! -*- encoding=utf-8 -*- # # 109. Noughts and Crosses # import copy import math def main(): f = Field() print who_wins(f, 1) ## field(盤面)とturn(手番、1または-1)とを受け取り、 ## 勝利する手が有れば turn を、 ## 勝利的ないが引き分けが可能なら 0 を返す。 def who_wins(field, turn): if field.check() == change_turn(turn): # 既に勝負が付いている場合 return change_turn(turn) elif len(field.unoccupied()) == 0: # 盤面が埋まってしまった場合(引き分け) return 0 else: rtn = change_turn(turn) # 可能な手ごとに、再帰的に who_wins を呼び出す for hand in field.unoccupied(): next_field = copy.deepcopy(field) next_field.set(hand[0], hand[1], turn) w = who_wins(next_field, change_turn(turn)) if math.fabs(rtn - turn) > math.fabs(w - turn): # 探索済みの手より良い手が見つかった場合 rtn = w if rtn == turn: # 勝利する手が見つかった場合 break return rtn def change_turn(turn): return 0 - turn ## 盤面を表すクラス class Field(): # 全面を0(空白)で初期化する def __init__(self): self.field = [[0,0,0],[0,0,0],[0,0,0]] # 特定の枡に値を設定する def set(self,x,y,turn): self.field[x][y] = turn # 盤面を表示する def show(self): for column in self.field: print column # 値が設定されていない枡のリストを返す def unoccupied(self): rtn = [] for i in range(0,3): for j in range(0,3): if self.field[i][j] == 0: rtn.append((i,j)) return rtn # 揃っているラインが有った場合、そのラインの値(1または-1)を返す # 揃っているラインが無い場合、0を返す def check(self): # 縦のラインをチェック if self.field[0][0] == self.field[1][0] == self.field[2][0] != 0: return self.field[0][0] elif self.field[0][1] == self.field[1][1] == self.field[2][1] != 0: return self.field[0][1] elif self.field[0][2] == self.field[1][2] == self.field[2][2] != 0: return self.field[0][2] # 横のラインをチェック elif self.field[0][0] == self.field[0][1] == self.field[0][2] != 0: return self.field[0][0] elif self.field[1][0] == self.field[1][1] == self.field[1][2] != 0: return self.field[1][0] elif self.field[2][0] == self.field[2][1] == self.field[2][2] != 0: return self.field[2][0] # 斜めのラインをチェック elif self.field[0][0] == self.field[1][1] == self.field[2][2] != 0: return self.field[0][0] elif self.field[0][2] == self.field[1][1] == self.field[2][0] != 0: return self.field[0][2] else: return 0 # 盤面にユニークなIDを割り当てる(本門んは使用せず) def get_id(self): rtn = 0 for i in range(0,3): for j in range(0,3): rtn += (self.field[i][j] + 1) * 3**(3*i + j) return rtn if __name__ == '__main__': main()