-
-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathstate.rb
313 lines (272 loc) · 7.84 KB
/
state.rb
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
302
303
304
305
306
307
308
309
310
311
312
313
# frozen_string_literal: true
module Twenty48
#
# A board state. This class is implemented to try to keep its memory footprint
# small, because we're going to have many, many State instances.
#
# State objects are immutable.
#
# State objects implement content-based `eql?` and `hash`, because this is
# required by {FiniteMDP::Model}.
#
class State
include CommonState
def initialize(state_array)
@data = pack(state_array)
end
attr_reader :data
def board_size
Math.sqrt(data.size).to_i
end
#
# i = n * y + x
# x = i % n
# y = i / n
#
# x' = n - x - 1, y' = y =>
# i' = n*y + n - 1 - x = n*(y + 1) - (x + 1)
#
def reflect_horizontally
transform { |n, x, y| n * (y + 1) - (x + 1) }
end
#
# y' = n - y - 1, x' = x => i' = n*(n - y - 1) + x
#
def reflect_vertically
transform { |n, x, y| n * (n - y - 1) + x }
end
#
# x' = y, y' = x => i' = n*x + y
#
def transpose
transform { |n, x, y| n * x + y }
end
def sum
to_a.reject(&:zero?).map { |value| 2**value }.sum
end
def max_value
to_a.max
end
def win?(max_exponent)
to_a.any? { |value| value == max_exponent }
end
def lose?
(0...board_size**2).none? { |index| can_move_tile?(index) }
end
def cells_available
unpack(data).count(&:zero?)
end
#
# Does the state contain a pair of cells, both with value `value`, separated
# only by zero or more (known) zeros? If so, we can always swipe to get a
# `value + 1` tile.
#
# @param [Boolean?] zeros_unknown treat zero as 'unknown', not 'empty'
#
def adjacent_pair?(value, zeros_unknown = false)
any_row_or_col?(unpack(data)) do |line|
Line.adjacent_pair?(line, value, zeros_unknown)
end
end
def can_move_tile?(index)
state = unpack(data)
value = state[index]
return false if value.zero?
n = board_size
x = index % n
y = index.div(n)
[
[x.positive?, n * y + x - 1], # left
[x < n - 1, n * y + x + 1], # right
[y.positive?, n * (y - 1) + x], # up
[y < n - 1, n * (y + 1) + x], # down
].any? do |interior, adjacent_index|
next false unless interior
other = state[adjacent_index]
other == value || other.zero?
end
end
#
# Apply reflections and return the state with the lowest lexical index.
#
# There are eight reflections (including the identity) to be considered, as
# expected from the order of the dihedral group $D_4$.
#
# ```
# reflect hz: L -> R, R -> L
# reflect vt: U -> D, D -> U
# transpose: L -> U, U -> L, R -> D, D -> R
# anti-transpose: U -> R, R -> U, D -> L, L -> D
# rotate 90: L -> U, U -> R, R -> D, D -> L
# rotate 270: L -> D, D -> R, R -> U, U -> L
# rotate 180: U -> D, D -> U, L -> R, R -> L
# ```
#
def canonicalize
canonicalize_candidates.min
end
def canonicalize_candidates
horizontal_reflection = reflect_horizontally
vertical_reflection = reflect_vertically
transposition = transpose
rotated_90 = transposition.reflect_horizontally
rotated_180 = horizontal_reflection.reflect_vertically
rotated_270 = transposition.reflect_vertically
anti_transposition = rotated_90.reflect_vertically # transpose rotated 180
[self, horizontal_reflection, vertical_reflection,
transposition, anti_transposition,
rotated_90, rotated_180, rotated_270]
end
#
# Slide tiles left (-1, 0), right (+1, 0), up (0, -1) or down (0, +1).
# Signs are for consistency with the 2048 source.
#
def move(direction, zeros_unknown = false)
state = unpack(data)
case direction
when :left
update_each_row_with(state) do |row|
Line.move(row, zeros_unknown)
end
when :right
update_each_row_with(state) do |row|
Line.move(row.reverse, zeros_unknown).reverse
end
when :up
update_each_col_with(state) do |col|
Line.move(col, zeros_unknown)
end
when :down
update_each_col_with(state) do |col|
Line.move(col.reverse, zeros_unknown).reverse
end
else
raise "bad direction: #{direction}"
end
end
#
# Generate a 2^1 with 90% probability and a 2^2 with 10% probability.
#
RANDOM_TILES = { 1 => 0.9, 2 => 0.1 }.freeze
#
# Generate all possible random successors without the probabilities.
# We can add either a 2 or 4 tile (value 1 or 2) in any available cell.
# The returned states are not canonicalized. If there are no available
# cells, the state itself is returned as the only entry.
#
# TODO why not canonicalize?
#
def random_successors
state_array = to_a
new_states = []
state_array.each.with_index do |value, i|
next unless value.zero?
RANDOM_TILES.each_key do |new_value|
new_state_array = state_array.dup
new_state_array[i] = new_value
new_states << self.class.new(new_state_array)
end
end
new_states << self if new_states.empty?
new_states
end
#
# Generate the successors and include the probabilities. The states are
# canonicalized. The probabilities are normalized. If there are no
# available cells, the state itself is returned as the only entry, with
# probability 1.
#
def random_successors_hash
state_array = to_a
hash = Hash.new { 0 }
cells_available = self.cells_available
state_array.each.with_index do |value, i|
next unless value.zero?
RANDOM_TILES.each do |new_value, value_probability|
new_state_array = state_array.dup
new_state_array[i] = new_value
new_state = self.class.new(new_state_array).canonicalize
hash[new_state] += value_probability / cells_available
end
end
hash[self] = 1.0 if hash.empty?
check_normalised hash
hash
end
def to_a
unpack(data)
end
def to_s
to_a.to_s
end
def alt
to_a.map { |value| value == 0 ? '-' : 2**value }.join(' ')
end
def ==(other)
return false if other.nil?
data.eql?(other.data)
end
alias eql? ==
def hash
data.hash
end
def <=>(other)
data <=> other.data
end
def >=(other)
data >= other.data
end
private
def transform
n = board_size
state = unpack(data)
new_state = (0...state.length).map do |index|
y, x = index.divmod(n)
state[yield(n, x, y)]
end
self.class.new(new_state)
end
def any_row?(state)
n = board_size
(0...n).any? { |i| yield(state[i * n, n]) }
end
def any_col?(state)
n = board_size
(0...n).any? { |j| yield((0...n).map { |i| state[i * n + j] }) }
end
def any_row_or_col?(state, &block)
any_row?(state, &block) || any_col?(state, &block)
end
def update_each_row_with(state)
n = board_size
(0...n).each do |i|
state[i * n, n] = yield(state[i * n, n])
end
self.class.new(state)
end
def update_each_col_with(state)
n = board_size
(0...n).each do |j|
col = (0...n).map do |i|
state[i * n + j]
end
new_col = yield(col)
(0...n).each do |i|
state[i * n + j] = new_col[i]
end
end
self.class.new(state)
end
def check_normalised(hash)
raise "non-normalized: #{inspect}" unless
(hash.values.inject(:+) - 1).abs < 1e-6
end
PACK_FORMAT = 'c*' # signed chars are enough
def pack(state_array)
state_array.pack(PACK_FORMAT)
end
def unpack(state_data)
state_data.unpack(PACK_FORMAT)
end
end
end