深度优先Tic Tac Toe

1. #[allow(unused_imports)]
2. use std::io;

4. //Interactive Tic-Tac-Toe play needs the "rand = "0.8.3" crate.
5. //#[cfg(not(test))]
6. //extern crate rand;
7. //#[cfg(not(test))]
8. //use rand::Rng;

10. #[derive(Copy, Clone, PartialEq, Debug)]
11. struct Position {
12. x: u8,
13. y: u8,
14. }

16. #[derive(Copy, Clone, PartialEq, Debug)]
17. pub enum Players {
18. Blank,
19. PlayerX,
20. PlayerO,
21. }

23. #[derive(Copy, Clone, PartialEq, Debug)]
24. struct SinglePlayAction {
25. position: Position,
26. side: Players,
27. }

29. #[derive(Clone, PartialEq, Debug)]
30. pub struct PlayActions {
31. positions: Vec<Position>,
32. side: Players,
33. }

35. #[allow(dead_code)]
36. #[cfg(not(test))]
37. fn main() {
38. let mut board = vec![vec![Players::Blank; 3]; 3];

40. while !available_positions(&board).is_empty()
41. && !win_check(Players::PlayerX, &board)
42. && !win_check(Players::PlayerO, &board)
43. {
44. display_board(&board);
45. println!("Type in coordinate for X mark to be played. ie. a1 etc.");
46. let mut input = String::new();
47. io::stdin()
48. .read_line(&mut input)
49. .expect("Failed to read line");

51. let mut move_position: Option<Position> = None;
52. input.make_ascii_lowercase();
53. let bytes = input.trim().trim_start().as_bytes();
54. if bytes.len() as u32 == 2
55. && (bytes[0] as char).is_alphabetic()
56. && (bytes[1] as char).is_numeric()
57. {
58. let column: u8 = bytes[0] - b'a';
59. let row: u8 = bytes[1] - b'1';

61. if column <= 2 && row <= 2 {
62. move_position = Some(Position { x: column, y: row });
63. }
64. }

66. //Take the validated user input coordinate and use it.
67. if let Some(move_pos) = move_position {
68. let open_positions = available_positions(&board);

70. let mut search = open_positions.iter();
71. let result = search.find(|&&x| x == move_pos);
72. if result.is_none() {
73. println!("Not a valid empty coordinate.");
74. continue;
75. } else {
76. board[move_pos.y as usize][move_pos.x as usize] = Players::PlayerX;

78. if win_check(Players::PlayerX, &board) {
79. display_board(&board);
80. println!("Player X Wins!");
81. return;
82. }
83. }

85. //Find the best game plays from the current board state
86. let recusion_result = minimax(Players::PlayerO, &board);
87. match recusion_result {
88. Some(x) => {
89. //Interactive Tic-Tac-Toe play needs the "rand = "0.8.3" crate.
90. //#[cfg(not(test))]
91. //let random_selection = rand::thread_rng().gen_range(0..x.positions.len());
92. let random_selection = 0;

94. let response_pos = x.positions[random_selection];
95. board[response_pos.y as usize][response_pos.x as usize] = Players::PlayerO;
96. if win_check(Players::PlayerO, &board) {
97. display_board(&board);
98. println!("Player O Wins!");
99. return;
100. }
101. }

103. None => {
104. display_board(&board);
105. println!("Draw game.");
106. return;
107. }
108. }
109. }
110. }
111. }

113. #[allow(dead_code)]
114. fn display_board(board: &[Vec<Players>]) {
115. println!();
116. for (y, board_row) in board.iter().enumerate() {
117. print!("{} ", (y + 1));
118. for board_cell in board_row {
119. match board_cell {
120. Players::PlayerX => print!("X "),
121. Players::PlayerO => print!("O "),
122. Players::Blank => print!("_ "),
123. }
124. }
125. println!();
126. }
127. println!("  a b c");
128. }

130. fn available_positions(board: &[Vec<Players>]) -> Vec<Position> {
131. let mut available: Vec<Position> = Vec::new();
132. for (y, board_row) in board.iter().enumerate() {
133. for (x, board_cell) in board_row.iter().enumerate() {
134. if *board_cell == Players::Blank {
135. available.push(Position {
136. x: x as u8,
137. y: y as u8,
138. });
139. }
140. }
141. }
142. available
143. }

145. fn win_check(player: Players, board: &[Vec<Players>]) -> bool {
146. if player == Players::Blank {
147. return false;
148. }

150. //Check for a win on the diagonals.
151. if (board[0][0] == board[1][1]) && (board[1][1] == board[2][2]) && (board[2][2] == player)
152. || (board[2][0] == board[1][1]) && (board[1][1] == board[0][2]) && (board[0][2] == player)
153. {
154. return true;
155. }

157. for i in 0..3 {
158. //Check for a win on the horizontals.
159. if (board[i][0] == board[i][1]) && (board[i][1] == board[i][2]) && (board[i][2] == player) {
160. return true;
161. }

163. //Check for a win on the verticals.
164. if (board[0][i] == board[1][i]) && (board[1][i] == board[2][i]) && (board[2][i] == player) {
165. return true;
166. }
167. }

169. false
170. }

172. //Minimize the actions of the opponent while maximizing the game state of the current player.
173. pub fn minimax(side: Players, board: &[Vec<Players>]) -> Option<PlayActions> {
174. //Check that board is in a valid state.
175. if win_check(Players::PlayerX, board) || win_check(Players::PlayerO, board) {
176. return None;
177. }

179. let opposite = match side {
180. Players::PlayerX => Players::PlayerO,
181. Players::PlayerO => Players::PlayerX,
182. Players::Blank => panic!("Minimax can't operate when a player isn't specified."),
183. };

185. let positions = available_positions(board);
186. if positions.is_empty() {
187. return None;
188. }

190. //Play position
191. let mut best_move: Option<PlayActions> = None;

193. for pos in positions {
194. let mut board_next = board.to_owned();
195. board_next[pos.y as usize][pos.x as usize] = side;

197. //Check for a win condition before recursion to determine if this node is terminal.
198. if win_check(Players::PlayerX, &board_next) {
199. append_playaction(
200. side,
201. &mut best_move,
202. SinglePlayAction {
203. position: pos,
204. side: Players::PlayerX,
205. },
206. );
207. continue;
208. }

210. if win_check(Players::PlayerO, &board_next) {
211. append_playaction(
212. side,
213. &mut best_move,
214. SinglePlayAction {
215. position: pos,
216. side: Players::PlayerO,
217. },
218. );
219. continue;
220. }

222. let result = minimax(opposite, &board_next);
223. let current_score = match result {
224. Some(x) => x.side,
225. _ => Players::Blank,
226. };

228. append_playaction(
229. side,
230. &mut best_move,
231. SinglePlayAction {
232. position: pos,
233. side: current_score,
234. },
235. )
236. }
237. best_move
238. }

240. //Promote only better or collate equally scored game plays
241. fn append_playaction(
242. current_side: Players,
243. opt_play_actions: &mut Option<PlayActions>,
244. appendee: SinglePlayAction,
245. ) {
246. if opt_play_actions.is_none() {
247. *opt_play_actions = Some(PlayActions {
248. positions: vec![appendee.position],
249. side: appendee.side,
250. });
251. return;
252. }

254. let mut play_actions = opt_play_actions.as_mut().unwrap();

256. //New game action is scored from the current side and the current saved best score against the new game action.
257. match (current_side, play_actions.side, appendee.side) {
258. (Players::Blank, _, _) => panic!("Unreachable state."),

260. //Winning scores
261. (Players::PlayerX, Players::PlayerX, Players::PlayerX) => {
262. play_actions.positions.push(appendee.position);
263. }
264. (Players::PlayerX, Players::PlayerX, _) => {}
265. (Players::PlayerO, Players::PlayerO, Players::PlayerO) => {
266. play_actions.positions.push(appendee.position);
267. }
268. (Players::PlayerO, Players::PlayerO, _) => {}

270. //Non-winning to Winning scores
271. (Players::PlayerX, _, Players::PlayerX) => {
272. play_actions.side = Players::PlayerX;
273. play_actions.positions.clear();
274. play_actions.positions.push(appendee.position);
275. }
276. (Players::PlayerO, _, Players::PlayerO) => {
277. play_actions.side = Players::PlayerO;
278. play_actions.positions.clear();
279. play_actions.positions.push(appendee.position);
280. }

282. //Losing to Neutral scores
283. (Players::PlayerX, Players::PlayerO, Players::Blank) => {
284. play_actions.side = Players::Blank;
285. play_actions.positions.clear();
286. play_actions.positions.push(appendee.position);
287. }

289. (Players::PlayerO, Players::PlayerX, Players::Blank) => {
290. play_actions.side = Players::Blank;
291. play_actions.positions.clear();
292. play_actions.positions.push(appendee.position);
293. }

295. //Ignoring lower scored plays
296. (Players::PlayerX, Players::Blank, Players::PlayerO) => {}
297. (Players::PlayerO, Players::Blank, Players::PlayerX) => {}

299. //No change hence append only
300. (_, _, _) => {
301. assert!(play_actions.side == appendee.side);
302. play_actions.positions.push(appendee.position);
303. }
304. }
305. }

307. #[cfg(test)]
308. mod test {
309. use super::*;

311. #[test]
312. fn win_state_check() {
313. let mut board = vec![vec![Players::Blank; 3]; 3];
314. board[0][0] = Players::PlayerX;
315. board[0][1] = Players::PlayerX;
316. board[0][2] = Players::PlayerX;
317. let responses = minimax(Players::PlayerO, &board);
318. assert_eq!(responses, None);
319. }

321. #[test]
322. fn win_state_check2() {
323. let mut board = vec![vec![Players::Blank; 3]; 3];
324. board[0][0] = Players::PlayerX;
325. board[0][1] = Players::PlayerO;
326. board[1][0] = Players::PlayerX;
327. board[1][1] = Players::PlayerO;
328. board[2][1] = Players::PlayerO;
329. let responses = minimax(Players::PlayerO, &board);
330. assert_eq!(responses, None);
331. }

333. #[test]
334. fn block_win_move() {
335. let mut board = vec![vec![Players::Blank; 3]; 3];
336. board[0][0] = Players::PlayerX;
337. board[0][1] = Players::PlayerX;
338. board[1][2] = Players::PlayerO;
339. board[2][2] = Players::PlayerO;
340. let responses = minimax(Players::PlayerX, &board);
341. assert_eq!(
342. responses,
343. Some(PlayActions {
344. positions: vec![Position { x: 2, y: 0 }],
345. side: Players::PlayerX
346. })
347. );
348. }

350. #[test]
351. fn block_move() {
352. let mut board = vec![vec![Players::Blank; 3]; 3];
353. board[0][1] = Players::PlayerX;
354. board[0][2] = Players::PlayerO;
355. board[2][0] = Players::PlayerO;
356. let responses = minimax(Players::PlayerX, &board);
357. assert_eq!(
358. responses,
359. Some(PlayActions {
360. positions: vec![Position { x: 1, y: 1 }],
361. side: Players::Blank
362. })
363. );
364. }

366. #[test]
367. fn expected_loss() {
368. let mut board = vec![vec![Players::Blank; 3]; 3];
369. board[0][0] = Players::PlayerX;
370. board[0][2] = Players::PlayerO;
371. board[1][0] = Players::PlayerX;
372. board[2][0] = Players::PlayerO;
373. board[2][2] = Players::PlayerO;
374. let responses = minimax(Players::PlayerX, &board);
375. assert_eq!(
376. responses,
377. Some(PlayActions {
378. positions: vec![
379. Position { x: 1, y: 0 },
380. Position { x: 1, y: 1 },
381. Position { x: 2, y: 1 },
382. Position { x: 1, y: 2 }
383. ],
384. side: Players::PlayerO
385. })
386. );
387. }
388. }