井字棋

ZhKQYu

1. from copy import deepcopy
   
2. 
   
3. class Board:
   
4.     def __init__(self):
   
5.         self.state = [[0, 0, 0], [0, 0, 0], [0, 0, 0]]
   
6.         self.flag = 0
   
7. 
   
8.     def __str__(self):
   
9.         new_lst = deepcopy(self.state)
   
10.         for i in range(len(new_lst)):
    
11.             for j in range(len(new_lst[i])):
    
12.                 if new_lst[i][j] == 0:
    
13.                     new_lst[i][j] = "-"
    
14.                 elif new_lst[i][j] == 1:
    
15.                     new_lst[i][j] = "X"
    
16.                 else:
    
17.                     new_lst[i][j] = "O"
    
18.         string = "{:^5}|{:^5}|{:^5}\n{:_^5}|{:_^5}|{:_^5}\n{:^5}|{:^5}|{:^5}\n{:^5}|{:^5}|{:^5}\n{:_^5}|{:_^5}|{:_^5}\n{:^5}|{:^5}|{:^5}\n{:^5}|{:^5}|{:^5}\n{:^5}|{:^5}|{:^5}\n"
    
19.         return string.format(*new_lst[0], "_", "_", "_", " ", " ", " ", *new_lst[1], "_", "_", "_", " ", " ", " ", *new_lst[2], " ", " ", " ")
    
20. 
    
21.     def reset(self):
    
22.         self.state = [[0, 0, 0], [0, 0, 0], [0, 0, 0]]
    
23.         self.flag = 0  # 采用法一的时候必须将flag置为0
    
24. 
    
25.     @property
    
26.     def is_valid(self):
    
27.         count_X = 0
    
28.         count_O = 0
    
29.         if len(self.state) != 3:
    
30.             return False
    
31.         for line in self.state:
    
32.             if len(line) != 3:
    
33.                 return False
    
34.             if not(isinstance(line[0], int) and isinstance(line[1], int) and isinstance(line[2], int) and line[0] in [0, 1, 2] and line[1] in [0, 1, 2] and line[2] in [0, 1, 2]):
    
35.                 return False
    
36.             for each in line:
    
37.                 if each == 1:
    
38.                     count_X += 1
    
39.                 elif each == 2:
    
40.                     count_O += 1
    
41.         if abs(count_X - count_O) > 1:
    
42.             return False
    
43.         return True
    
44. 
    
45.     @property
    
46.     def round(self):
    
47.         count = 0
    
48.         for line in self.state:
    
49.             for each in line:
    
50.                 if each != 0:
    
51.                     count += 1
    
52. 
    
53.         return count
    
54. 
    
55.     def __getitem__(self, key):
    
56.         return self.state[key.row][key.col]
    
57. 
    
58.     def __setitem__(self, key, value):
    
59.         if self.state[key.row][key.col] != 0:
    
60.             raise ValueError
    
61.         # 交替添加就叫一致或者连续
    
62.         # 法一
    
63.         if value == 1 and self.flag != -1:
    
64.             self.state[key.row][key.col] = value
    
65.             self.flag = -1
    
66.         elif value == 2 and self.flag != 1:
    
67.             self.state[key.row][key.col] = value
    
68.             self.flag = 1
    
69.         else:
    
70.             raise ValueError
    
71.         # 法二
    
72.         # 如果在添加之后，棋盘不合法，则valueerror
    
73.          
    
74. 
    
75.     @property
    
76.     def winner(self):
    
77.         # 横竖
    
78.         for i in range(3):
    
79.             if self.state[i][0] == self.state[i][1] == self.state[i][2] and self.state[i][0] != 0:
    
80.                 return self.state[i][0]
    
81.             elif self.state[0][i] == self.state[1][i] == self.state[2][i] and self.state[0][i] != 0:
    
82.                 return self.state[0][i]
    
83.         # 对角线
    
84.         if self.state[0][0] == self.state[1][1] == self.state[2][2] and self.state[0][0] != 0:
    
85.             return self.state[0][0]
    
86.         # 副对角线
    
87.         elif self.state[0][2] == self.state[1][1] == self.state[2][0] and self.state[0][2] != 0:
    
88.             return self.state[0][2]
    
89.         return 0
    
90. 
    
91.     @property
    
92.     def is_finished(self):
    
93.         if self.winner == True or self.round == 9:
    
94.             return True
    
95.         
    
96.             
    
97. 
    
98. class Position:
    
99.     def __init__(self, row, col):
    
100.         if row in [0, 1, 2] and col in [0, 1, 2]:
     
101.             self.row = row
     
102.             self.col = col
     
103.         else:
     
104.             raise ValueError
     
105. 
     
106. import random
     
107. # 井字棋核心算法
     
108. class Agent:
     
109.     def make_move(self, board):
     
110.         iswin = self.get_win_or_lost(board, 1)
     
111.         # 如果自己能赢直接赢
     
112.         if iswin != None:
     
113.             return iswin
     
114.         islost = self.get_win_or_lost(board, 2)
     
115.         # 如果对方能赢则堵住
     
116.         if islost != None:
     
117.             return islost
     
118.         # 预判一下自己能否必胜
     
119.         will_win = self.I_will_win_or_lost(board, 1)
     
120.         if will_win != None:
     
121.             return will_win
     
122.         # 预判一下自己是否必输
     
123.         will_lost = self.I_will_win_or_lost(board, 2)
     
124.         if will_lost != None:
     
125.             return will_lost
     
126.         # 如果中间位置没有棋子则下在中间，因为放在中间赢得概率最大
     
127.         if board[Position(1, 1)] == 0:
     
128.             return Position(1, 1)
     
129.         if board.round == 1:
     
130.             # 当别人先手时，如果中间位置被占，那么就在(0, 0)下子
     
131.             if board[Position(1, 1)] != 0:
     
132.                 return Position(0, 0)
     
133.         # 其他情况随机放子，基本不影响赢的概率
     
134.         row = random.randint(0, 2)
     
135.         col = random.randint(0, 2)
     
136.         while board[Position(row, col)] != 0:
     
137.             row = random.randint(0, 2)
     
138.             col = random.randint(0, 2)
     
139.         return Position(row, col)
     
140. 
     
141.     # 去试一试自己要赢还是要输
     
142.     def get_win_or_lost(self, board, player):
     
143.         empty_position = []
     
144.         for i in range(3):
     
145.             for j in range(3):
     
146.                 if board[Position(i, j)] == 0:
     
147.                     empty_position.append(Position(i, j))
     
148.         for each in empty_position:
     
149.             board.state[each.row][each.col] = player
     
150.             if board.winner == player:
     
151.                 board.state[each.row][each.col] = 0
     
152.                 return each
     
153.             board.state[each.row][each.col] = 0
     
154. 
     
155.     def I_will_win_or_lost(self, board, player):
     
156.         empty_position = []
     
157.         for i in range(3):
     
158.             for j in range(3):
     
159.                 if board[Position(i, j)] == 0:
     
160.                     empty_position.append(Position(i, j))
     
161.         for each in empty_position:
     
162.             board.state[each.row][each.col] = player
     
163.             if self.get_win_lost_count(board, player) > 1:
     
164.                 board.state[each.row][each.col] = 0
     
165.                 return each
     
166.             board.state[each.row][each.col] = 0
     
167. 
     
168.     def get_win_lost_count(self, board, player):
     
169.         empty_position = []
     
170.         for i in range(3):
     
171.             for j in range(3):
     
172.                 if board[Position(i, j)] == 0:
     
173.                     empty_position.append(Position(i, j))
     
174.         count = 0
     
175.         for each in empty_position:
     
176.             board.state[each.row][each.col] = player
     
177.             if board.winner == player:
     
178.                 board.state[each.row][each.col] = 0
     
179.                 count += 1
     
180.             board.state[each.row][each.col] = 0
     
181.         return count
     
182. 
     
183. 
     
184. 
     
185. count_a = 0
     
186. count_b = 0
     
187. 
     
188. agent1 = Agent()
     
189. # agent2 = Agent()
     
190. 
     
191. # 完全随机下棋的玩家
     
192. class agent_random:
     
193.     def make_move(self, board):
     
194.         row = random.randint(0, 2)
     
195.         col = random.randint(0, 2)
     
196.         while board[Position(row, col)] != 0:
     
197.             row = random.randint(0, 2)
     
198.             col = random.randint(0, 2)
     
199.         return Position(row, col)
     
200. 
     
201. agent2 = agent_random()
     
202. 
     
203. board = Board()
     
204. # 先手一定不会输
     
205. # for i in range(5000):
     
206. #     while board.winner == 0:
     
207. #         board[agent1.make_move(board)] = 1
     
208. #         if board.winner != 0:
     
209. #             # print("agent1 win")
     
210. #             # print(board)
     
211. #             count_a += 1
     
212. #             break
     
213. #         if board.is_finished:
     
214. #             break
     
215. #         board[agent2.make_move(board)] = 2
     
216. #         if board.winner != 0:
     
217. #             print("agent2 win")
     
218. #             print(board)
     
219. #             count_b += 1
     
220. #             break
     
221. #         if board.is_finished:
     
222. #             break
     
223. #     board.reset()
     
224. #     board.flag = 0
     
225. #     # print("Finished %s times" % (i+1))
     
226. 
     
227. # 后手获胜概率很大
     
228. for j in range(5000):
     
229.     while board.winner == 0:
     
230.         board[agent2.make_move(board)] = 1
     
231.         if board.winner != 0:
     
232.             print("agent2 win")
     
233.             print(board)
     
234.             count_b += 1
     
235.             break
     
236.         if board.is_finished:
     
237.             break
     
238.         board[agent1.make_move(board)] = 2
     
239.         if board.winner != 0:
     
240.             # print("agent1 win")
     
241.             # print(board)
     
242.             count_a += 1
     
243.             break
     
244.         if board.is_finished:
     
245.             break
     
246.     board.reset()
     
247.     board.flag = 0
     
248. 
     
249. print(count_a, count_b)

复制代码

代码太臃肿了
时间复杂度还是比较高的
不过好在还是可以跑起来
测试了5000次
先手的话应该是必胜
后手获胜概率也很大
记录一下

繁宇宙

好厉害的样子，good

ZhKQYu

人机对战，人类输入想要下子的位置，比如输入0 0，代表在左上角下子，其他情况类似

1. board = Board()
   
2. 
   
3. agent = Agent()
   
4. # 机器先手
   
5. # while True:
   
6. #     board[agent.make_move(board)] = 1
   
7. #     print(board)
   
8. #     if board.winner != 0:
   
9. #         break
   
10. #     if board.is_finished:
    
11. #         break
    
12. #     while True:
    
13. #         try:
    
14. #             board[Position(*[int(each) for each in input("Please input the position : ").split()])] = 2
    
15. #             break
    
16. #         except:
    
17. #             pass
    
18. #     print(board)
    
19. #     if board.winner != 0:
    
20. #         break
    
21. #     if board.is_finished:
    
22. #         break
    
23. # board.reset()
    
24. # board.flag = 0
    
25. 
    
26. # 玩家先手，有必胜的策略
    
27. # 玩家先放(0, 0)，机器会放在中间,玩家放在(2, 2),机器会放在(0, 2),玩家放在(2, 0)，人类获胜
    
28. while True:
    
29.     while True:
    
30.         try:
    
31.             board[Position(*[int(each) for each in input("Please input the position : ").split()])] = 2
    
32.             break
    
33.         except:
    
34.             pass
    
35.    
    
36.     print(board)
    
37.     if board.winner != 0:
    
38.         break
    
39.     if board.is_finished:
    
40.         break
    
41.     board[agent.make_move(board)] = 1
    
42.     print(board)
    
43.     if board.winner != 0:
    
44.         break
    
45.     if board.is_finished:
    
46.         break
    
47. board.reset()
    
48. board.flag = 0

复制代码