No BSD License  

Highlights from
Finding the Similar Entries: A Quantitative Approach based on CPU Runtime Behavior

image thumbnail

Finding the Similar Entries: A Quantitative Approach based on CPU Runtime Behavior

by

 

08 Apr 2009 (Updated )

Entry to Matlab contest Spring 2009

collaborationSover(board)
function [moves,score] = collaborationSover(board)
    rand( 'state', 0 );
    rand( 57, 1 );
    [m,n] = size( board );
    pegCount = sum( board( : )>0 );
        rows = m + 4;
    rv = 5:rows;
    cols = n + 4;
    cv = 5:cols;
    fill = (pegCount - nnz( board<0 ))/(m*n);
        i = repmat( rv', [ n, 1 ] );
        j = reshape( repmat( cv, [ m, 1 ] ), [ m*n, 1 ] );
    mm = m + 8;
    nn = n + 8;
    ppBoard = zeros( mm, nn );
    ppBoard( : ) = -1;
        ppBoard( rv, cv ) = board;
    I = [ i; i; i; i ];
    J = [ j; j; j; j ];
    K = [ i; i; i - 2; i + 2 ];
    L = [ j - 2; j + 2; j; j ];
    K1 = [ i; i; i - 4; i + 4 ];
    L1 = [ j - 4; j + 4; j; j ];
    K2 = [ i - 2; i + 2; i - 2; i + 2 ];
    L2 = [ j - 2; j + 2; j + 2; j - 2 ];
    K3 = [ i + 2; i - 2; i - 2; i + 2 ];
    L3 = [ j - 2; j + 2; j - 2; j + 2 ];
    F = I + (J - 1)*mm;
    T = K + (L - 1)*mm;
    M = (F + T)*0.5;
        bogusMoves = (ppBoard( F )<0) | (ppBoard( M )<0) | (ppBoard( T )<0);
        I( bogusMoves ) = [  ];
        J( bogusMoves ) = [  ];
        K( bogusMoves ) = [  ];
        L( bogusMoves ) = [  ];
        F( bogusMoves ) = [  ];
        T( bogusMoves ) = [  ];
        M( bogusMoves ) = [  ];
        K1( bogusMoves ) = [  ];
        K2( bogusMoves ) = [  ];
        K3( bogusMoves ) = [  ];
        L1( bogusMoves ) = [  ];
        L2( bogusMoves ) = [  ];
        L3( bogusMoves ) = [  ];
        [moveid1,moveid2,moveid3] = createMoves( M, F, T );
    T1 = K1 + (L1 - 1)*mm;
    T2 = K2 + (L2 - 1)*mm;
    T3 = K3 + (L3 - 1)*mm;
    TT = [ T1, T2, T3 ];
    M1 = (T + T1)*0.5;
    M2 = (T + T2)*0.5;
    M3 = (T + T3)*0.5;
    MM = [ M1, M2, M3 ];
    MV = [ I, J, K, L ];
    MV1 = [ K, L, K1, L1 ];
    MV2 = [ K, L, K2, L2 ];
    MV3 = [ K, L, K3, L3 ];
    MVV = { MV1, MV2, MV3 };
    [moves,score] = subsoltweak( ppBoard, F, T, M, pegCount, TT, MM, MV, MVV, moveid1, moveid2, moveid3 );
    maxsum = sum( board( board>0 ) );
    maxscore = 0.81*maxsum;
        for dd = getDdlist( pegCount )
        if (size( moves, 1 )<=3) || (score>maxscore)
    moves = moves - 4;
        return
end
        [newMoves,newScore] = subsol( ppBoard, dd, 0, F, T, M, pegCount, TT, MM, MV, moveid1, moveid2, moveid3 );
            if (newScore>score)
                score = newScore;
                moves = newMoves;
end
end
        k = 1;
    while k<=(min( (pegCount*0.0078125) + 1, 3 )*(score<maxsum*0.79))
        [newMoves,newScore] = subsol( ppBoard, 1.0, 1.16, F, T, M, pegCount, TT, MM, MV, moveid1, moveid2, moveid3 );
            if (newScore>score)
                score = newScore;
                moves = newMoves;
end
        k = k + 1;
end
    moves = moves - 4;
    if (pegCount<272) && (fill<.96)*(score<maxsum*0.775)
        [newMoves,newScore] = solveri( board, rows, cols );
            if (newScore>score)
                score = newScore;
                moves = newMoves;
end
end
end
function ddlist = getDdlist(pegCount)
        RX = 2*(rand( 4, 1 ) - 0.5);
    switch ceil( pegCount/102.5 )
                case 1
            ddlist = [ 1 + 0.1*RX( 1 ), 0.05 ];
                case 2
            ddlist = [ 6.8, 5, 2.1, 1 + 0.1*RX( 2 ), 0.6 + 0.1*RX( 2 ), 0.45 ];
                case 3
            ddlist = [ 0.05, 2.1, 1 + 0.1*RX( 3 ), 0.6 + 0.1*RX( 3 ), 0.4 + 0.1*RX( 3 ), 0.254 ];
        case 5
            ddlist = [ 0.05, 2.1, 0.6 + 0.1*RX( 4 ), 0.18 ];
            otherwise
            ddlist = [ 0.05, 2.1, 1 + 0.1*RX( 4 ), 0.592 ];
end
end
function [moveid1,moveid2,moveid3] = createMoves(M,F,T)
    ni = max( F );
        nmove1 = zeros( ni, 1 );
    nmove2 = nmove1;
    nmove3 = nmove1;
        moveid1 = zeros( ni, 4 );
    moveid2 = moveid1;
    moveid3 = moveid1;
    for k = 1:numel( F )
            nmove1( F( k ) ) = nmove1( F( k ) ) + 1;
            moveid1( F( k ), nmove1( F( k ) ) ) = k;
            nmove2( M( k ) ) = nmove2( M( k ) ) + 1;
            moveid2( M( k ), nmove2( M( k ) ) ) = k;
            nmove3( T( k ) ) = nmove3( T( k ) ) + 1;
            moveid3( T( k ), nmove3( T( k ) ) ) = k;
end
end
function [moves,last_score] = solveri(board,rows,cols)
    pBoard = zeros( rows, cols );
    pBoard( : ) = -1;
    pBoard( 3:end - 2, 3:end - 2 ) = board;
    nNonHoles = nnz( pBoard );
    moves = zeros( nNonHoles, 4 );
    cellbuf = zeros( nNonHoles*4, 1 );
        valbuf = cellbuf;
        movebuf = cellbuf;
        hopbuf = cellbuf;
    hop_list = cellbuf;
        dead_weight = 0.1*mean( board( board>0 ) );
    count = 0;
        last_move = 0;
    score = 0;
        last_pos = 0;
        last_score = 0;
        depth = 10;
        hop_max = 0;
        hop_cnt = 0;
    [lJumpers,lValues,lLandings] = CalculateMoves( pBoard );
    while true
        if isempty( lJumpers )
            break
end
        FindHops( pBoard, lJumpers, lLandings, lValues );
            if (hop_max~=0) && (hop_cnt>2)
                for zh = 1:hop_cnt - 1
                lJumpers = [ lJumpers; hop_list( zh ) ];
                lLandings = [ lLandings; hop_list( zh + 1 ) ];
                lValues = [ lValues; hop_max ];
                DoMove( numel( lJumpers ) );
end
    else
            [hop_values,pos] = sort( lValues, 'descend' );
            lValues = hop_values;
            lJumpers = lJumpers( pos );
            lLandings = lLandings( pos );
            for zh = 1:min( depth, numel( lJumpers ) )
                [newB,newC,newM,newV] = ProcessMove( pBoard, zh, lJumpers, lLandings, lValues );
                    FindHops( newB, newC, newM, newV );
                    hop_values( zh ) = hop_values( zh ) + hop_max;
end
            [max_val,pos] = max( hop_values );
            DoMove( pos )
end
end
    moves( last_pos + 1:end, : ) = [  ];
        function DoMove(pos)
        max_cell = lJumpers( pos );
        max_move = lLandings( pos );
        count = count + 1;
            moves( count, : ) = [ mod( max_cell - 2, rows ), ceil( max_cell/rows ) - 2, mod( max_move - 2, rows ), ceil( max_move/rows ) - 2 ];
            brem = (max_cell + max_move)*0.5;
        score = score + pBoard( brem );
            if (max_cell~=last_move)
            score = score - pBoard( max_cell );
end
            if (score>last_score)
                last_pos = count;
                last_score = score;
end
        [pBoard,lJumpers,lLandings,lValues] = ProcessMove( pBoard, pos, lJumpers, lLandings, lValues );
            last_move = max_move;
end
    function FindHops(pBoard,lJumpers,lLandings,lValues)
        hop_max = 0;
        if ~isempty( lJumpers )
            dst = lLandings( 1:numel( lJumpers ) );
            tmp = (~pBoard( dst + 2 ) & pBoard( dst + 1 ));
            tmp = (~pBoard( dst - 2 ) & pBoard( dst - 1 )) | tmp;
            tmp = (~pBoard( dst - 2*rows ) & pBoard( dst - rows )) | tmp;
            tmp = (~pBoard( dst + 2*rows ) & pBoard( dst + rows )) | tmp;
            idx = find( ~tmp );
            if ~isempty( idx )
                tmp2 = lValues( idx );
                [hop_max,tmp2] = max( tmp2 );
                tmp2 = idx( tmp2 );
                        hop_cnt = 2;
                hop_list( 1 ) = lJumpers( tmp2 );
                hop_list( 2 ) = lLandings( tmp2 );
end
            idx = find( tmp )';
            for ii = idx
                hopbuf( 1 ) = lJumpers( ii );
                FindHopTree( pBoard, lJumpers( ii ), lLandings( ii ), lValues( ii ), 2 );
end
end
end
    function FindHopTree(pBoard,src,dst,hop_value,count)
        pBoard( dst ) = pBoard( src );
        pBoard( (src + dst)*0.5 ) = 0;
        pBoard( src ) = 0;
        hopbuf( count ) = dst;
        if ~pBoard( dst + 2 ) && pBoard( dst + 1 )>0
            FindHopTree( pBoard, dst, dst + 2, hop_value + pBoard( dst + 1 ), count + 1 );
end
        if ~pBoard( dst - 2 ) && pBoard( dst - 1 )>0
            FindHopTree( pBoard, dst, dst - 2, hop_value + pBoard( dst - 1 ), count + 1 );
end
        if ~pBoard( dst + 2*rows ) && pBoard( dst + rows )>0
            FindHopTree( pBoard, dst, dst + 2*rows, hop_value + pBoard( dst + rows ), count + 1 );
end
        if ~pBoard( dst - 2*rows ) && pBoard( dst - rows )>0
            FindHopTree( pBoard, dst, dst - 2*rows, hop_value + pBoard( dst - rows ), count + 1 );
end
                if hop_value>hop_max
                    hop_max = hop_value;
            hop_cnt = count;
            hop_list( 1:count ) = hopbuf( 1:count );
end
end
    function n = CalculateBall(pBoard,src,dst,n)
        POP = pBoard( (src + dst)*0.5 );
        if POP>0 && ~pBoard( dst ) && pBoard( src )>0
                            n = n + 1;
            if sum( pBoard( [ dst + 1, dst - 1, dst + rows, dst - rows ] )>0 )==1
                valbuf( n ) = POP - pBoard( src ) - dead_weight;
    else
                valbuf( n ) = POP - pBoard( src );
end
                            cellbuf( n ) = src;
                            movebuf( n ) = dst;
end
end
    function n = CalculateHole(pBoard,dst,src,n)
            pop = (src + dst)*0.5;
        if pBoard( pop )>0 && pBoard( src )>0
                            n = n + 1;
            if sum( pBoard( [ dst + 1, dst - 1, dst + rows, dst - rows ] )>0 )==1
                valbuf( n ) = pBoard( pop ) - pBoard( src ) - dead_weight;
    else
                valbuf( n ) = pBoard( pop ) - pBoard( src );
end
                            cellbuf( n ) = src;
                            movebuf( n ) = dst;
end
end
    function [new_cell_list,new_value_list,new_move_list] = CalculateMoves(pBoard)
        zb = find( pBoard>0 );
        zz = find( ~pBoard );
            n = 0;
            if numel( zz )<numel( zb )
                for zi = 1:numel( zz )
                    i = zz( zi );
                n = CalculateHole( pBoard, i, i - 2, n );
                n = CalculateHole( pBoard, i, i + 2, n );
                n = CalculateHole( pBoard, i, i - rows*2, n );
                n = CalculateHole( pBoard, i, i + rows*2, n );
end
    else
                for zi = 1:numel( zb )
                    i = zb( zi );
                n = CalculateBall( pBoard, i, i - 2, n );
                n = CalculateBall( pBoard, i, i + 2, n );
                n = CalculateBall( pBoard, i, i - rows*2, n );
                n = CalculateBall( pBoard, i, i + rows*2, n );
end
end
            new_cell_list = cellbuf( 1:n );
            new_value_list = valbuf( 1:n );
            new_move_list = movebuf( 1:n );
end
    function [pBoard,lJumpers,lLandings,lValues] = ProcessMove(pBoard,pos,lJumpers,lLandings,lValues)
        src = lJumpers( pos );
        dst = lLandings( pos );
            pop = (src + dst)*0.5;
        pBoard( dst ) = pBoard( src );
        pBoard( pop ) = 0;
        pBoard( src ) = 0;
            u = src - pop;
            if (abs( u )==1)
                v = rows;
    else
            v = 1;
end
        lLandings( logical( lLandings==dst ) ) = 0;
        lLandings( logical( lJumpers==src ) ) = 0;
        lLandings( logical( lJumpers==pop ) ) = 0;
        rem_src = find( lJumpers==src - v );
        lLandings( rem_src( lLandings( rem_src )==src + v ) ) = 0;
        rem_src = find( lJumpers==src + v );
        lLandings( rem_src( lLandings( rem_src )==src - v ) ) = 0;
        rem_src = find( lJumpers==src - v - u );
        lLandings( rem_src( lLandings( rem_src )==src + v - u ) ) = 0;
        rem_src = find( lJumpers==src + v - u );
        lLandings( rem_src( lLandings( rem_src )==src - v - u ) ) = 0;
        [lLandings,rem_dst] = sort( lLandings, 'descend' );
        lJumpers = lJumpers( rem_dst );
        lValues = lValues( rem_dst );
        ncnt = find( ~lLandings, 1, 'first' );
        lJumpers = lJumpers( 1:ncnt - 1 );
        lValues = lValues( 1:ncnt - 1 );
        lLandings = lLandings( 1:ncnt - 1 );
            n = 0;
        n = CalculateBall( pBoard, src - 3*u, src - u, n );
        n = CalculateBall( pBoard, src + 2*v - u, src - u, n );
        n = CalculateBall( pBoard, src + 2*v, src, n );
        n = CalculateBall( pBoard, src + 2*u, src, n );
        n = CalculateBall( pBoard, src - 2*v, src, n );
        n = CalculateBall( pBoard, src - 2*v - u, src - u, n );
        n = CalculateBall( pBoard, dst, dst - 2*u, n );
        n = CalculateBall( pBoard, dst, dst - 2*v, n );
        n = CalculateBall( pBoard, dst, dst + 2*v, n );
            clf = src - v - 2*u;
            crt = src + v - 2*u;
        if ~pBoard( clf )
            n = CalculateBall( pBoard, crt, clf, n );
end
        if ~pBoard( crt )
            n = CalculateBall( pBoard, clf, crt, n );
end
            if (n>0)
                if (ncnt>1)
                lJumpers = [ lJumpers; cellbuf( 1:n ) ];
                lLandings = [ lLandings; movebuf( 1:n ) ];
                lValues = [ lValues; valbuf( 1:n ) ];
    else
                lJumpers = cellbuf( 1:n );
                lValues = valbuf( 1:n );
                lLandings = movebuf( 1:n );
end
end
end
end
function [moves,v] = subsol(board,d,rfac,F,T,M,pegCount,TT,MM,MV,moveid1,moveid2,moveid3)
        rrr = rfac*rand( 5000, 1 );
    moves = zeros( pegCount - 1, 4 );
    v0 = zeros( pegCount - 1, 1 );
        Bzero = ~board;
        Bpos = board>0;
        Bmax = max( board, 0 );
    validMoves = (Bpos( F ) & Bzero( T ) & Bpos( M ));
    h = find( validMoves );
                C0 = board( M( h ) ) - board( F( h ) );
            if d
                CV = max( Bmax( MM( h, : ) ) .* Bzero( TT( h, : ) ), [  ], 2 );
    else
                CV = 0;
end
                [v,k] = max( (1 + rrr( 1:length( C0 ) )) .* (C0 + CV*d) );
    v0( 1 ) = C0( k );
                k = h( k );
    moves( 1, : ) = MV( k, : );
        T0 = T( k );
            F0 = F( k );
            M0 = M( k );
    t = 2;
            Bmax( T0 ) = board( F0 );
            Bmax( F0 ) = 0;
            Bmax( M0 ) = 0;
            board( T0 ) = board( F0 );
            Bzero( T0 ) = false;
            Bpos( T0 ) = true;
            board( F0 ) = 0;
            Bzero( F0 ) = true;
            Bpos( F0 ) = false;
            board( M0 ) = 0;
            Bpos( M0 ) = false;
            Bzero( M0 ) = true;
        FF = [ F0, M0, T0 ];
        originatingMoves = moveid1( FF, : );
        originatingMoves = originatingMoves( originatingMoves>0 );
        jumpedMoves = moveid2( FF, : );
        jumpedMoves = jumpedMoves( jumpedMoves>0 );
        terminatingMoves = moveid3( FF, : );
        terminatingMoves = terminatingMoves( terminatingMoves>0 );
        allMoves = [ originatingMoves; jumpedMoves; terminatingMoves ];
        validMoves( allMoves ) = Bpos( F( allMoves ) ) & Bzero( T( allMoves ) ) & Bpos( M( allMoves ) );
    h = find( validMoves );
    while ~isempty( h )
        if (numel( h )>1)
                c = find( F( h )==T0 );
            if ~isempty( c )
                h = h( c );
                C0 = board( M( h ) );
    else
                C0 = board( M( h ) ) - board( F( h ) );
end
            if d
                CV = max( Bmax( MM( h, : ) ) .* Bzero( TT( h, : ) ), [  ], 2 );
    else
                CV = 0;
end
                [v,k] = max( (1 + rrr( 1:length( C0 ) )) .* (C0 + CV*d) );
                v0( t ) = C0( k );
                k = h( k );
    else
                k = h( 1 );
                v0( t ) = board( M( k ) ) - board( F( k ) );
end
            moves( t, : ) = MV( k, : );
        T0 = T( k );
            F0 = F( k );
            M0 = M( k );
        t = t + 1;
            Bmax( T0 ) = board( F0 );
            Bmax( F0 ) = 0;
            Bmax( M0 ) = 0;
            board( T0 ) = board( F0 );
            Bzero( T0 ) = false;
            Bpos( T0 ) = true;
            board( F0 ) = 0;
            Bzero( F0 ) = true;
            Bpos( F0 ) = false;
            board( M0 ) = 0;
            Bpos( M0 ) = false;
            Bzero( M0 ) = true;
        FF = [ F0, M0, T0 ];
        originatingMoves = moveid1( FF, : );
        originatingMoves = originatingMoves( originatingMoves>0 );
        jumpedMoves = moveid2( FF, : );
        jumpedMoves = jumpedMoves( jumpedMoves>0 );
        terminatingMoves = moveid3( FF, : );
        terminatingMoves = terminatingMoves( terminatingMoves>0 );
        allMoves = [ originatingMoves; jumpedMoves; terminatingMoves ];
        validMoves( allMoves ) = Bpos( F( allMoves ) ) & Bzero( T( allMoves ) ) & Bpos( M( allMoves ) );
    h = find( validMoves );
end
    v0 = cumsum( v0 );
    [v,t] = max( v0 );
        moves = moves( 1:t, : );
end
function [moves,v] = subsoltweak(board,F,T,M,pegCount,TT,MM,MV,MVV,moveid1,moveid2,moveid3)
    moves = zeros( pegCount - 1, 4 );
    v0 = zeros( pegCount - 1, 1 );
        Bzero = ~board;
        Bpos = board>0;
        Bmax = max( board, 0 );
            hs = (Bpos( F ) & Bzero( T ) & Bpos( M ));
        h = find( hs );
                C0 = board( M( h ) ) - board( F( h ) );
        [CV,kc] = max( Bmax( MM( h, : ) ) .* Bzero( TT( h, : ) ), [  ], 2 );
        [v,k] = max( C0 + CV );
    v0( 1 ) = C0( k );
                k = h( k );
    moves( 1, : ) = MV( k, : );
            F0 = F( k );
    t = 2;
        T0 = T( k );
            FF = [ F0, M( k ), T0 ];
            M0 = M( k );
            Bmax( T0 ) = board( F0 );
            Bmax( F0 ) = 0;
            Bmax( M0 ) = 0;
            board( T0 ) = board( F0 );
            Bzero( T0 ) = false;
            Bpos( T0 ) = true;
            board( F0 ) = 0;
            Bzero( F0 ) = true;
            Bpos( F0 ) = false;
            board( M0 ) = 0;
            Bpos( M0 ) = false;
            Bzero( M0 ) = true;
        originatingMoves = moveid1( FF, : );
        originatingMoves = originatingMoves( originatingMoves>0 );
        jumpedMoves = moveid2( FF, : );
        jumpedMoves = jumpedMoves( jumpedMoves>0 );
        terminatingMoves = moveid3( FF, : );
        terminatingMoves = terminatingMoves( terminatingMoves>0 );
        allMoves = [ originatingMoves; jumpedMoves; terminatingMoves ];
        hs( allMoves ) = Bpos( F( allMoves ) ) & Bzero( T( allMoves ) ) & Bpos( M( allMoves ) );
        h = find( hs );
    while ~isempty( h )
                c = find( F( h )==T0 );
            if ~isempty( c )
                h = h( c );
                C0 = board( M( h ) );
    else
                C0 = board( M( h ) ) - board( F( h ) );
end
        [CV,kc] = max( Bmax( MM( h, : ) ) .* Bzero( TT( h, : ) ), [  ], 2 );
        [v,k] = max( C0 + CV );
                v0( t ) = C0( k );
        cv = CV( k );
        kc = kc( k );
                k = h( k );
            moves( t, : ) = MV( k, : );
            F0 = F( k );
        t = t + 1;
        if ~cv
        T0 = T( k );
            FF = [ F0, M( k ), T0 ];
    else
            T0 = TT( k, kc );
            M0 = MM( k, kc );
            moves( t, : ) = MVV{ kc }( k, : );
            FF = [ F0, M( k ), M0, T0 ];
            v0( t ) = cv;
            board( M0 ) = 0;
            Bzero( M0 ) = true;
            Bpos( M0 ) = false;
            Bmax( M0 ) = 0;
        t = t + 1;
end
            M0 = M( k );
            Bmax( T0 ) = board( F0 );
            Bmax( F0 ) = 0;
            Bmax( M0 ) = 0;
            board( T0 ) = board( F0 );
            Bzero( T0 ) = false;
            Bpos( T0 ) = true;
            board( F0 ) = 0;
            Bzero( F0 ) = true;
            Bpos( F0 ) = false;
            board( M0 ) = 0;
            Bpos( M0 ) = false;
            Bzero( M0 ) = true;
        originatingMoves = moveid1( FF, : );
        originatingMoves = originatingMoves( originatingMoves>0 );
        jumpedMoves = moveid2( FF, : );
        jumpedMoves = jumpedMoves( jumpedMoves>0 );
        terminatingMoves = moveid3( FF, : );
        terminatingMoves = terminatingMoves( terminatingMoves>0 );
        allMoves = [ originatingMoves; jumpedMoves; terminatingMoves ];
        hs( allMoves ) = Bpos( F( allMoves ) ) & Bzero( T( allMoves ) ) & Bpos( M( allMoves ) );
        h = find( hs );
end
    vv0 = cumsum( v0 );
    [v,t] = max( vv0 );
        moves = moves( 1:t, : );
end

Contact us