OpenCV Python: 2048 Game Solver

A sample application of Digit Recognition.
2048 solver algorithm based on term2048-AI

import cv2
import numpy as np
import win32api, win32gui, win32ui, win32con, win32com.client
from PIL import Image, ImageFont, ImageDraw, ImageOps

# create training model based on the given TTF font file
# http://projectproto.blogspot.com/2014/07/opencv-python-digit-recognition.html
def createDigitsModel(fontfile, digitheight):
    font = ImageFont.truetype(fontfile, digitheight)
    samples =  np.empty((0,digitheight*(digitheight/2)))
    responses = []
    for n in range(10):
        pil_im = Image.new("RGB", (digitheight, digitheight*2))
        ImageDraw.Draw(pil_im).text((0, 0), str(n), font=font)
        pil_im = pil_im.crop(pil_im.getbbox())
        pil_im = ImageOps.invert(pil_im)
        #pil_im.save(str(n) + ".png")

        # convert to cv image
        cv_image = cv2.cvtColor(np.array( pil_im ), cv2.COLOR_RGBA2BGRA)
        gray = cv2.cvtColor(cv_image, cv2.COLOR_BGR2GRAY)
        blur = cv2.GaussianBlur(gray,(5,5),0)
        thresh = cv2.adaptiveThreshold(blur,255,1,1,11,2)

        roi = cv2.resize(thresh,(digitheight,digitheight/2))
        responses.append( n )
        sample = roi.reshape((1,digitheight*(digitheight/2)))
        samples = np.append(samples,sample,0)

    samples = np.array(samples,np.float32)
    responses = np.array(responses,np.float32)
    
    model = cv2.KNearest()
    model.train(samples,responses)
    return model

class Board(object):
    UP, DOWN, LEFT, RIGHT = 1, 2, 3, 4
    FONT = "font/ClearSans-Bold.ttf"
    def __init__(self, clientwindowtitle):
        self.hwnd = self.getClientWindow(clientwindowtitle)
        if not self.hwnd:
            return
        self.hwndDC = win32gui.GetWindowDC(self.hwnd)
        self.mfcDC  = win32ui.CreateDCFromHandle(self.hwndDC)
        self.saveDC = self.mfcDC.CreateCompatibleDC()

        self.cl, self.ct, right, bot = win32gui.GetClientRect(self.hwnd)
        self.cw, self.ch = right-self.cl, bot-self.ct
        self.cl += win32api.GetSystemMetrics(win32con.SM_CXSIZEFRAME)
        self.ct += win32api.GetSystemMetrics(win32con.SM_CYSIZEFRAME)
        self.ct += win32api.GetSystemMetrics(win32con.SM_CYCAPTION)
        self.ch += win32api.GetSystemMetrics(win32con.SM_CYSIZEFRAME)*2

        self.saveBitMap = win32ui.CreateBitmap()
        self.saveBitMap.CreateCompatibleBitmap(self.mfcDC, self.cw, self.ch)
        self.saveDC.SelectObject(self.saveBitMap)

        self.tiles, self.tileheight, self.contour = self.findTiles(self.getClientFrame())
        if not len(self.tiles):
            return
        self.digitheight = self.tileheight / 2
        self.digitsmodel = createDigitsModel(self.FONT, self.digitheight)

        self.update()

    def getClientWindow(self, windowtitle):
        toplist, winlist = [], []
        def enum_cb(hwnd, results):
            winlist.append((hwnd, win32gui.GetWindowText(hwnd)))
        win32gui.EnumWindows(enum_cb, toplist)
        window = [(hwnd, title) for hwnd, title in winlist if windowtitle.lower() in title.lower()]
        if not len(window):
            return 0
        return window[0][0]

    def getClientFrame(self):
        self.saveDC.BitBlt((0, 0), (self.cw, self.ch),
                    self.mfcDC, (self.cl, self.ct), win32con.SRCCOPY)

        bmpinfo = self.saveBitMap.GetInfo()
        bmpstr = self.saveBitMap.GetBitmapBits(True)

        pil_img = Image.frombuffer( 'RGB',
            (bmpinfo['bmWidth'], bmpinfo['bmHeight']),
            bmpstr, 'raw', 'BGRX', 0, 1)

        array = np.array( pil_img )
        cvimage = cv2.cvtColor(array, cv2.COLOR_RGBA2BGRA)
        return cvimage

    def findTiles(self, cvframe):
        tiles, avgh = [], 0
        
        gray = cv2.cvtColor(cvframe,cv2.COLOR_BGRA2GRAY)
        thresh = cv2.adaptiveThreshold(gray,255,1,1,11,2)
        contours, hierarchy = cv2.findContours(thresh.copy(), cv2.RETR_TREE, cv2.CHAIN_APPROX_SIMPLE)

        def findBoard(contours): # get largest square
            ww, sqcnt = 10, None
            for cnt in contours:
                x,y,w,h = cv2.boundingRect(cnt)
                if w>ww and abs(w-h)<w/10:
                    ww = w
                    sqcnt = cnt
            return sqcnt

        board = findBoard(contours)
        if board==None:
            print 'board not found!'
            return tiles, avgh, board
        
        bx,by,bw,bh = cv2.boundingRect(board)
        #cv2.rectangle(cvframe,(bx,by),(bx+bw,by+bh),(0,255,0),2)
        #cv2.imshow('board',cvframe)
        #cv2.waitKey(0)
        #cv2.destroyWindow( 'board' )        
        maxh = bh/4
        minh = (maxh*4)/5
        count = 0
        for contour in contours:
            x,y,w,h = cv2.boundingRect(contour)
            if y>by and w>minh and w<maxh and h>minh and h<maxh:
                avgh += h
                count += 1
        if not count:
            print 'no tile found!'
            return tiles, avgh, board

        avgh = avgh / count
        margin = (bh-avgh*4)/5
        for row in range(4):
            for col in range(4):
                x0 = bx + avgh*col + margin*(col+1)
                x1 = x0 + avgh
                y0 = by + avgh*row + margin*(row+1)
                y1 = y0 + avgh
                tiles.append([x0, y0, x1, y1])
                #cv2.rectangle(cvframe,(x0,y0),(x1,y1),(0,255,0),2)
        #cv2.imshow('tiles',cvframe)
        #cv2.waitKey(0)
        #cv2.destroyWindow( 'tiles' )       
        return tiles, avgh, board
    
    def getTileThreshold(self, tileimage):
        gray = cv2.cvtColor(tileimage,cv2.COLOR_BGR2GRAY)
        row, col = gray.shape
        tmp = gray.copy().reshape(1, row*col)
        counts = np.bincount(tmp[0])
        sort = np.sort(counts)

        modes, freqs = [], []
        for i in range(len(sort)):
            freq = sort[-1-i]
            if freq < 4:
                break
            mode = np.where(counts==freq)[0][0]
            modes.append(mode)
            freqs.append(freq)

        bg, fg = modes[0], modes[0]
        for i in range(len(modes)):
            fg = modes[i]
            #if abs(bg-fg)>=48:
            if abs(bg-fg)>32 and abs(fg-150)>4: # 150?!
                break
        #print bg, fg
        if bg>fg: # needs dark background ?
            tmp = 255 - tmp
            bg, fg = 255-bg, 255-fg
        
        tmp = tmp.reshape(row, col)
        ret, thresh = cv2.threshold(tmp,(bg+fg)/2,255,cv2.THRESH_BINARY)        
        return thresh
    
    def getTileNumbers(self, cvframe):
        numbers = []
        outframe = np.zeros(cvframe.shape,np.uint8)
        def guessNumber(digits):
            for i in range(1,16):
                nn = 2**i
                ss = str(nn)
                dd = [int(c) for c in ss]
                if set(digits) == set(dd):
                    return nn
            return 0
        
        for tile in self.tiles:
            x0,y0,x1,y1 = tile
            tileimage = cvframe[y0:y1,x0:x1]
            cv2.rectangle(cvframe,(x0,y0),(x1,y1),(0,255,0),2)
            cv2.rectangle(outframe,(x0,y0),(x1,y1),(0,255,0),1)

            thresh = self.getTileThreshold(tileimage)
            contours,hierarchy = cv2.findContours(thresh.copy(),cv2.RETR_EXTERNAL,cv2.CHAIN_APPROX_SIMPLE)

            dh = self.digitheight
            digits = []
            for cnt in contours:
                x,y,w,h = cv2.boundingRect(cnt)
                if  h>w and h>(dh*1)/5 and h<(dh*6)/5:
                    cv2.rectangle(cvframe,(x0+x,y0+y),(x0+x+w,y0+y+h),(0,0,255),1)
                    roi = thresh[y:y+h,x:x+w]
                    roi = cv2.resize(roi,(dh,dh/2))
                    roi = roi.reshape((1,dh*(dh/2)))
                    roi = np.float32(roi)
                    retval, results, neigh_resp, dists = self.digitsmodel.find_nearest(roi, k=1)
                    digit = int((results[0][0]))
                    string = str(digit)
                    digits.append(digit)
                    cv2.putText(outframe,string,(x0+x,y0+y+h),0,float(h)/24,(0,255,0))

            numbers.append(guessNumber(digits))
        return numbers, outframe

    def getWindowHandle(self):
        return self.hwnd

    def getBoardContour(self):
        return self.contour
    
    def update(self):
        frame = self.getClientFrame()
        self.tilenumbers, outframe = self.getTileNumbers(frame)
        return self.tilenumbers, frame, outframe

    def copyTileNumbers(self):
        return self.tilenumbers[:]

    def getCell(self, tiles, x, y):
        return tiles[(y*4)+x]

    def setCell(self, tiles, x, y, v):
        tiles[(y*4)+x] = v
        return tiles

    def getCol(self, tiles, x):
        return [self.getCell(tiles, x, i) for i in range(4)]

    def setCol(self, tiles, x, col):
        for i in range(4):
            self.setCell(tiles, x, i, col[i])
        return tiles

    def getLine(self, tiles, y):
        return [self.getCell(tiles, i, y) for i in range(4)]

    def setLine(self, tiles, y, line):
        for i in range(4):
            self.setCell(tiles, i, y, line[i])
        return tiles

    def validMove(self, tilenumbers, direction):
        if direction == self.UP or direction == self.DOWN:
            for x in range(4):
                col = self.getCol(tilenumbers, x)
                for y in range(4):
                    if(y < 4-1 and col[y] == col[y+1] and col[y]!=0):
                        return True
                    if(direction == self.DOWN and y > 0 and col[y] == 0 and col[y-1]!=0):
                        return True
                    if(direction == self.UP and y < 4-1 and col[y] == 0 and col[y+1]!=0):
                        return True
        if direction == self.LEFT or direction == self.RIGHT:
            for y in range(4):
                line = self.getLine(tilenumbers, y)
                for x in range(4):
                    if(x < 4-1 and line[x] == line[x+1] and line[x]!=0):
                        return True
                    if(direction == self.RIGHT and x > 0 and line[x] == 0 and line[x-1]!=0):
                        return True
                    if(direction == self.LEFT and x < 4-1 and line[x] == 0 and line[x+1]!=0):
                        return True
        return False

    def moveTileNumbers(self, tilenumbers, direction):
        def collapseline(line, direction):
            if (direction==self.LEFT or direction==self.UP):
                inc = 1
                rg = xrange(0, 4-1, inc)
            else:
                inc = -1
                rg = xrange(4-1, 0, inc)
            pts = 0
            for i in rg:
                if line[i] == 0:
                    continue
                if line[i] == line[i+inc]:
                    v = line[i]*2
                    line[i] = v
                    line[i+inc] = 0
                    pts += v
            return line, pts
        def moveline(line, directsion):
            nl = [c for c in line if c != 0]
            if directsion==self.UP or directsion==self.LEFT:
                return nl + [0] * (4 - len(nl))
            return [0] * (4 - len(nl)) + nl
            
        score = 0
        if direction==self.LEFT or direction==self.RIGHT:
            for i in range(4):
                origin = self.getLine(tilenumbers, i)
                line = moveline(origin, direction)
                collapsed, pts = collapseline(line, direction)
                new = moveline(collapsed, direction)
                tilenumbers = self.setLine(tilenumbers, i, new)
                score += pts
        elif direction==self.UP or direction==self.DOWN:
            for i in range(4):
                origin = self.getCol(tilenumbers, i)
                line = moveline(origin, direction)
                collapsed, pts = collapseline(line, direction)
                new = moveline(collapsed, direction)
                tilenumbers = self.setCol(tilenumbers, i, new)
                score += pts
                
        return score, tilenumbers      

# AI based on "term2048-AI"
# https://github.com/Nicola17/term2048-AI
class AI(object):
    def __init__(self, board):
        self.board = board
        
    def nextMove(self):
        tilenumbers = self.board.copyTileNumbers()
        m, s = self.nextMoveRecur(tilenumbers[:],3,3)
        return m

    def nextMoveRecur(self, tilenumbers, depth, maxDepth, base=0.9):
        bestMove, bestScore = 0, -1
        for m in range(1,5):
            if(self.board.validMove(tilenumbers, m)):
                score, newtiles = self.board.moveTileNumbers(tilenumbers[:], m)
                score, critical = self.evaluate(newtiles)
                newtiles = self.board.setCell(newtiles,critical[0],critical[1],2)
                if depth != 0:
                    my_m,my_s = self.nextMoveRecur(newtiles[:],depth-1,maxDepth)
                    score += my_s*pow(base,maxDepth-depth+1)
                if(score > bestScore):
                    bestMove = m
                    bestScore = score
                
        return bestMove, bestScore

    def evaluate(self, tilenumbers, commonRatio=0.25):

        maxVal = 0.
        criticalTile = (-1, -1)
        
        for i in range(8):
            linearWeightedVal = 0
            invert = False if i<4 else True
            weight = 1.
            ctile = (-1,-1)

            cond = i%4
            for y in range(4):
                for x in range(4):
                    if cond==0:
                        b_x = 4-1-x if invert else x
                        b_y = y
                    elif cond==1:
                        b_x = x
                        b_y = 4-1-y if invert else y
                    elif cond==2:
                        b_x = 4-1-x if invert else x
                        b_y = 4-1-y
                    elif cond==3:
                        b_x = 4-1-x
                        b_y = 4-1-y if invert else y
                        
                    currVal=self.board.getCell(tilenumbers,b_x,b_y)
                    if(currVal == 0 and ctile == (-1,-1)):
                        ctile = (b_x,b_y)
                    linearWeightedVal += currVal*weight
                    weight *= commonRatio
                invert = not invert
            
            if linearWeightedVal > maxVal:
                maxVal = linearWeightedVal
                criticalTile = ctile

        return maxVal, criticalTile

    def solveBoard(self, moveinterval=500):
        boardHWND = self.board.getWindowHandle()
        if not boardHWND:
            return False
        bx, by, bw, bh = cv2.boundingRect(self.board.getBoardContour())
        x0, x1, y0, y1 = bx, bx+bw, by, by+bh

        win32gui.SetForegroundWindow(boardHWND)
        shell = win32com.client.Dispatch('WScript.Shell')
        print 'Set the focus to the Game Window, and the press this arrow key:'
        keymove = ['UP', 'DOWN', 'LEFT', 'RIGHT']

        delay = moveinterval / 3 # milliseconds delay to cancel board animation effect
        prev_numbers = []
        while True:
            numbers, inframe, outframe = self.board.update()
            if numbers != prev_numbers:
                cv2.waitKey(delay)
                numbers, inframe, outframe = self.board.update()
                if numbers == prev_numbers: # recheck if has changed
                    continue
                prev_numbers = numbers
                move = ai.nextMove()
                if move:
                    key = keymove[move-1]
                    shell.SendKeys('{%s}'%key)
                    print key
                    cv2.waitKey(delay)
                    cv2.imshow('CV copy',inframe[y0:y1,x0:x1])
                    cv2.imshow('CV out', outframe[y0:y1,x0:x1])
            cv2.waitKey(delay)
        cv2.destroyWindow( 'CV copy' )
        cv2.destroyWindow( 'CV out' )
        

# http://gabrielecirulli.github.io/2048/
# http://ov3y.github.io/2048-AI/
board = Board("2048 - Google Chrome")
#board = Board("2048 - Mozilla Firefox")

ai = AI(board)
ai.solveBoard(360)

print 'stopped.'

download: 2048opencv.py

# open this site with Chrome: http://gabrielecirulli.github.io/2048/
board = Board("2048 - Google Chrome")
ai = AI(board)
ai.solveBoard()

demo video:


==================================
update:
Solving the Android version of 2048..
Android phone is running a VNC server (vnc server & viewer are both slow!).

python script: 2048opencv_adb.py

tip: send [touchscreen]swipe event through adb:

adb shell input swipe x1 y1 x2 y2

sources:
gabrielecirulli.github
diaryofatinker.blogspot
stackoverflow.com