Commits

committed 16e4b78

Use minimax algo to calculate next best move.

• Participants
• Parent commits 738b259

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):`