Anonymous avatar Anonymous committed 16e4b78

Use minimax algo to calculate next best move.

Comments (0)

Files changed (1)

tic-tac-toe/server/tttserv.py

                 return (r,c)
     return None
 
+def other_player(player):
+    if player == 1 or player == -1:
+        return -1*player
+    else: raise Exception("other_player: Unknown Player")
+
+def heuristic(board, player):
+    player_wins = 0
+    other_wins = 0
+    if winning_move(board, player):
+        return 10*-player
+    elif winning_move(board, other_player(player)):
+        return -10*-player
+    for line in rows() + columns() + diagnols():
+       squares = [board[r][c] for r,c in line]
+       if not squares.count(other_player(player)):
+           player_wins += 1
+       if not squares.count(player):
+           other_wins += 1
+    return player_wins - other_wins
+
+def children(board, player):
+    result = []
+    for i in range(len(board)):
+        for j in range(len(board[0])):
+            if board[i][j] == 0:
+                import copy
+                new_board = copy.deepcopy(board)
+                new_board[i][j] = player
+                result.append(new_board)
+    return result
+
+def minimax(board, depth, player):
+    if depth <= 0:
+        return (heuristic(board, player), board)
+    alpha = float('-inf')
+    best_child = None
+    for child in children(board, player):
+        child_alpha, child_board = minimax(child, depth-1, other_player(player))
+        child_alpha = -child_alpha
+        if child_alpha >= alpha:
+            best_child = child
+            alpha = child_alpha
+    return (alpha, child)
+
 def move(board):
     #can win?
     if winning_move(board, -1):
         r,c = winning_move(board, 1)
         board[r][c] = -1
         return board
+    alpha, board = minimax(board, 2, -1)
     return board
 
 class MainHandler(tornado.web.RequestHandler):
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.