Commits

Geoff Hill committed 14be2ea

finished tic-tac-toe assignment

Comments (0)

Files changed (5)

src/tic-tac-toe/game.py

 
 
 class MinimaxPlayer(Player):
-    NEG_INF = -10
     INF = 10
     def utility(self, state, mark):
         if not state.complete():
         return self.minimax(state)
     def minimax(self, state):
         mark = state.currentMark
-        a, score = self.maxValue(state, mark)
+        a, score, alpha, beta = self.maxValue(state, -self.INF, self.INF, mark)
         return a
-    def maxValue(self, state, mark):
+    def maxValue(self, state, alpha, beta, mark):
         if state.complete():
-            return (None, self.utility(state, mark))
+            return (None, self.utility(state, mark), alpha, beta)
         actions = self.actions(state)
         best_action = None
-        best_action_score = self.NEG_INF
+        best_score = -self.INF
         for action in actions:
             next = self.nextState(state, action)
-            a, score = self.minValue(next, mark)
-            if score > best_action_score:
+            a, score, y, z = self.minValue(next, alpha, beta, mark)
+            if score > best_score:
                 best_action = action
-                best_action_score = score
-        return (best_action, best_action_score)
-    def minValue(self, state, mark):
+                best_score = score
+            if score >= beta:
+                return (action, score, alpha, beta)
+            alpha = max(alpha, score)
+        return (best_action, best_score, alpha, beta)
+    def minValue(self, state, alpha, beta, mark):
         if state.complete():
-            return (None, self.utility(state, mark))
+            return (None, self.utility(state, mark), alpha, beta)
         actions = self.actions(state)
         best_action = None
-        best_action_score = self.INF
+        best_score = self.INF
         for action in actions:
             next = self.nextState(state, action)
-            a, score = self.maxValue(next, mark)
-            if score < best_action_score:
+            a, score, y, z = self.maxValue(next, alpha, beta, mark)
+            if score < best_score:
                 best_action = action
-                best_action_score = score
-        return (best_action, best_action_score)
+                best_score = score
+            if score <= alpha:
+                return (action, score, alpha, beta)
+            beta = min(beta, score)
+        return (best_action, best_score, alpha, beta)
     def __repr__(self):
         return str(self)
     def __str__(self):
             return None
 
 
-def main():
+def playFirst():
     player_a = HumanPlayer()
     player_b = MinimaxPlayer()
     b = Board(player_a, player_b)
     else:
         print("Tie.")
 
-
-if __name__ == "__main__":
-    main()
-
-
-
-
-
-
-
-
+def playSecond():
+    player_a = MinimaxPlayer()
+    player_b = HumanPlayer()
+    b = Board(player_a, player_b)
+    winner = b.play()
+    if winner == player_b:
+        print("You win!")
+    elif winner == player_a:
+        print("You lose! Good day, sir.")
+    else:
+        print("Tie.")
 
 
+if __name__ == "__main__":
+    playFirst()
 
 
 

src/tic-tac-toe/output-a.txt

+Current player: HumanPlayer()
+Waiting player: MinimaxPlayer()
+Current board state:
+N|N|N
+N|N|N
+N|N|N
+
+Your move, pick a row (0-2):
+2
+Now pick a col (0-2):
+2
+Current player: MinimaxPlayer()
+Waiting player: HumanPlayer()
+Current board state:
+N|N|N
+N|N|N
+N|N|X
+
+Current player: HumanPlayer()
+Waiting player: MinimaxPlayer()
+Current board state:
+N|N|N
+N|O|N
+N|N|X
+
+Your move, pick a row (0-2):
+2
+Now pick a col (0-2):
+0
+Current player: MinimaxPlayer()
+Waiting player: HumanPlayer()
+Current board state:
+N|N|N
+N|O|N
+X|N|X
+
+Current player: HumanPlayer()
+Waiting player: MinimaxPlayer()
+Current board state:
+N|N|N
+N|O|N
+X|O|X
+
+Your move, pick a row (0-2):
+0
+Now pick a col (0-2):
+1
+Current player: MinimaxPlayer()
+Waiting player: HumanPlayer()
+Current board state:
+N|X|N
+N|O|N
+X|O|X
+
+Current player: HumanPlayer()
+Waiting player: MinimaxPlayer()
+Current board state:
+O|X|N
+N|O|N
+X|O|X
+
+Your move, pick a row (0-2):
+0
+Now pick a col (0-2):
+2
+Current player: MinimaxPlayer()
+Waiting player: HumanPlayer()
+Current board state:
+O|X|X
+N|O|N
+X|O|X
+
+Current player: HumanPlayer()
+Waiting player: MinimaxPlayer()
+Current board state:
+O|X|X
+N|O|O
+X|O|X
+
+Your move, pick a row (0-2):
+1
+Now pick a col (0-2):
+0
+Final board state:
+O|X|X
+X|O|O
+X|O|X
+
+Tie.
+

src/tic-tac-toe/output-b.txt

+Current player: MinimaxPlayer()
+Waiting player: HumanPlayer()
+Current board state:
+N|N|N
+N|N|N
+N|N|N
+
+Current player: HumanPlayer()
+Waiting player: MinimaxPlayer()
+Current board state:
+X|N|N
+N|N|N
+N|N|N
+
+Your move, pick a row (0-2):
+1
+Now pick a col (0-2):
+1
+Current player: MinimaxPlayer()
+Waiting player: HumanPlayer()
+Current board state:
+X|N|N
+N|O|N
+N|N|N
+
+Current player: HumanPlayer()
+Waiting player: MinimaxPlayer()
+Current board state:
+X|X|N
+N|O|N
+N|N|N
+
+Your move, pick a row (0-2):
+0
+Now pick a col (0-2):
+2
+Current player: MinimaxPlayer()
+Waiting player: HumanPlayer()
+Current board state:
+X|X|O
+N|O|N
+N|N|N
+
+Current player: HumanPlayer()
+Waiting player: MinimaxPlayer()
+Current board state:
+X|X|O
+N|O|N
+X|N|N
+
+Your move, pick a row (0-2):
+1
+Now pick a col (0-2):
+0
+Current player: MinimaxPlayer()
+Waiting player: HumanPlayer()
+Current board state:
+X|X|O
+O|O|N
+X|N|N
+
+Current player: HumanPlayer()
+Waiting player: MinimaxPlayer()
+Current board state:
+X|X|O
+O|O|X
+X|N|N
+
+Your move, pick a row (0-2):
+2
+Now pick a col (0-2):
+2
+Current player: MinimaxPlayer()
+Waiting player: HumanPlayer()
+Current board state:
+X|X|O
+O|O|X
+X|N|O
+
+Final board state:
+X|X|O
+O|O|X
+X|X|O
+
+Tie.
+

src/tic-tac-toe/output-c.txt

+Current player: HumanPlayer()
+Waiting player: MinimaxPlayer()
+Current board state:
+N|N|N
+N|N|N
+N|N|N
+
+Your move, pick a row (0-2):
+0
+Now pick a col (0-2):
+2
+Current player: MinimaxPlayer()
+Waiting player: HumanPlayer()
+Current board state:
+N|N|X
+N|N|N
+N|N|N
+
+Current player: HumanPlayer()
+Waiting player: MinimaxPlayer()
+Current board state:
+N|N|X
+N|O|N
+N|N|N
+
+Your move, pick a row (0-2):
+2
+Now pick a col (0-2):
+0
+Current player: MinimaxPlayer()
+Waiting player: HumanPlayer()
+Current board state:
+N|N|X
+N|O|N
+X|N|N
+
+Current player: HumanPlayer()
+Waiting player: MinimaxPlayer()
+Current board state:
+N|O|X
+N|O|N
+X|N|N
+
+Your move, pick a row (0-2):
+2
+Now pick a col (0-2):
+1
+Current player: MinimaxPlayer()
+Waiting player: HumanPlayer()
+Current board state:
+N|O|X
+N|O|N
+X|X|N
+
+Current player: HumanPlayer()
+Waiting player: MinimaxPlayer()
+Current board state:
+N|O|X
+N|O|N
+X|X|O
+
+Your move, pick a row (0-2):
+0
+Now pick a col (0-2):
+0
+Current player: MinimaxPlayer()
+Waiting player: HumanPlayer()
+Current board state:
+X|O|X
+N|O|N
+X|X|O
+
+Current player: HumanPlayer()
+Waiting player: MinimaxPlayer()
+Current board state:
+X|O|X
+O|O|N
+X|X|O
+
+Your move, pick a row (0-2):
+1
+Now pick a col (0-2):
+2
+Final board state:
+X|O|X
+O|O|X
+X|X|O
+
+Tie.
+

src/tic-tac-toe/output-d.txt

+Current player: MinimaxPlayer()
+Waiting player: HumanPlayer()
+Current board state:
+N|N|N
+N|N|N
+N|N|N
+
+Current player: HumanPlayer()
+Waiting player: MinimaxPlayer()
+Current board state:
+X|N|N
+N|N|N
+N|N|N
+
+Your move, pick a row (0-2):
+1
+Now pick a col (0-2):
+1
+Current player: MinimaxPlayer()
+Waiting player: HumanPlayer()
+Current board state:
+X|N|N
+N|O|N
+N|N|N
+
+Current player: HumanPlayer()
+Waiting player: MinimaxPlayer()
+Current board state:
+X|X|N
+N|O|N
+N|N|N
+
+Your move, pick a row (0-2):
+0
+Now pick a col (0-2):
+2
+Current player: MinimaxPlayer()
+Waiting player: HumanPlayer()
+Current board state:
+X|X|O
+N|O|N
+N|N|N
+
+Current player: HumanPlayer()
+Waiting player: MinimaxPlayer()
+Current board state:
+X|X|O
+N|O|N
+X|N|N
+
+Your move, pick a row (0-2):
+2
+Now pick a col (0-2):
+2
+Current player: MinimaxPlayer()
+Waiting player: HumanPlayer()
+Current board state:
+X|X|O
+N|O|N
+X|N|O
+
+Final board state:
+X|X|O
+X|O|N
+X|N|O
+
+You lose! Good day, sir.
+