0

## 用python程式解井字遊戲的盤面，先能窮舉三步棋就好 #只要找到程式碼錯誤即給最佳解答

(但本題希望能指出程式碼錯誤為佳)

1. 能指出原程式碼錯誤並修正
2. 不知怎麼修正原程式碼錯誤但寫出自己的版本能過測試
3. 隻字片語或提供想法

debug一整天實在寫不出來才來求助

# 問題描述

``````# 寫井字遊戲的基本邏輯，棋子共'X','O'兩種
class TicTacToe():
def __init__(self):
self.board = [[' ']*3 for i in range(3)]

# 初始化棋盤
def iniBoard(self):
for i in range(3):
for j in range(3):
self.board[i][j]=' '

# 視覺化的把井字棋棋盤畫出來
def drawBoard(self) -> None:
HLINE =  ' ' * 3 + '+---' * 3  + '+'
VLINE = (' ' * 3 +'|') *  (3 +1)
title = '     0'
for i in range(1,3):
title += ' ' * 3 +str(i)
print(title)
print(HLINE)
for y in range(3):
print(VLINE)
print(y, end='  ')
for x in range(3):
print(f'| {self.board[x][y]}', end=' ')
print('|')
print(VLINE)
print(HLINE)

def isOnBoard(self, x, y):
return 0 <= x < 3 and 0 <= y < 3

#檢查tile放在某個座標是否為合法棋步
def isValidMove(self, tile, x, y):
return self.isOnBoard(x, y) and self.board[x][y]==' '

# 把棋子下在座標x, y的地方
def makeMove(self, tile, x, y):
if self.isValidMove(tile, x, y):
self.board[x][y]=tile

# 回傳現在盤面輪到tile走的所有合法棋步
def getValidMoves(self, tile):
return [[x, y] for x in range(3) for y in range(3) if self.isValidMove(tile, x, y)]

# 判斷一個盤面是否有人贏了
def check_TicTacToe(self):
rows = list(map(''.join,self.board))
cols = list(map(''.join, zip(*rows)))
diags = list(map(''.join, zip(*[(r[i], r[2 - i]) for i, r in enumerate(rows)])))
lines = rows + cols + diags

if 'XXX' in lines:
return 'X'
if 'OOO' in lines:
return 'O'
return 'D' # draw(和棋)
``````

``````     0   1   2
+---+---+---+
|   |   |   |
0  |   |   |   |
|   |   |   |
+---+---+---+
|   |   |   |
1  |   |   |   |
|   |   |   |
+---+---+---+
|   |   |   |
2  |   |   |   |
|   |   |   |
+---+---+---+
``````

# 電腦下棋的邏輯

TicTacToeAI實作alpha-beta演算法，

``````
import random
from copy import deepcopy

class Node(TicTacToe):
def __init__(self, board):
super().__init__()
self.board = deepcopy(board)

def ending(self):
return self.check_TicTacToe()!='D'

# 'X'贏的話得分
def valuef(self):
winTile = self.check_TicTacToe()
if winTile == 'X':
return 100
elif winTile == 'O':
return -100
return 0

# 電腦ai下棋的邏輯
class TicTacToeAI(TicTacToe):
def __init__(self, board):
super().__init__()
self.board = board

"""
參數: node代表盤面，depth是窮舉幾步棋，isMaxPlayer為True時換'X'走
alpha, beta是alpha-beta演算法的參數，如果看不懂，
理論上你把我函數的
if beta <= alpha:
break
註解掉即是min-max演算法，
代表說窮舉所有棋步不剪枝
"""
def alphabeta(self, node, depth, alpha, beta, isMaxPlayer):
if depth==0 or node.ending():
return [-1,-1], node.valuef()

if isMaxPlayer: # 'X'的回合
bestop, bestScore = [-1,-1], -99999999
moves = node.getValidMoves('X')
random.shuffle(moves)
for move in moves:

newNode = Node(self.board)
newNode.makeMove('X', move[0], move[1])

M, score = self.alphabeta(newNode, depth-1, alpha,beta,False)

if score> bestScore:
bestop = move[:]
bestScore = score

alpha = max(alpha, bestScore)
if beta <= alpha:
break
return bestop, bestScore

else: # 'O'的回合
bestop, bestScore = [-1,-1], 99999999
moves = node.getValidMoves('O')
random.shuffle(moves)
for move in moves:

newNode = Node(self.board)
newNode.makeMove('O', move[0], move[1])

M, score = self.alphabeta(newNode, depth-1, alpha,beta,True)

if score< bestScore:
bestop = move[:]
bestScore = score

beta = min(beta, bestScore)
if beta <= alpha:
break
return bestop, bestScore

# 給定盤面board，回傳電腦的選擇
def getComputerMove(self, computerTile):
root = Node(self.board)
isMaxPlayer = (computerTile == 'X')
move, score = self.alphabeta(root, 3, -999,999, isMaxPlayer)
return move
``````

# 三個測試的盤面

``````     0   1   2
+---+---+---+
|   |   |   |
0  | O |   |   |
|   |   |   |
+---+---+---+
|   |   |   |
1  | O | X |   |
|   |   |   |
+---+---+---+
|   |   |   |
2  | X |   |   |
|   |   |   |
+---+---+---+
``````

``````     0   1   2
+---+---+---+
|   |   |   |
0  | X |   |   |
|   |   |   |
+---+---+---+
|   |   |   |
1  | X | O |   |
|   |   |   |
+---+---+---+
|   |   |   |
2  | O |   |   |
|   |   |   |
+---+---+---+
``````

X下在座標1,2或2,2皆可必勝

``````     0   1   2
+---+---+---+
|   |   |   |
0  |   |   | O |
|   |   |   |
+---+---+---+
|   |   |   |
1  | O | X |   |
|   |   |   |
+---+---+---+
|   |   |   |
2  | X |   |   |
|   |   |   |
+---+---+---+
``````

``````import unittest

class Test(unittest.TestCase):

def test_basic(self):
game = TicTacToe()
game.makeMove('O',0,0)
game.makeMove('O',0,1)
game.makeMove('X',1,1)
game.makeMove('X',0,2)
ai = TicTacToeAI(game.board)
move = ai.getComputerMove('X')
ai.drawBoard()
self.assertEqual(move, [2,0])

def test_basic2(self):
game = TicTacToe()
game.makeMove('X',0,0)
game.makeMove('X',0,1)
game.makeMove('O',1,1)
game.makeMove('O',0,2)
ai = TicTacToeAI(game.board)
move = ai.getComputerMove('X')
ai.drawBoard()
self.assertEqual(move, [2,0])

def test_fixDatas(self):
game = TicTacToe()
game.makeMove('O',2,0)
game.makeMove('O',0,1)
game.makeMove('X',1,1)
game.makeMove('X',0,2)
ai = TicTacToeAI(game.board)
move = ai.getComputerMove('X')
ai.drawBoard()
self.assertIn(move, [[1,2],[2,2]])

unittest.main()
``````

# 完整測試的程式碼

unitest的class當然不能改，

``````import random
import unittest
from copy import deepcopy

# 寫井字遊戲的基本邏輯，棋子共'X','O'兩種
class TicTacToe():
def __init__(self):
self.board = [[' ']*3 for i in range(3)]

# 初始化棋盤
def iniBoard(self):
for i in range(3):
for j in range(3):
self.board[i][j]=' '

# 視覺化的把井字棋棋盤畫出來
def drawBoard(self) -> None:
HLINE =  ' ' * 3 + '+---' * 3  + '+'
VLINE = (' ' * 3 +'|') *  (3 +1)
title = '     0'
for i in range(1,3):
title += ' ' * 3 +str(i)
print(title)
print(HLINE)
for y in range(3):
print(VLINE)
print(y, end='  ')
for x in range(3):
print(f'| {self.board[x][y]}', end=' ')
print('|')
print(VLINE)
print(HLINE)

def isOnBoard(self, x, y):
return 0 <= x < 3 and 0 <= y < 3

#檢查tile放在某個座標是否為合法棋步
def isValidMove(self, tile, x, y):
return self.isOnBoard(x, y) and self.board[x][y]==' '

# 把棋子下在座標x, y的地方
def makeMove(self, tile, x, y):
if self.isValidMove(tile, x, y):
self.board[x][y]=tile

# 回傳現在盤面輪到tile走的所有合法棋步
def getValidMoves(self, tile):
return [[x, y] for x in range(3) for y in range(3) if self.isValidMove(tile, x, y)]

# 判斷一個盤面是否有人贏了
def check_TicTacToe(self):
rows = list(map(''.join,self.board))
cols = list(map(''.join, zip(*rows)))
diags = list(map(''.join, zip(*[(r[i], r[2 - i]) for i, r in enumerate(rows)])))
lines = rows + cols + diags

if 'XXX' in lines:
return 'X'
if 'OOO' in lines:
return 'O'
return 'D' # draw(和棋)

class Node(TicTacToe):
def __init__(self, board):
super().__init__()
self.board = deepcopy(board)

def ending(self):
return self.check_TicTacToe()!='D'

# 'X'贏的話得分
def valuef(self):
winTile = self.check_TicTacToe()
if winTile == 'X':
return 100
elif winTile == 'O':
return -100
return 0

# 電腦ai下棋的邏輯
class TicTacToeAI(TicTacToe):
def __init__(self, board):
super().__init__()
self.board = board

def alphabeta(self, node, depth, alpha, beta, isMaxPlayer):
if depth==0 or node.ending():
return [-1,-1], node.valuef()

if isMaxPlayer: # 'X'的回合
bestop, bestScore = [-1,-1], -99999999
moves = node.getValidMoves('X')
random.shuffle(moves)
for move in moves:

newNode = Node(self.board)
newNode.makeMove('X', move[0], move[1])

M, score = self.alphabeta(newNode, depth-1, alpha,beta,False)

if score> bestScore:
bestop = move[:]
bestScore = score

alpha = max(alpha, bestScore)
if beta <= alpha:
break
return bestop, bestScore

else: # 'O'的回合
bestop, bestScore = [-1,-1], 99999999
moves = node.getValidMoves('O')
random.shuffle(moves)
for move in moves:

newNode = Node(self.board)
newNode.makeMove('O', move[0], move[1])

M, score = self.alphabeta(newNode, depth-1, alpha,beta,True)

if score< bestScore:
bestop = move[:]
bestScore = score

beta = min(beta, bestScore)
if beta <= alpha:
break
return bestop, bestScore

# 給定盤面board，回傳電腦的選擇
def getComputerMove(self, computerTile):
root = Node(self.board)
isMaxPlayer = (computerTile == 'X')
move, score = self.alphabeta(root, 3, -999,999, isMaxPlayer)
return move

class Test(unittest.TestCase):

def test_basic(self):
game = TicTacToe()
game.makeMove('O',0,0)
game.makeMove('O',0,1)
game.makeMove('X',1,1)
game.makeMove('X',0,2)
ai = TicTacToeAI(game.board)
move = ai.getComputerMove('X')
ai.drawBoard()
self.assertEqual(move, [2,0])

def test_basic2(self):
game = TicTacToe()
game.makeMove('X',0,0)
game.makeMove('X',0,1)
game.makeMove('O',1,1)
game.makeMove('O',0,2)
ai = TicTacToeAI(game.board)
move = ai.getComputerMove('X')
ai.drawBoard()
self.assertEqual(move, [2,0])

def test_fixDatas(self):
game = TicTacToe()
game.makeMove('O',2,0)
game.makeMove('O',0,1)
game.makeMove('X',1,1)
game.makeMove('X',0,2)
ai = TicTacToeAI(game.board)
move = ai.getComputerMove('X')
ai.drawBoard()
self.assertIn(move, [[1,2],[2,2]])

unittest.main()
``````

### 1 個回答

1
zhweiliu
iT邦新手 5 級 ‧ 2020-07-15 00:25:00

(我知道可以用 numpy 或 dataframe 來解，但那不是目前的場域XD)

``````#檢查tile放在某個座標是否為合法棋步
def isValidMove(self, tile, x, y):
return self.isOnBoard(x, y) and self.board[x][y]==' '
``````

isValidMove 用不到 tile 變數，依當前程式片段來看是要找出所有空格

``````# 回傳現在盤面輪到tile走的所有合法棋步
def getValidMoves(self, tile):
return [[x, y] for x in range(3) for y in range(3) if self.isValidMove(tile, x, y)]
``````

``````moves = node.getValidMoves('X')
random.shuffle(moves)
for move in moves:

newNode = Node(self.board)
newNode.makeMove('X', move[0], move[1])

M, score = self.alphabeta(newNode, depth-1, alpha,beta,False)

if score> bestScore:
bestop = move[:]
bestScore = score

alpha = max(alpha, bestScore)
if beta <= alpha:
break
return bestop, bestScore
``````

``````# 這一行的 recursive 只考慮相同一方連走3步
# 但考量實際的規則情況下
# 應該是雙方交互總共下 3步 = 往後看 1 局結果
# 或者是雙方交互下棋各 3 步 = 往後看 3 局結果
M, score = self.alphabeta(newNode, depth-1, alpha,beta,False)
``````

``````# 'X'贏的話得分
def valuef(self):
if winTile == 'X':
return 100
elif winTile == 'O':
return -100
return 0
``````

``````M, score = self.alphabeta(newNode, depth-1, alpha,beta,False)
``````

``````M, score = self.alphabeta(newNode, depth-1, alpha,beta, not isMaxPlayer)
``````

TicTacToe 應該是零和賽局，最佳棋步應該要採納 greedy strategy 較為合適

``````line_map = [
[(0,0), (0,1), (0,2)],
[(1,0), (1,1), (1,2)],
[(2,0), (2,1), (2,2)],
[(0,0), (1,0), (2,0)],
[(1,0), (1,1), (1,2)],
[(2,0), (2,1), (2,2)],
[(0,0), (1,1), (2,2)],
[(0,2), (1,1), (2,0)],
]
``````

``````newNode = Node(self.board)
newNode.makeMove('X', move[0], move[1])
``````

``````newNode = Node(node.board)
newNode.makeMove('X', move[0], move[1])
``````

``````newNode = Node(self.board)
newNode.makeMove('O', move[0], move[1])
``````

``````newNode = Node(node.board)
newNode.makeMove('O', move[0], move[1])
``````

1. 思考策略看起來是偏向某一方連走，而非模擬交互下棋的規則。其實我的是有交互下棋的，因為我用if-else控制，當isMaxPlayer為True時改成False，isMaxPlayer為False時改成True
2. 你說最佳棋步改用計算「連線總分最高」，但由於井字盤面的對局樹夠小，而且這幾個測試盤面三步內可解，因此此例我想直接計算到底是沒問題的。