2
\$\begingroup\$

Inspired by this answer on stackoverflow for AI implementation in 2048 game.

I have been trying to make AI calculate best move by playing the game given specific times in memory preceding by one specific move first, then averaging the score and declaring move with highest score as best move.

The workflow is fine, i am getting results good and as described in the answer, the chances of win in this game at 100 runs per move is about 80%.

The problem is: My implementation in python is really slow. If somebody please could suggest me improvements in my program to increase speed, that'd be so helpful.

Here's extract of main items:

from random import choice, random
import numpy as np
import time

def left(grid):
    #assumption: grid is 4 x 4 numpy matrix
    l = grid.copy()
    for j in range(4):
        res = []
        merged = False
        for i in l[j]:
            if i==0:continue
            if res and i == res[-1] and not merged:
                res[-1] += i
                merged = True
            else:
                if res: merged = False
                res.append(i)
        for i in range(4 - len(res)): res.append(0)
        l[j] = res
    return l

def right(grid):
    l = grid.copy()
    for j in range(4):
        res = []
        merged = False
        for i in range(4):
            t = l[j][i]
            if t == 0: continue
            if res and t == res[-1] and not merged:
                res[-1]+=t
                merged = True
            else:
                if res: merged = False
                res.append(t)
        for i in range(4-len(res)): res = [0]+res
        l[j] = res
    return l

def down(grid):
    l = grid.copy()
    for j in range(4):
        res = []
        merged = False
        for i in range(4):
            t = l[i][j]
            if t == 0: continue
            if res and t == res[-1] and not merged:
                res[-1]+=t
                merged = True
            else:
                if res: merged = False
                res.append(t)
        for i in range(4-len(res)): res=[0]+res
        l[:, j] = res
    return l

def up(grid):
    l = grid.copy()
    for j in range(4):
        res = []
        merged = False
        for i in range(4):
            t = l[-i-1][j]
            if t == 0: continue
            if res and t == res[-1] and not merged:
                res[-1]+=t
                merged = True
            else:
                if res: merged = False
                res.append(t)
        for i in range(4-len(res)): res=[0]+res
        l[:, j] = res[::-1]
    return l

def c(grid, move):
    if move == 2: return left(grid)
    if move == 0: return up(grid)
    if move == 1: return down(grid)
    if move == 3: return right(grid)

def isvalid(grid):
    if 0 in grid: return True
    l = grid
    for i in range(3):
        for j in range(4):
            if l[i][j] == l[i+1][j]: return True
        if l[i][0] == l[i][1] or l[i][1] == l[i][2] or l[i][2] == l[i][3]: return True
    i = 3
    if l[i][0] == l[i][1] or l[i][1] == l[i][2] or l[i][2] == l[i][3]: return True
    return False

ind = np.arange(16).reshape(4,4)
def next_play(grid, move):
    #assumption: grid is 4 x 4 matrix
    if move not in range(4): return grid #invalid move.
    moved_grid = c(grid, move)           # c moves grid by specific move "move".
    moved = not (moved_grid == grid).all()
    if not moved: return grid # return as it was
    if 0 not in moved_grid: return moved_grid  #no spawn needed
    idx = choice(ind[moved_grid==0]) #randomly picked empty place's index
    moved_grid[idx//4][idx%4] = 2 if random() < .9 else 4
    return moved_grid

def rand_moves(data,first_move,times): #data is playing grid, numpy matrix 4 x 4
    assert times >0, 'Wrong value of times'
    score = 0
    k = range(4)
    for _ in range(times):
        data1 = data.copy()
        data1 = next_play(data1, first_move) #next_play moves grid & generate tile randomly on an empty place if moved
        while isvalid(data1):                #isvalid checks validity of grid, ie playable or not.
            data1 = next_play(data1, choice(k)) #choice is random.choice func.
            score+= data1.max()
    return score/times

def getAvailableMoves(data):
    data_list= [(c(data,i),i) for i in range(4)]
    ret = []
    for data1,i in data_list:
        if (data1==data).all():continue
        else:
            ret.append(i)
    return ret

def getBestMove(data, times = 10):
    sc, mv = float('-inf'), None
    for move in getAvailableMoves(data):
        score = 0
        score += rand_moves(data.copy(),move,times)
        if score > sc:
            sc= score
            mv = move
        elif score == sc:
            mv = choice([mv, move]) #randomly choose one of them
    return mv #if none, case handing occurs at caller side.

data = np.asarray([[2,0,0,2],
                   [4,4,0,2],
                   [32,32,2,8],
                   [0,0,0,2]]) #a sample grid
t1 = time.time()
print(getBestMove(data, 100))
print(time.time() - t1, 's')

You can run this whole program by copying it. You'll notice that its taking 2.5 to 4 seconds or more for each move decision. I need at least 100 runs in memory for deciding best move. This is really slow, since at least thousand moves or above are needed for scoring better, which is quite bad for me.

I don't know C++ or C language, thus can't shift in those language or make cython's use to optimize them.

Any suggestions or improvements would be helpful . Thanks.

For ease, directly TryItOnline

EDIT 1

I tried to store solutions of vectors in dictionary since accessing is faster in dictionary, here's the code:

import pickle
with open('ds_small.pickle', 'rb') as var:
    ds =  pickle.load(var) #list of dicts
d1 = ds[0]  #dictionary containing left shift of all possible tuples of size 4, having elems from 0 to 2048, 2's powers
d2 = ds[1] #dictionary containing right shift of all possible tuples of size 4, having elems from 0 to 2048, 2's powers

def l(grid):
    l1=grid.copy()
    for i in range(4):
        l1[i] = d1[tuple(l1[i])]
    return l1

def r(grid):
    l1 = grid.copy()
    for i in range(4):
        l1[i] = d2[tuple(l1[i])]
    return l1

def u(grid):
    l1 = grid.copy()
    for i in range(4):
        l1[:,i] = d1[tuple(l1[:,i])]
    return l1

def d(grid):
    l1 = grid.copy()
    for i in range(4):
        l1[:,i] = d2[tuple(l1[:,i])]
    return l1

def c(grid, move):
    if move == 2: return l(grid)
    if move == 0: return u(grid)
    if move == 1: return d(grid)
    if move == 3: return r(grid)

Performance incremented. Time got low to 1.8 seconds per move average. But you see, its still quite slow. Suggestions please.

Edit 2 Improved performance by .2 sec by improving isvalid function.

I tried improving next_play function but no success.

Edit 3

I tried cython here, it surely increased performance:

from random import choice, random
import numpy as np
cimport numpy as np
import time
import pickle
cimport cython

@cython.boundscheck(False)
def left(np.ndarray grid):
    #assumption: grid is 4 x 4 numpy matrix
    cdef np.ndarray l = grid.copy()
    cdef int j, i, p, merged;
    cdef long t;
    cdef list res;
    for j in range(4):
        res = [];
        merged = 0
        for i in range(4):
            t = l[j][-i-1]
            if t == 0: continue
            if res and t == res[-1] and merged == 0:
                res[-1]+=t
                merged = 1
            else:
                if res: merged = 0
                res+=[t]
        for p in range(4-len(res)): res = [0]+res
        l[j] = res[::-1]
    return l

@cython.boundscheck(False)
def right(np.ndarray grid):
    cdef np.ndarray l = grid.copy()
    cdef int j, i, p, merged;
    cdef long t;
    cdef list res;
    for j in range(4):
        res = []
        merged = 0
        for i in range(4):
            t = l[j][i]
            if t == 0: continue
            if res and t == res[-1] and merged == 0:
                res[-1]+=t
                merged = 1
            else:
                if res: merged = 0
                res+=[t]
        for p in range(4-len(res)): res = [0]+res
        l[j] = res
    return l

@cython.boundscheck(False)
def down(np.ndarray grid):
    cdef np.ndarray l = grid.copy()
    cdef int j, i, p, merged;
    cdef long t;
    cdef list res;
    for j in range(4):
        res = []
        merged = 0
        for i in range(4):
            t = l[i][j]
            if t == 0: continue
            if res and t == res[-1] and merged == 0:
                res[-1]+=t
                merged = 1
            else:
                if res: merged = 0
                res+=[t]
        for p in range(4-len(res)): res=[0]+res
        l[:, j] = res
    return l

@cython.boundscheck(False)
def up(np.ndarray grid):
    cdef np.ndarray l = grid.copy()
    cdef int j, i, p, merged;
    cdef long t;
    cdef list res;
    for j in range(4):
        res = []
        merged = 0
        for i in range(4):
            t = l[-i-1][j]
            if t == 0: continue
            if res and t == res[-1] and merged == 0:
                res[-1]+=t
                merged = 1
            else:
                if res: merged = 0
                res+=[t]
        for p in range(4-len(res)): res=[0]+res
        l[:, j] = res[::-1]
    return l

@cython.boundscheck(False)
@cython.wraparound(False)
def c(np.ndarray grid, int move):
    if move == 2: return left(grid)
    if move == 0: return up(grid)
    if move == 1: return down(grid)
    if move == 3: return right(grid)

@cython.boundscheck(False)
@cython.wraparound(False)
def isvalid(np.ndarray l):#l is grid
    if 0 in l: return True
    cdef int i, j;
    for i in range(3):
        for j in range(4):
            if l[i][j] == l[i+1][j]: return True
        if l[i][0] == l[i][1] or l[i][1] == l[i][2] or l[i][2] == l[i][3]: return True
    i = 3
    if l[i][0] == l[i][1] or l[i][1] == l[i][2] or l[i][2] == l[i][3]: return True
    return False

cdef np.ndarray ind = np.arange(16).reshape(4,4)

@cython.boundscheck(False)
@cython.wraparound(False)
def next_play(np.ndarray grid, int move):
    #assumption: grid is 4 x 4 matrix
    if move not in range(4): return grid #invalid move.
    cdef np.ndarray moved_grid = c(grid, move)           # c moves grid by specific move "move".
    cdef int moved = (moved_grid == grid).all()^1
    if moved == 0: return grid # return as it was
    cdef np.ndarray p = ind[moved_grid==0]
    if len(p) == 0: return moved_grid  #no spawn needed
    cdef int idx = choice(p) #randomly picked empty place's index
    moved_grid[idx//4][idx%4] = 2 if random() < .9 else 4
    return moved_grid

@cython.boundscheck(False)
def rand_moves(np.ndarray data,int first_move,int times): #data is playing grid, numpy matrix 4 x 4
    assert times >0, 'Wrong value of times'
    cdef int score = 0;
    k = range(4)
    cdef int p,m;
    cdef np.ndarray data1;
    for p in range(times):
        data1 = data.copy()
        data1 = next_play(data1, first_move) #next_play moves grid & generate tile randomly on an empty place if moved
        m = data.max()
        while isvalid(data1):                #isvalid checks validity of grid, ie playable or not.
            data1 = next_play(data1, choice(k)) #choice is random.choice func.
            m *= 1 if 2*m not in data else 2
            score+= m#data1.max()
    return score/times


def getAvailableMoves(np.ndarray data):
    data_list= [(c(data,i),i) for i in range(4)]
    ret = []
    cdef int move;
    for data1,move in data_list:
        if (data1==data).all():continue
        else:
            ret.append(move)
    return ret

def getMove(data, int times = 10):
    cdef float sc = float('-inf')
    mv = None
    cdef int move;
    cdef int score;
    for move in getAvailableMoves(data):
        score = 0
        score += rand_moves(data.copy(),move,times)
        if score > sc:
            sc= score
            mv = move
        elif score == sc:
            mv = choice([mv, move]) #randomly choose one of them
    return mv #if none, case handing occurs at caller side.

#if __name__ == '__main__':
def do():
    cdef np.ndarray data = np.asarray([[2,2,0,2],
                       [4,4,0,2],
                       [32,32,32,8],
                       [0,0,0,2]]) #a sample grid

    print(data)

    t1 = time.time()
    from sys import argv
    print(getMove(data, 100))#int(argv[1])))
    t_time = time.time() - t1
    print(t_time, 's')
    return t_time

At this edit, the average speed is 1.35763 seconds per move for 100 runs in memory. I immensely need atleast 5 moves per second.

\$\endgroup\$
8
  • 2
    \$\begingroup\$ Not the downvoter, but have you done any profiling to determine what precisely is slowing you code down? \$\endgroup\$ – Brian Feb 9 '20 at 18:01
  • \$\begingroup\$ @Brian Its sure that its all because of the game trials in each move. It needs optimization is all i know. The post i linked has js version of that algorithm, this is the link for that js version github.com/ronzil/2048-AI. I did see the code and saw that its roughly doing same stuff in ai.js. I think its python's slowness, but since i can't shift to other language, thus trying to see if optimization is possible. \$\endgroup\$ – Vicrobot Feb 9 '20 at 18:14
  • \$\begingroup\$ The Javascript version looks a lot different than yours, and not just because of the different language. In that version there is a set of "prototype vectors" to deal with the different move directions; in yours you apparently do all kinds of transformations on the entire array to set it up for just a single move. \$\endgroup\$ – David K Feb 9 '20 at 21:45
  • \$\begingroup\$ @DavidK I separated each move's function. Still slow. \$\endgroup\$ – Vicrobot Feb 9 '20 at 23:46
  • 1
    \$\begingroup\$ @Vicrobot: Please update your question in that case. Since you have not received any answer yet, you can freely do so. At the moment it is unclear which of your three solutions should be reviewed, or should all of them be reviewed? I would suggest to pick one (maybe the most vanilla one, or maybe the fastest) and ask about that. You can ask about the other approaches in separate questions (maybe a day or so later in order to incorporate any generically applicable advice you might receive). \$\endgroup\$ – Graipher Feb 13 '20 at 8:44
2
\$\begingroup\$

A couple observations:

  1. Using different names for the playing grid (data, grid, l) makes it more difficult to follow the code.

  2. For the top level call getMove(data, 100), let's assume the 'up' is a possible move. Then c(data, up) gets called 101 times.

    getMove() calls getAvailableMoves() which calls c(data, i) once for each direction (but the moves are discarded).

    getMove() then calls rand_moves() which calls next_play(data1, first_move) 100 times. And next_play() calls c(data, move).

  3. Move constant calculations outside of the loop. In random_moves():

        for p in range(times):
            data1 = data.copy()
            data1 = next_play(data1, first_move)
            m = data.max()
    

    should be:

        data = next_play(data, first_move)
        m = data.max()
        for p in range(times):
            data1 = data.copy()
            ...
    
  4. Extra copying. For example:

    getMove() calls rand_move() with a copy of data:

    rand_moves(data.copy(),move,times)
    

    rand_move() then makes another copy:

    data1 = data.copy()
    
  5. is_valid() could use features of numpy array:

    def isvalid(np.ndarray grid): return ( 0 in grid or (grid[:3]==grid[1:]).any() or (grid[:,:3]==grid[:,1:]).any() )

  6. It might be possible to cache some of the score calculations. For example, there are many ways to arrive at a grid like:

    2 4 0 0
    0 0 0 0
    0 0 0 0
    0 0 0 0
    

    Figuring out a way to cache the score for that grid might save some duplicate calculations.

\$\endgroup\$
1
  • \$\begingroup\$ Thanks so much for taking this deep look in there. I implemented what you said, but performance gain was 0.005 seconds only for each real move per 100 runs in memory. I had to leave my hashing of dict because those trivial left right functions are performing better due to most conversion to c types in cython. Is there any way i could use hashing in cython just like dictionary of python? \$\endgroup\$ – Vicrobot Feb 12 '20 at 16:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.