|
目录
1. 前言
2. 处理流程
3. 代码
4. 代码说明
4.1 棋盘显示
4.2 初始化
4.3 人类棋手的下一步
4.4 AI棋手的下一步
4.5 终局及胜负判断
5. 棋局示例
1. 前言
前面几篇博客（以循序渐进的方式）实现了Tic-Tac-Toe游戏的棋局搜索、遍历以及所有可能棋局数和盘面状态数的计算，参见：
Tic-Tac-Toe可能棋局搜索的实现（python）
Tic-Tac-Toe可能棋局遍历的实现（python）
Tic-Tac-Toe有多少种不同棋局和盘面状态（python实现）
本文先实现一个简单的Tic-Tac-Toe人机对弈程序，为下一步实现基于minimax算法的Tic-Tac-Toe人机对弈程序做一个准备。
2. 处理流程
3. 代码
# Tic Tac Toe
# Created by chenxy in 2017-06-23, with only drawBoard() copied from
# 2023-01-04 refined
import random
import sys
def drawBoard(board, initFlag = 0):
# This function prints out the board that it was passed.
brd_copy = board.copy()
if initFlag:
brd_copy = ['0','1','2','3','4','5','6','7','8','9']
# "board" is a list of 10 strings representing the board (ignore index 0)
print('=============')
# print(' | |')
print(' ' + brd_copy[7] + ' | ' + brd_copy[8] + ' | ' + brd_copy[9])
# print(' | |')
print('-----------')
# print(' | |')
print(' ' + brd_copy[4] + ' | ' + brd_copy[5] + ' | ' + brd_copy[6])
# print(' | |')
print('-----------')
# print(' | |')
print(' ' + brd_copy[1] + ' | ' + brd_copy[2] + ' | ' + brd_copy[3])
# print(' | |')
print('=============')
print()
def askGameStart():
# Ask human start a game or not;
print('Do you want to start a game? Y or y to start; Others to exit');
inputWord = input().lower();
if inputWord.startswith('y'):
startNewGame = True;
else:
startNewGame = False;
return(startNewGame);
# Decide whether the number human input for the next move has been already used or not.
# It can be decided by whether the corrsponding element is empty or not.
def isValidInput(board, humanNextMove):
isValid = 1;
if humanNextMove == 0:
print('Please input 1~9, 0 is not an valid input for the next move!');
isValid = 0;
elif board[humanNextMove] != ' ':
print('The space has already been used! Please select an empty space for the next move');
isValid = 0;
return(isValid);
# Ask the human player for the next move.
def askNextMove(board):
while True:
print('Please input the next move!');
c = input()
if not c.isdigit():
print('Invalid input! Please input [1-9]!');
continue
nextMove = int(c);
if board[nextMove] == ' ':
break;
else:
continue;
isValid = isValidInput(board, nextMove)
return isValid,nextMove
def gameRsltDisplay(winner):
if 'A' == winner:
print('AI win!');
elif 'H' == winner:
print('Human win!');
else:
print('A tie game!');
# Decide AI's next move.
# Decide whether the three input are all the same
def isTripleGoalReachedNext(board,idx1, idx2, idx3, role):
in1 = board[idx1];
in2 = board[idx2];
in3 = board[idx3];
if in1 == ' ' and in2 == in3 and in2 == role:
return idx1;
elif in2 == ' ' and in1 == in3 and in3 == role:
return idx2;
elif in3 == ' ' and in1 == in2 and in1 == role:
return idx3;
else:
return 0; # Invalid space index.
def isGoalReachedNext(board, role):
nextMove = 0;
nextMove = isTripleGoalReachedNext(board, 1, 4, 7, role);
if nextMove > 0:
return True, nextMove
nextMove = isTripleGoalReachedNext(board, 1, 2, 3, role);
if nextMove > 0:
return True, nextMove
nextMove = isTripleGoalReachedNext(board, 1, 5, 9, role);
if nextMove > 0:
return True, nextMove
nextMove = isTripleGoalReachedNext(board, 2, 5, 8, role);
if nextMove > 0:
return True, nextMove
nextMove = isTripleGoalReachedNext(board, 3, 5, 7, role);
if nextMove > 0:
return True, nextMove
nextMove = isTripleGoalReachedNext(board, 3, 6, 9, role);
if nextMove > 0:
return True, nextMove
nextMove = isTripleGoalReachedNext(board, 4, 5, 6, role);
if nextMove > 0:
return True, nextMove
nextMove = isTripleGoalReachedNext(board, 7, 8, 9, role);
if nextMove > 0:
return True, nextMove
return False, nextMove;
def aiNextMove(board, gameRole):
# Temporarily, select the first empty space.
# 1. First, check whether AI will reach the goal in the next step.
# gameRole[0] represents AI's role.
goalReachedNext, nextMove = isGoalReachedNext(board, gameRole[0]);
if goalReachedNext == True:
return nextMove;
# 2. Secondly, check whether Human will reach the goal in the next step.
# gameRole[1] represents Human's role.
# Of course, AI should take the next move to blocking Human player to reach the goal.
goalReachedNext, nextMove = isGoalReachedNext(board, gameRole[1]);
if goalReachedNext == True:
return nextMove;
# Randomly selected from the left spaces for the next move.
spaces = []
for k in range(1,10):
if board[k] == ' ':
spaces.append(k)
else:
continue;
nextMove = random.choice(spaces)
return(nextMove);
# Decide whether the three input are all the same
def isTripleSame(in1, in2, in3):
if in1 == ' ' or in2 == ' ' or in3 == ' ':
return False
elif in1 == in2 and in1 == in3:
return True
else:
return False
def gameJudge(board):
if isTripleSame(board[1],board[4],board[7]):
gameOver = True; winner = board[1];
elif isTripleSame(board[1],board[2],board[3]):
gameOver = True; winner = board[1];
elif isTripleSame(board[1],board[5],board[9]):
gameOver = True; winner = board[1];
elif isTripleSame(board[2],board[5],board[8]):
gameOver = True; winner = board[2];
elif isTripleSame(board[3],board[5],board[7]):
gameOver = True; winner = board[3];
elif isTripleSame(board[3],board[6],board[9]):
gameOver = True; winner = board[3];
elif isTripleSame(board[4],board[5],board[6]):
gameOver = True; winner = board[4];
elif isTripleSame(board[7],board[8],board[9]):
gameOver = True; winner = board[7];
elif ' ' in board[1:9]:
gameOver = False; winner = ' ';
else:
gameOver = True; winner = ' ';
return gameOver, winner
whoseTurn = 0; # 0 : AI's turn; 1: Human's turn.
gameRole = ['A','H']; # [0]: AI's role; [1]: Human's role;
board = [' ']*10; # Note: '*' for string means concatenation.
drawBoard(board,1); # Draw the initial board with numbering
if not askGameStart():
print('Bye-Bye! See you next time!');
sys.exit();
while True:
# Initialization.
gameOver = 0;
board = [' ',' ',' ',' ',' ',' ',' ',' ',' ',' '];
# Decide who, either human or AI, play first.
# 0: AI; 1: human.
role = random.randint(0,1);
if role == 0:
whoseTurn = 0;
elif role == 1:
whoseTurn = 1;
while(not gameOver):
if whoseTurn == 0:
print('AI\'s turn')
nextMove = aiNextMove(board,gameRole);
board[nextMove] = gameRole[0];
whoseTurn = 1;
else:
print('Human\'s turn')
isValid = 0;
while(not isValid):
isValid, nextMove = askNextMove(board);
board[nextMove] = gameRole[1];
whoseTurn = 0;
drawBoard(board);
gameOver,winner = gameJudge(board);
gameRsltDisplay(winner);
#startNewGame = askGameStart();
if not askGameStart():
print('Bye-Bye! See you next time!');
sys.exit();
4. 代码说明
4.1 棋盘显示
为了方便操作，棋盘的格点位置与（人类棋手下棋时输入的）数字的对应关系设计成和计算机键盘右边的小键盘相同，如下图所示。这样的话，比如说棋手输入7的话就表示在棋盘左上角落子，输入3的话表示在棋盘右下角落子，余者类推。
代码中用一个包含10个元素的（字符：“H”，“A”）数组表示棋盘board，其中board[0]不使用。人类棋手用字母“H”（Human）表示；AI棋手用字母“A”（Artificial Intelligence）表示。比如说，人类棋手输入7的话，表示在左上角落子，则将board[7]赋值为“H”；AI棋手输入1的话，表示在左下角落子，则将board[1]赋值为“A”。。。
详细参见drawBoard(board, initFlag = 0)函数的实现。
4.2 初始化
初始棋盘显示。游戏开始时的初始棋盘显示中，显示的是上图所示棋盘各个位置对应的数字，方便玩家参考。在游戏过程中，各棋盘格子中显示的是“H”或者“A”或者空格（还没有落子的格子）。
猜先。调用askGameStart()开始游戏并进行猜先。
4.3 人类棋手的下一步
askNextMove ()：询问人类棋手的下一步。应该输入1~9中的一个数字
isValidInput()：用于判断棋手输入的合法性。如果输入0或者非数字的话，程序会要求棋手再次输入。
4.4 AI棋手的下一步
本程序中目前只实现了一个傻傻的AI，只比完全随机落子聪明一点点。
AI决定落子时，首先检查是否有能够终结棋局的下一手，如果有的话就选择那一手（如果有多个下一手可以终结棋局的话则选择找到的第一手）；如果没有能够终结棋局的下一手时就从余下的空格中随机选择一手。很显然，将来优化这个AI时就应该从此处着手。
aiNextMove(board, gameRole)：AI agent。决定AI的下一手。
isGoalReachedNext(board, role)：AI决定下一手时首先遍历空的棋格看是否存在能够终结棋局的下一手。
isTripleGoalReachedNext(board,idx1, idx2, idx3, role)：用于确定指定的三个棋格（在再下一手的条件下）是否满足终结棋局的条件。
4.5 终局及胜负判断
gameJudge()：
终局及胜负判断。如果已经出现排成一条直线的三个棋格相同的终结棋局的局面，则判定棋局结束且判定胜者为谁；如果棋盘已满但是没有出现“排成一条直线的三个棋格相同”的情况，则判定平局；否则，棋局仍将继续。
isTripleSame()：
用于确定指定的三个棋格是否满足终结棋局的条件。注意它与isTripleGoalReachedNext()的区别。
5. 棋局示例
以下为一局棋的运行过程示例。
(base) E:\TicTacToe>python tictactoe.py ============= 7 | 8 | 9 ----------- 4 | 5 | 6 ----------- 1 | 2 | 3 =============
Do you want to start a game? Y or y to start; Others to exit y Human's turn Please input the next move! 7 ============= H | | ----------- | | ----------- | | =============
AI's turn ============= H | | ----------- | | ----------- A | | =============
Human's turn Please input the next move! 3 ============= H | | ----------- | | ----------- A | | H =============
AI's turn ============= H | | ----------- | A | ----------- A | | H =============
Human's turn Please input the next move! 9 ============= H | | H ----------- | A | ----------- A | | H =============
AI's turn ============= H | | H ----------- | A | A ----------- A | | H =============
Human's turn Please input the next move! 8 ============= H | H | H ----------- | A | A ----------- A | | H =============
Human win! Do you want to start a game? Y or y to start; Others to exit
Next Step：
实现基于完全minimax的unbeatable TicTacToe AI
实现TicTacToe GUI
。。。
后记（2023-01-05）：调研学习alphaGo论文中，想先写一个Tic-Tac-Toe的游戏程序，以此为基础学习minimax，alphabeta，MCTS等算法概念。然后翻了翻计算机中的文件发现自己居然在2017年就写过一个，完全没有印象了^-^。整理了一下先发出来以免自己再次忘记。
基于minimax算法的tic-tac-toe AI agent实现参见：
https://chenxiaoyuan.blog.csdn.net/article/details/128591542 https://chenxiaoyuan.blog.csdn.net/article/details/128591542
参考文献：
AL SWEIGART, Invent Your Own Computer Games with Python(4th)
|