Created
October 15, 2018 04:06
-
-
Save xiaodaigh/b3a4a04053b56f2b917b7bc4dcd25101 to your computer and use it in GitHub Desktop.
2048 Simulation challenge
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
using StatsBase | |
const DIRS = [:left, :up, :right, :down] | |
function init_game() | |
grid = zeros(Int8,4,4) | |
grid[rand(1:4),rand(1:4)] = rand2_1() | |
grid[rand(1:4),rand(1:4)] = rand2_1() | |
grid | |
end | |
rand2_1() = rand() < 0.1 ? 2 : 1 | |
# a function to simulate the move and return a reward | |
function move!(x, xinc, xstart, xend) | |
reward = 0 | |
@inbounds for i = xstart:xinc:xend # for each row move the left most piece first #if move_row = 1 then i control the row | |
if x[i] != 0 # if the position is occupied by a number move it | |
# firstly look "behind" to see if there is a number that is the same | |
# this is to deal better with situations like 2 2 4 4 | |
@inbounds for k = i+xinc:xinc:xend | |
if x[k] != 0 | |
if x[k] == x[i] | |
x[i] += 1 | |
reward += 2^x[i] | |
x[k] = 0 | |
end | |
break; | |
end | |
end | |
# now place it in the first empty slot | |
@inbounds for k = xstart:xinc:i | |
if x[k] == 0 | |
x[k] = x[i] | |
x[i] = 0 | |
end | |
end | |
end | |
end | |
(x, reward) | |
end | |
function move_left!(x) | |
move!(x, 1, 1, 4) | |
end | |
function move_right!(x) | |
move!(x, -1, 4, 1) | |
end | |
function move!(grid::Array{T,2}, direction) where T <: Integer | |
reward::Int16 = zero(Int16) | |
if direction == :left | |
for j = 1:4 | |
#grid[j,:] .= move_left!(grid[j,:]) | |
(tmp, new_reward) = move_left!(@view grid[j,:]) | |
reward += new_reward | |
end | |
elseif direction == :right | |
for j = 1:4 | |
#grid[j,:] .= move_right!(grid[j,:]) | |
(tmp, new_reward) = move_right!(@view grid[j,:]) | |
reward += new_reward | |
end | |
elseif direction == :up | |
for j = 1:4 | |
#grid[:,j] .= move_left!(grid[:,j]) | |
(tmp, new_reward) = move_left!(@view grid[:,j]) | |
reward += new_reward | |
end | |
else | |
for j = 1:4 | |
#grid[:,j] .= move_right!(grid[:,j]) | |
(tmp, new_reward) = move_right!(@view grid[:,j]) | |
reward += new_reward | |
end | |
end | |
(grid, reward) | |
end | |
function simulate_move!(grid) | |
directions = sample(DIRS, 4 , replace = false) | |
for i in 1:3 | |
d1 = directions[i] | |
(grid, ok, cart, two_or_four, reward) = simulate_move!(grid, d1) | |
if ok | |
return (grid, true, d1, cart, two_or_four, reward) | |
end | |
end | |
(grid, ok, cart, two_or_four, reward) = simulate_move!(grid, directions[4]) | |
(grid, ok, directions[4], cart, two_or_four, reward) | |
end | |
# assume no need to check for validate moves | |
function simulate_move!(grid, direction) | |
tmp_grid = copy(grid) | |
(grid, reward) = move!(grid, direction) | |
if all(tmp_grid .== grid) | |
return (grid, false, CartesianIndex{2}(-1,-1), -1, 0) | |
else | |
cart = rand(findall(grid .== 0)) # randomly choose one empty slot | |
one_or_two = rand2_1() | |
grid[cart] = one_or_two | |
return (grid, true, cart, one_or_two, reward) | |
end | |
end | |
function simulate_game!(grid, lim) | |
init_grid = copy(grid) | |
seq = Symbol[]::Array{Symbol,1} | |
cartarr = CartesianIndex{2}[] | |
one_or_two_arr = Int8[] | |
reward_vec = Int16[] | |
ok = true | |
while ok | |
(grid, ok1, move, cart, one_or_two, new_reward) = simulate_move!(grid) | |
ok = ok1 & all(grid .< lim) | |
push!(seq, move) | |
push!(cartarr, cart) | |
push!(one_or_two_arr, one_or_two) | |
push!(reward_vec, new_reward) | |
end | |
(init_grid, grid, seq, cartarr, one_or_two_arr, reward_vec) | |
end | |
function simulate_game() | |
init = init_game() | |
simulate_game!(init, Inf) | |
end | |
using BenchmarkTools | |
@benchmark simulate_game() | |
# BenchmarkTools.Trial: | |
# memory estimate: 398.47 KiB | |
# allocs estimate: 628 | |
# -------------- | |
# minimum time: 118.100 μs (0.00% GC) | |
# median time: 542.347 μs (0.00% GC) | |
# mean time: 669.478 μs (13.89% GC) | |
# maximum time: 70.973 ms (98.78% GC) | |
# -------------- | |
# samples: 7422 | |
# evals/sample: 1 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment