-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathconnect4.py
201 lines (171 loc) · 7.91 KB
/
connect4.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
from random import choice
from copy import deepcopy
player = 'o'
enemy = 'x'
empty = '.'
width = 7
height = 6
# Connect 4 Board Object
class Board:
# Create new board
def __init__(self):
self.state = {}
for col in range(width):
for row in range(height):
self.state[(col,row)] = empty
# Prints the board at the current state
# No return
def print_board(self,state):
for i in range(height-1,-1,-1):
for j in range(0,width):
print(str(state[(j,i)]) + " ", end="")
print()
print()
# Applies move to state
# Returns new state
def do_move(self,state,turn,move):
new_state = deepcopy(state)
if move in new_state:
if move in self.get_valid_moves(new_state):
if new_state[move] == empty:
new_state[move] = turn
else:
print("do_move: Tried to do " + str(move) + " but position is " + str(new_state[move]))
else:
print("do_move: Not a valid move. " + str(move))
else:
print("do_move: Move not in board. " + str(move))
self.state = new_state
self.turn = player if turn == enemy else enemy
return new_state
# Gets the best move to do given a state and a move set
# Returns best move
def get_best_move(self,state,moves = []):
# TODO : Optimize move choice. Pick moves closer to middle, with more pieces around, if piece above isn't a
# winning move for enemy, scissors, etc.
#if not provided any moves, get valid moves
if not moves:
moves = self.get_valid_moves(state)
# check for winning/losing moves
winning_moves = self.get_winning_moves(state,moves)
if winning_moves:
move = winning_moves[0][0]
else: # if no winning/losing moves, pick random move
move = choice(moves)
return move
# Get moves you can do for next turn
# Returns valid moves at state of game
def get_valid_moves(self,state):
valid_moves = []
for col in range(width):
for row in range(height):
if state[col,row] == empty:
valid_moves.append((col,row))
break
return valid_moves
# Check the valid moves and see if any are moves that will make either player win
# Returns the winning moves for either player in a list with entries (move, player)
# Winning moves are at beginning of list and losing moves (ie must block) are at end of list
def get_winning_moves(self,state,valid_moves=[]):
winning_moves = []
players = [player,enemy]
if not valid_moves: # this will let us check if any moves are winning/losing moves
valid_moves = self.get_valid_moves(state)
for turn in players: # check for both player and enemy
for move in valid_moves:
winnable = 0
# check vertical win
if move[1] > 2:
for i in range(1,4):
if (state[(move[0],move[1]-i)] == turn):
if winnable == 2:
if turn == player:
winning_moves.insert(0,(move,turn))
else:
winning_moves.append((move,turn))
else:
winnable += 1
else:
break
winnable = 0
#horizontal win
for k in range(-1,2,2): # check to both left and right
if (move,turn) not in winning_moves: # haven't already found win from one direction
for i in range(1,4):
if (move[0]-i*k,move[1]) in state: # check 3 left/right
if (state[(move[0]-i*k,move[1])] == turn):
if winnable == 2:
if turn == player:
winning_moves.insert(0,(move,turn))
else:
winning_moves.append((move,turn))
break
else:
winnable += 1
else:
break
winnable = 0
# / win
for k in range(-1,2,2): # check bottom left and top right directions
if (move,turn) not in winning_moves: # haven't already found win from one direction
for i in range(1,4):
if (move[0]-i*k,move[1]-i*k) in state:
if (state[(move[0]-i*k,move[1]-i*k)] == turn):
if winnable == 2:
if turn == player:
winning_moves.insert(0,(move,turn))
else:
winning_moves.append((move,turn))
break
else:
winnable += 1
else:
break
winnable = 0
# \ win
for k in range(-1,2,2): # check bottom right and top left directions
if (move,turn) not in winning_moves: # haven't already found win from one direction
for i in range(1,4):
if (move[0]-i*k,move[1]+i*k) in state:
if (state[(move[0]-i*k,move[1]+i*k)] == turn):
if winnable == 2:
if turn == player:
winning_moves.insert(0,(move,turn))
else:
winning_moves.append((move,turn))
break
else:
winnable += 1
else:
break
return winning_moves
# Checks if game at state is over by looking at the last possible moves (top piece of every row)
# Returns (game ended, player that won)
def is_ended(self,state):
if sum([1 if taken_piece == player or taken_piece == enemy
else 0 for taken_piece in state.values()]) == height*width:
return (True,None)
last_moves = []
for col in range(width):
for row in range(height):
if state[col,row] == empty: # if we reach an empty spot (going up vertically)
if (col,row-1) in state: # then add the spot right before empty spot
last_moves.append((col,row-1))
break
elif row == height - 1: # if we reach the top
last_moves.append((col,row))
won = self.get_winning_moves(state,last_moves)
# won will contains wins for either player
# so we must check if that player actually owns the piece.
# we need a separate to maintain what we need to remove or else it will not properly
# iterate through every item
remove_list = []
for move in won:
if state[move[0]] != move[1]:
remove_list.append(move)
for move in remove_list:
won.remove(move)
if len(won) == 0:
return (False,None)
else:
return (True,won[0][1])