diff options
| author | vehme003 <vehme003@umn.edu> | 2021-04-25 14:54:01 -0500 |
|---|---|---|
| committer | GitHub Enterprise <noreply-github@umn.edu> | 2021-04-25 14:54:01 -0500 |
| commit | 1c7a9d1e88e44362b2303a2a591e4993e4dc458f (patch) | |
| tree | 8bbba073ae0a576b335952f70807c158b571a9e0 /Algorithm.py | |
| parent | Delete board2.py (diff) | |
| download | csci4511w-1c7a9d1e88e44362b2303a2a591e4993e4dc458f.tar csci4511w-1c7a9d1e88e44362b2303a2a591e4993e4dc458f.tar.gz csci4511w-1c7a9d1e88e44362b2303a2a591e4993e4dc458f.tar.bz2 csci4511w-1c7a9d1e88e44362b2303a2a591e4993e4dc458f.tar.lz csci4511w-1c7a9d1e88e44362b2303a2a591e4993e4dc458f.tar.xz csci4511w-1c7a9d1e88e44362b2303a2a591e4993e4dc458f.tar.zst csci4511w-1c7a9d1e88e44362b2303a2a591e4993e4dc458f.zip | |
Add files via upload
Diffstat (limited to 'Algorithm.py')
| -rw-r--r-- | Algorithm.py | 68 |
1 files changed, 68 insertions, 0 deletions
diff --git a/Algorithm.py b/Algorithm.py new file mode 100644 index 0000000..85a9f15 --- /dev/null +++ b/Algorithm.py @@ -0,0 +1,68 @@ +class Algo: # A class for defining algorithms used (minimax and alpha-beta pruning)
+
+ def miniMax(State, Ply_num): # Function for the minimax algorithm
+
+ for i in range(State.Current.dimY):
+ for j in range(State.Current.dimX):
+ if State.Current.Mat[i][j] == ' ' and (j, i) not in State.children:
+ State.Make(j, i, True)
+ if Ply_num < 2:
+ return (i, j)
+
+ Minimum_Score = 1000
+ i = 0
+
+
+ j = 0
+ for k, z in State.children.items():
+ Result = Algo.Maximum(z, Ply_num - 1, Minimum_Score)
+ if Minimum_Score > Result:
+ Minimum_Score = Result
+ i = k[0]
+ j = k[1]
+
+ return (i, j)
+
+
+ def Maximum(State, Ply_num, Alpha): # Alpha-beta pruning function for taking care of Alpha values
+ if Ply_num == 0:
+ return State.CurrentScore
+
+ for i in range(State.Current.dimY):
+ for j in range(State.Current.dimX):
+ if State.Current.Mat[i][j] == ' ' and (j, i) not in State.children:
+ State.Make(j, i, False)
+
+ Maximum_Score = -1000
+ i = 0
+ j = 0
+ for k, z in State.children.items():
+ Result = Algo.Minimum(z, Ply_num - 1, Maximum_Score)
+ if Maximum_Score < Result:
+ Maximum_Score = Result
+ if Result > Alpha:
+ return Result
+
+ return Maximum_Score
+
+
+ def Minimum(State, Ply_num, Beta): # Alpha-beta pruning function for taking care of Beta values
+ if Ply_num == 0:
+ return State.CurrentScore
+
+ for i in range(State.Current.dimY):
+ for j in range(State.Current.dimX):
+ if State.Current.Mat[i][j] == ' ' and (j, i) not in State.children:
+ State.Make(j, i, True)
+
+ Minimum_Score = 1000
+ i = 0
+ j = 0
+ for k, z in State.children.items():
+ Result = Algo.Maximum(z, Ply_num - 1, Minimum_Score)
+ if Minimum_Score > Result:
+ Minimum_Score = Result
+ if Result < Beta:
+ return Result
+
+ return Minimum_Score
\ No newline at end of file |