-
Notifications
You must be signed in to change notification settings - Fork 0
/
Search_2048.py
executable file
·301 lines (280 loc) · 17 KB
/
Search_2048.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
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Mon Jun 8 14:35:25 2020
@author: Jonathan
"""
import gc
import numpy as np
from Game_2048 import Game_2048
from copy import deepcopy
class Search_2048():
def __init__(self, Board):
try:
self.Board = Board
except:
type(Board) != np.ndarray
self.Nodes = {}
self.GameClass = Game_2048(len(Board))
pass
# Move function, almost identical to the one within the game, but optimised
# for use in this function as called for AgentMove
def AgentMove(self, Direction, Board):
# Uses the dict of directions to specify a direction to rotate the old
# board in before the operation continues.
OldBoard = np.rot90(Board, Direction)
NewBoard = np.zeros([len(OldBoard),len(OldBoard)], dtype=int)
# Iterates through each row one at a time. For every row, will iterate
# through each column.
for Row,Col in enumerate(OldBoard):
# First creates a new row of empty 0s the length of the original row
NewRow = np.zeros(len(Col), dtype=Col.dtype)
# 'j' is an iterator that will count from the left-most cell and move
# along as it fills up.
j = 0
# Using 'Prev', the last-seen value can be used to check if the next
# 'New' cell should be the sum of 2 values, or just the last value
# slid over from the right, or other direction.
Prev = None
for i in range(Col.size):
# If the column is a zero, then the cell will be skipped over,
# since all zeros are basically ignored...
if Col[i] != 0:
# If there is no previous value stored, this will pull the
# next seen value and store it.
if (Prev == None):
Prev = Col[i]
# Now, if the next cell matches the Previously-seen value,
# The two values will be added and the value saved to the
# next "New" value seen.
elif Prev == Col[i]:
NewRow[j] = 2 * Col[i]
j += 1
Prev = None
# Finally, if the previous value looks wildly different, it
# will just push the previous value into the new row's cell.
else:
NewRow[j] = Prev
j += 1
Prev = Col[i]
# If there is still a value stored as "Previous" in the original set,
# it will push that last stored value into the new row's cell.
if Prev != None:
NewRow[j] = Prev
# Finally, pushes the new Row into the new board array.
NewBoard[Row] = NewRow
# If there is no change in the board, then it is an invalid move, and
# the board does not change. Otherwise, adds a new cell.
if (NewBoard == OldBoard).all():
return None
else:
# Returns the new, shifted Board.
return np.rot90(NewBoard, -Direction)
def GetAgentMove(self, Board, Layer):
MaxReward = None
OptimalMove = None
for Direction in range(4):
NewBoard = self.AgentMove(Direction, Board)
try:
if NewBoard.any() != False:
reward = NewBoard.max()
if reward > MaxReward:
MaxReward = reward
OptimalMove = Direction
# self.Node[Layer]["board"] = NewBoard
except:
type(NewBoard) == bool
return MaxReward, OptimalMove
# Returns the number of empty spaces. This algorithm currently wants to have
# fewest empty spaces on the board.
def EmptySpaces(self, Board):
EmptySpaces = (2*len(Board)) - np.count_nonzero(Board)
return EmptySpaces
def BFS(self, Board):
OptimalMove = None
MaxReward = 0
''' Move_1 = None
Reward_1 = 0
Move_2 = None
Reward_2 = 0
Move_3 = None
Reward_3 = 0 '''
_, UniqueCount = np.unique(Board, return_counts = True)
UniqueVals = np.count_nonzero(UniqueCount == 1)
Spaces = self.EmptySpaces(Board)
# Iterating through each direction possible.
for Direction in range(4):
# Gets a new board based on the predicted movement at each stage.
NewBoard = self.AgentMove(Direction, Board)
# The Try-Catch statements prevent the "None" returns from being
# processed. This speeds up later searches when the move is invalid.
try:
if NewBoard.all() != None:
''' # If there is no move stored currently, saves the current
# move as valid, otherwise does nothing.
Move_1 = Direction if (Move_1 is None) else Move_1
# If the reward at this state is higher than before (i.e.
# if moving in a particular direction gets you a higher
# score, saves that move.)
if Reward_1 < NewBoard.max():
Reward_1 = NewBoard.max()
Move_1 = Direction
# If the saved reward is the same in each direction, now
# prefers to take a step that will reduce the number of
# empty spaces on the board. (Only checks for the first
# move, since next-generation moves are fairly stochastic
# by nature)
elif Reward_1 == NewBoard.max():
if self.EmptySpaces(NewBoard) < OrigSpace:
Reward_1 = NewBoard.max()
Move_1 = Direction
# This is an array of possible random permutations given the
# number of possible spaces on the board. The algorithm wants
# to maximise the possible score, so a 3-level search is
# performed. '''
PossibleBoards = self.GetChanceBoard(NewBoard)
for L2_Board in PossibleBoards:
for L2_Direction in range(4):
L2_NewBoard = self.AgentMove(L2_Direction, L2_Board)
try:
if L2_NewBoard.all() != None:
''' # L2 and L3 are only concerned with the maximum
# possible score. For an even deeper search,
# this stochastic search could possibly
# find the true maximum, but to save on
# computational power, and since this is just
# a proof-of-concept, I'm stopping at 3 layers.
Move_2 = Direction if (Move_2 is None) else Move_2
if L2_NewBoard.max() > Reward_1:
Reward_2 = L2_NewBoard.max()
Move_2 = Direction '''
L2_PossibleBoards = self.GetChanceBoard(L2_NewBoard)
for L3_Board in L2_PossibleBoards:
for L3_Direction in range(4):
L3_NewBoard = self.AgentMove(L3_Direction, L3_Board)
try:
if L3_NewBoard.all() != None:
L3_PossibleBoards = self.GetChanceBoard(L3_NewBoard)
for L4_Board in L3_PossibleBoards:
for L4_Direction in range(4):
L4_NewBoard = self.AgentMove(L4_Direction, L4_Board)
try:
if L4_NewBoard.all() != None:
L4_PossibleBoards = self.GetChanceBoard(L4_NewBoard)
for L5_Board in L4_PossibleBoards:
for L5_Direction in range(4):
L5_NewBoard = self.AgentMove(L5_Direction, L5_Board)
try:
if L5_NewBoard.all() != None:
if OptimalMove == None:
OptimalMove = Direction
else:
''' First priority: highest possible reward. '''
if L5_NewBoard.max() > MaxReward:
MaxReward = L5_NewBoard.max()
OptimalMove = Direction
Spaces = self.EmptySpaces(L5_NewBoard)
''' If the reward is the same, tries to maximise
the number of empty spaces on the board '''
elif L5_NewBoard.max() == MaxReward:
_, NewCount = np.unique(L5_NewBoard, return_counts = True)
NewUniqueVals = np.count_nonzero(NewCount == 1)
if NewUniqueVals > UniqueVals:
MaxReward = L5_NewBoard.max()
OptimalMove = Direction
Spaces = self.EmptySpaces(L5_NewBoard)
UniqueVals = NewUniqueVals
elif self.EmptySpaces(L5_NewBoard) > Spaces:
MaxReward = L5_NewBoard.max()
OptimalMove = Direction
Spaces = self.EmptySpaces(L5_NewBoard)
except:
L5_NewBoard == None
except:
L4_NewBoard == None
# if OptimalMove == None:
# OptimalMove = Direction
# else:
# ''' First priority: highest possible reward. '''
# if L3_NewBoard.max() > MaxReward:
# MaxReward = L2_NewBoard.max()
# OptimalMove = Direction
# Spaces = self.EmptySpaces(L3_NewBoard)
# ''' If the reward is the same, tries to maximise
# the number of empty spaces on the board '''
# elif L3_NewBoard.max() == MaxReward:
# _, NewCount = np.unique(L3_NewBoard, return_counts = True)
# NewUniqueVals = np.count_nonzero(NewCount == 1)
# if NewUniqueVals > UniqueVals:
# MaxReward = L2_NewBoard.max()
# OptimalMove = Direction
# Spaces = self.EmptySpaces(L3_NewBoard)
# UniqueVals = NewUniqueVals
# elif self.EmptySpaces(L3_NewBoard) > Spaces:
# MaxReward = L2_NewBoard.max()
# OptimalMove = Direction
# Spaces = self.EmptySpaces(L3_NewBoard)
except:
L3_NewBoard == None
except:
L2_NewBoard == None
except:
NewBoard == None
''' OptimalMove = Move_1 if Reward_1 < Reward_2 else Move_2
OptimalMove = OptimalMove if (Reward_1 ** 2) <= Reward_3 else Move_1 '''
return OptimalMove, MaxReward
def FillBoard_1(self, x, y, Board):
Output = []
# For each possible value in the cell, puts and output board in the array
# of possible board permutations. Range 1,3 means that values of 1 and 2
# appear - which means 2^1 and 2^2: 2 and 4.
# for rnd in range(1,3):
# NewBoard = deepcopy(Board)
# NewBoard[x][y] = 2 ** rnd
# Output.append(NewBoard)
NewBoard = deepcopy(Board)
NewBoard[x][y] = 2
Output.append(NewBoard)
return Output
# Currently not used.
def FillBoard_2(self, x, y, i, j, Board):
Output = []
for rnd_1 in range(1,3):
for rnd_2 in range(1,3):
NewBoard = deepcopy(Board)
NewBoard[x][y] = 2 ** rnd_1
NewBoard[i][j] = 2 ** rnd_2
Output.append(NewBoard)
return Output
def GetChanceBoard(self, Board):
PossibleBoards = []
x,y = (Board == 0).nonzero()
for n in range(len(x)):
# if len(x) == 1:
''' Temporarily removed the 2nd random cell, so only ever one cell
is filled per move. Makes it a bit easier to start off with - the
number of possibilities otherwise are quite endless. '''
PossibleBoards.extend(self.FillBoard_1(x[n],y[n],Board))
# for q in range(len(x)):
# if q != n:
# PossibleBoards.extend(self.FillBoard_2( x[n],y[n], x[q],y[q], Board ))
return PossibleBoards
# Actual Function:
if __name__ == "__main__":
Game = Game_2048(4)
Search = Search_2048(Game.Board)
print("Original:")
print(Game.Board)
PreviousTurn = 0
while Game.Playing:
Move,_ = Search.BFS(Game.Board)
Game.Move(Move)
print(Game.Board, 'Move: ', Move, 'Turn: ', Game.Turns, "Score: ", Game.Board.max())
# Error check - there was a bug earlier where the algorithm was tryying to