GOTO M.

趣味のコーディングとか、勉強とか、読書とか

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()