井字棋介绍：https://en.wikipedia.org/wiki/Tic-tac-toe
井字棋简单，但是获胜策略却和直觉不同，四角比中间重要性要高，而且先手有很大的获胜概率获胜（先手胜：91， 后手胜：44，平局：3），所以当你陷入劣势时，怎么选择打平就是一个不那么简单的事情。不过无聊大抵孤单，没有人一起玩就只能和电脑PK，就写了个弱智AI，没事就偷着乐！
AI的获胜策略也很简单，先遍历检测棋盘副本的空格子看下一步能否获胜，如果有机会获胜，返回格子的下标，然后再棋盘上移动，其次，检测对手能否下一步获胜，提前封堵，如果前面两步都没返回的话，就说明双方都没有一步必胜的招式，这时候就得依次抢占四个角落，中间和剩余的位置。
import random def draw_board(board):
"""board is a 3X3 list containing the moves either ' ' representing
no moves there or 'x' or 'o' representing actual moves"""
for i in range(7):
if i%2 == 0:
print '+'.join(['---']*3)
else:
col = []
for j in range(11):
if j%2 == 0:
col.append(' ')
elif j==3 or j==7:
col.append('|')
else:
col.append(board[i/2][j/4])
print ''.join(col) def who_goes_first():
if random.randint(0, 1):
return 'AI'
else:
return 'P' def play_again():
print "Once Again?(y for Yes, n for No)"
return raw_input().lower().startswith('y') def make_move(board, letter, move):
seq = move-1
board[2-seq/3][seq%3] = letter def is_winner(bo, le):
# Given a board and a player’s letter, this function returns True if that player has won.
# We use bo instead of board and le instead of letter so we don’t have to type as much.
return ((bo[0][0] == le and bo[0][1] == le and bo[0][2] == le) or # across the top
(bo[1][0] == le and bo[1][1] == le and bo[1][2] == le) or # across the middle
(bo[2][0] == le and bo[2][1] == le and bo[2][2] == le) or # across the bottom
(bo[0][0] == le and bo[1][0] == le and bo[2][0] == le) or # down the left side
(bo[0][1] == le and bo[1][1] == le and bo[2][1] == le) or # down the middle
(bo[0][2] == le and bo[1][2] == le and bo[2][2] == le) or # down the right side
(bo[0][0] == le and bo[1][1] == le and bo[2][2] == le) or # diagonal
(bo[0][2] == le and bo[1][1] == le and bo[2][0] == le)) # diagonal def get_board_copy(board):
dup = [[' ']*3 for i in range(3)]
for i in range(3):
for j in range(3):
dup[i][j] = board[i][j]
return dup def is_move_avail(board, move):
seq = move-1
return board[2-seq/3][seq%3] == ' ' def get_P_moves(board):
move = ''
while move not in [1, 2, 3, 4, 5, 6, 7, 8, 9] or not is_move_avail(board, move):
print "Please input your next move('1-9')"
move = input()
return move def is_board_full(board):
for i in range(3):
for j in range(3):
if board[i][j] == ' ':
return False
return True def choose_randomly(board, avail):
possible_moves = []
for i in avail:
if is_move_avail(board, i):
possible_moves.append(i)
if len(possible_moves) != 0:
return random.choice(possible_moves)
else:
return None def get_AI_moves(board, AI, P):
#check if AI can win in the next move
for i in range(1, 10):
copy = get_board_copy(board)
if is_move_avail(board, i):
make_move(copy, AI, i)
if is_winner(copy, AI):
return i #else check if P can win in the next move and block the first found move
for i in range(1, 10):
copy = get_board_copy(board)
if is_move_avail(board, i):
make_move(copy, P, i)
if is_winner(copy, P):
return i #The key to win is to occupy the corners, so move there if available
move = choose_randomly(board, [1, 3, 7, 9])
print move
if move != None:
return move #of second priority is the center element
if is_move_avail(board, 5):
return 5 #Then the rest
return choose_randomly(board, [2, 4, 6, 8]) if __name__ == '__main__': while True:
Board = [[' ']*3 for i in range(3)]
P, AI = 'x', 'o'
turn = who_goes_first()
print "{0} will go first".format(turn)
GameOn = True while GameOn:
if turn == 'P':
move = get_P_moves(Board)
make_move(Board, P, move)
draw_board(Board) if is_winner(Board, P):
draw_board(Board)
print "GameOver You've Won!"
GameOn = False
else:
if is_board_full(Board):
draw_board(Board)
print "Tie"
break
else:
turn = 'AI' else:
move = get_AI_moves(Board, AI, P)
make_move(Board, AI, move)
draw_board(Board) if is_winner(Board, AI):
draw_board(Board)
print "GameOver AI has Won!"
GameOn = False
else:
if is_board_full(Board):
draw_board(Board)
print "Tie"
break
else:
turn = 'P' if not play_again():
break ##---+---+---
## x | o | x
##---+---+---
## o | x | o
##---+---+---
## x | o |
##---+---+---
注：
- python 2.7中input和raw_input的区别，python3中合并了
- 数据结构很简单，3X3的list of lists来表示棋盘。井字棋位置和小键盘一致。
- 参考文献: http://www.guokr.com/article/4754/