Building a Tic Tac Toe AI in Python

Transcript

1. BUILDING A TIC TAC TOE BOT IN PYTHON Kiran Gangadharan
2. WHAT THIS TALK IS NOT ABOUT
4. BUILDING A SIMPLE, EFFECTIVE AI FOR TIC TAC TOE (that almost always beats you)
5. MINIMAX
6. MINIMAX ➤ A decision rule used in game theory to minimise the worst case scenario (loss). ➤ It’s about minimising one’s maximum loss or maximising one’s minimum gain (hence the term Minimax) ➤ Originally designed for two player games where each player would alternate turns.
7. WHY USE MINIMAX?
8. https://xkcd.com/832/
9. HOW DOES IT WORK?
10. Image from http://neverstopbuilding.com/minimax
11. ALGORITHM
12. ➤ If leaf node, return score from AI’s perspective ➤ Otherwise, get all possible moves in board ➤ For each move ➤ Add minimax of that move to a scores list ➤ If it’s the AI’s turn, return max(scores) ➤ If it’s the player’s turn, return min(scores)
13. LET’S LOOK AT SOME CODE!
14. MINIMAX def minimax(self, board, player): empty_cells = self.empty_cells(board) score = self.get_score(board) if score == 0: # Check for draw if len(empty_cells) == 0: return score else: return score scores = [] for cell in empty_cells: b = list(board) b[cell] = player scores.append(self.minimax(b, self.opponent(player))) if player == self.player: return max(scores) else: return min(scores)
15. HEURISTIC FUNCTION def get_score(self, board): opp = self.opponent(self.player) win = self.has_won(board, self.player) has_two_in_line = self.has_two_in_line(board, self.player) opp_win = self.has_won(board, opp) opp_has_two_in_line = self.has_two_in_line(board, opp) score = 0 if win: score += 100 if has_two_in_line: score += 10 if opp_win: score -= 100 if opp_has_two_in_line: score -= 10 return score
16. DEMO
17. NEXT STEPS
18. ALPHA-BETA PRUNING
19. http://yuliana.lecturer.pens.ac.id/Kecerdasan%20Buatan/ppt/Game%20Playing/contoh%20prunning/
20. RESOURCES https://youtu.be/STjW3eH0Cik
21. https://github.com/kirang89/tictac
22. THANKS!
23. kirang89 @kirang89 http://kirang.in