Q:

Slime: The Territory War

You are a glob of slime. Naturally, being slime, you want to ooze over as much area as possible. But there are 3 other slimes who want to do the exact same thing. Who will be the superior slime?
Description
All slimes will be gathered into one arena. The judges (i.e. the control program) will go through an exhaustive list of all possible 4-slime combinations, place them on the corners of a table, and observe to see which slime oozes out over the most area.
Your slimes can do one of 3 actions each turn: spread out, jump, or merge. Further description on what these mean will be provided in the Output section.
Board / Arena
The arena will be a square board (currently 8x8, but this may change in the future). Here is an example arena of a game in progress:
11111222
11111444
11.22444
.1222.4.
333.3244
33333.44
333...44
333....4

Slime is represented by the numbers 1 through 4 (players 1 to 4), and empty space is represented by a dot (.). Initially, the board starts out as all empty space except for a single unit of player 1's slime in the top left corner, player 2 in the top right, player 3 in the bottom left, and player 4 in the bottom right.
Coordinates are represented by 0-based row and column index, for readability in the code. For example, the coordinates (3, 6) represent the 7th square in the 4th row (in the above example, a 4). (This makes it easier to access squares: board[coords.x][coords.y].) Here's a visual illustration:
(0, 0) (0, 1) (0, 2)
(1, 0) (1, 1) (1, 2)
(2, 0) (2, 1) (2, 2)

Input
Your program's input will be which player you are (1, 2, 3, or 4), a comma (,), then the content of the board / arena (with newlines replaced with commas). For example, if you were player 3 in the above scenario, your input would be:
3,11111222,11111444,11.22444,.1222.4.,333.3244,33333.44,333...44,333....4

Output
Your program must output 4 integers. The first two are the row and column index respectively of the slime you would like to move, and the next two are the row and column index of where you want to move them.
There are three choices you have on each turn: Spread out, jump, or merge.

Spread
To spread, the target coordinates must be exactly one square away from the slime being moved, and the square at the target coordinates must be empty space. When spreading, a new slime is created at the target coordinates and the old slime is not removed. After the new slime is created, all enemy slimes in the 8 squares around this new slime are converted to the player that moved.
For example, with the board in Fig. 1, if player 1 were to output 0 1 1 2, the result would be the board in Fig. 2.
1.         2.
  11.22      11.12
  1..22      1.112
  ..22.      ..11.
  .....      .....

Jump
To jump, the target coordinates must be exactly two squares away from the slime being moved, and the square at the target coordinates must be empty space. When jupming, a new slime is created at the target coordinates and the old slime is removed. After the new slime is created, all enemy slimes in the 8 squares around this new slime are converted to the player that moved.
For example, with the board in Fig. 1, if player 1 were to output 0 1 2 3, the result would be the board in Fig. 2.
1.         2.    
  11..2      1...2
  1...2      1...1
  ....2      ...11
  ...22      ...11

Merge
To merge, the target coordinates must be exactly one square away from the slime being moved, and the square at the target coordinates must be the same player's slime. When merging, the old slime is removed. Then, all empty spaces in the 8 squares around the target slime are converted to the player that moved (not including the old slime being moved).
For example, with the board in Fig. 1, if player 1 were to output 0 1 1 2, the result would be the board in Fig. 2.
1.         2.
  11..2      1.112
  1.1.2      11112
  ....2      .1112
  ..222      ..222

You can also pass, by simply outputting invalid coordinates (ex. 0 0 0 0).
Rules and constraints
Additional rules are:

You may read and write files within your own folder in order to persist data (submissions will be stored in players/YourBotName/yourBotName.language), but you may not modify or access anything else outside of it. Internet access is prohibited.
Your submission may not be coded specifically to help or hurt another submission. (You may have multiple submissions, but they must not specifically interact with each other in any way.)
Your submission must take no more than 0.1 seconds per turn. If your submission takes 0.105 seconds occasionally, that's fine, but it may not consistently take significantly longer than this time limit. (This is mainly a sanity check to avoid testing taking an overly long time.)
Your submission must not be an exact duplicate (i.e. use the exact same logic) of another, even if it's in a different language.
Your submission must be a serious submission. This is opinion-based, but if your submission is clearly not attempting to solve the challenge (ex. if you pass every turn), it will be disqualified.

If your submission breaks any of these rules or doesn't follow the specification, it will be disqualified, removed from playerlist.txt, and the game will restart from the beginning. If your submission is disqualified, I will leave a comment on your post explaining why. Otherwise, your submission will be added to the leaderboard. (If you don't see your submission on the leaderboard, have no explanatory comment on your post, and posted your submission before the "Last updated" time below, please tell me! I may have inadvertently overlooked it.)
In your entry, please include:

A name.
A shell command to run your program (for example, java MyBot.java, ruby MyBot.rb, python3 MyBot.py, etc.).

Note that the input (your player and map) will be appended to this as a command line argument.
Programs will be tested on Ubuntu 14.04, so make sure your code can be run (freely) on it.

A version number, if your code works differently on different versions of your language.
Your bot's code.
Instructions on how to compile the code, if necessary.

Controller code / testing, example bot
The controller code is written in C++, and can be found on Github. Further instructions on how to run and test your code can be found there.
simplebot.rb, a very simple bot that spreads or jumps a random slime to a random location each turn, is also posted on Github.
Scoring and leaderboard
When all squares on the board are filled, the game ends and scores are calculated. The final score of a player is the amount of squares that contain their slime at the end of the game. If 2000 turns have passed (500 for each player) and the game still isn't over, the game will end anyway and the scores will be reported as if the game had ended.
At the end of the tournament, the scores from all games will averaged to calculate each player's final score, which will be posted on the leaderboard. There is no submission deadline; I'll continue to update the leaderboard periodically as new submissions come in.
4 submissions are required until a real leaderboard appears.
+--------------------------+-----------+--------------------+
| Name                     | Avg Score | Last Updated (UTC) |
+--------------------------+-----------+--------------------+
| GreedySlime              | 47.000    | Jul 22 10:27 PM    |
| Jumper                   | 12.000    | Jul 22 10:27 PM    |
| ShallowBlue              | 5.000     | Jul 22 10:27 PM    |
| Lichen                   | 0.000     | Jul 22 10:27 PM    |
+--------------------------+-----------+--------------------+

Last updated: Jul 22 10:27 PM (UTC).

A:

GreedySlime
Simply makes the move that produces the greatest net gain of slime units.
Note that this is written in Python 2.x.
def gen_moves(board, pos):
    """Generate valid moves for a given position.

    Return value is a tuple of the form
       (type, from_x, from_y, to_x, to_y)

    The move 'type' is a single character with:
        - 's' = spread
        - 'j' = jump
        - 'm' = merge
    """

    N = len(board)
    x0, y0 = pos
    player = board[x0][y0]

    for i in -2,-1,0,1,2:
        for j in -2,-1,0,1,2:
            if (i == 0 and j == 0):
                continue

            x1, y1 = x0 + i, y0 + j

            if not ((0 <= x1 < N) and (0 <= y1 < N)):
                continue

            c = board[x1][y1]

            if -1 <= i <= 1 and -1 <= j <= 1:
                if c == '.':
                    yield ('s', x0, y0, x1, y1)
                elif c == player:
                    yield ('m', x0, y0, x1, y1)
            else:
                if c == '.':
                    yield ('j', x0, y0, x1, y1)

def eval_move(board, move, initial_net={'s': 1, 'j': 0, 'm': -1}):
    """Evaluates given move in given context.

    - Assumes move is valid.
    - `move` argument is a tuple of the form
       (type, from_x, from_y, to_x, to_y)
    - The move 'type' is a single character with:
        - 's' = spread
        - 'j' = jump
        - 'm' = merge
    """

    N = len(board)
    move_type = move[0]
    x0, y0, x1, y1 = move[1:]
    player = board[x0][y0]

    net = initial_net[move_type]
    for i in -1,0,1:
        for j in -1,0,1:
            if (i == 0 and j == 0):
                continue

            x2, y2 = x1 + i, y1 + j

            if not ((0 <= x2 < N) and (0 <= y2 < N)):
                continue

            c = board[x2][y2]

            if (move_type == 'm' and c == '.') or (move_type != 'm' and c != player and c != '.'):
                net += 1

    return net

def main():
    from sys import argv
    data = argv[1]

    player, board = data.split(',', 1)
    board = map(list, board.split(','))
    N = len(board)

    all_pos_gen = ((a,b) for a in range(N) for b in range(N) if board[a][b] == player)
    all_move_gen = (move for pos in all_pos_gen for move in gen_moves(board, pos))
    move = max(all_move_gen, key=lambda move: eval_move(board, move))

    print move[1], move[2], move[3], move[4]

if __name__ == "__main__":
    main()

Example run (using the example given in the challenge description, and assuming the code is saved in a file called slime.py):
$ python slime.py 3,11111222,11111444,11.22444,.1222.4.,333.3244,33333.44,333...44,333....4
4 0 2 2

A:

Shallow Blue
Shallow blue tries to figure out what might happen in the future by doing an exhaustive tree-search of possible moves, unfortunately, he doesn't get any further than his next turn. He then slaps some half-assed score on each possible boardstate after his next turn, calculates a score for each individual branch with an equally ridiculous formula and: voila the ideal move is known!
EDIT: The original code ran waay too slowly so I modified it so that it only takes a random sample of all possible moves. It will try almost all moves when there are little moves possible and a smaller percentage when there are more moves possible.
import java.awt.Point;  
    
    public class ShallowBlue {
        private static final int MAX_ROUNDS = 5, PLAYERS = 4;
        static int me = 0;
    
        public static void main(String[] args) {
            if (args[0] == null) {
                return;
            }
    
            me = Integer.parseInt(args[0].split(",", 2)[0]);
    String board = args[0].split(",", 2)[1];

    System.out.println(getBestMove(board, me, MAX_ROUNDS - 1));
}

private static String getBestMove(String board, int player, int rounds) {
    String [] boards = new String[24];
    int checkedBoards = 1;
    char playerChar = Integer.toString(player).charAt(0);
    String tempMove = getMove(0, 0, 0, 0);
    String tempBoard = calculateMove(board, tempMove); 
    boards[0] = tempBoard;
    String bestMove = tempMove;
    double us = numberOfUs(board, playerChar); 
    double skip = (us*2.5/(us*2.5 + 1))/4 + 0.735;
    if (rounds == MAX_ROUNDS - 2) {
        skip = skip*skip;
    }

    float bestScore, worstScore, averageScore, tempScore;
    int scores;

    if (rounds == 0) {
        tempScore = calculateScore(tempBoard, MAX_ROUNDS - rounds - 1);
    } else {
        tempScore = getScore(getBestMove(tempBoard, player%PLAYERS + 1, rounds - 1));
    }

    scores = 1;
    bestScore = tempScore;
    worstScore = tempScore;
    averageScore = tempScore;

    for (int x = 0; x < 8; x++) {
        for (int y = 0; y < 8; y++) {
            if (getCharAt(board, x, y) == playerChar) {
                Point[] possibleMergers = getNeighboringMatches(board, new Point(x, y), playerChar);
                if (possibleMergers[0] != null) {
                    tempMove = getMove(possibleMergers[0].x, possibleMergers[0].y, x, y); 
                    tempBoard = calculateMove(board, tempMove);
                    if (addIfUnique(boards, tempBoard, checkedBoards)) {
                        checkedBoards++;
                        if ((rounds != MAX_ROUNDS - 1) && (rounds == 0 || Math.random() < skip)) {
                            tempScore = calculateScore(tempBoard, MAX_ROUNDS - rounds - 1);
                        } else {
                            tempScore = getScore(getBestMove(tempBoard, player%PLAYERS + 1, rounds - 1));
                        }

                        if (tempScore > bestScore) {
                            bestMove = tempMove;
                        }
                        bestScore = Math.max(tempScore, bestScore);
                        worstScore = Math.min(tempScore, worstScore);

                        scores++;
                        averageScore = (averageScore*(scores - 1) + tempScore)/scores;
                    }
                }
            } else if (getCharAt(board, x, y) == '.') {
                Point[] possibleSpreaders = getNeighboringMatches(board, new Point(x, y), playerChar);
                int i = 0;
                while (i < possibleSpreaders.length && possibleSpreaders[i] != null) {
                    tempMove = getMove(possibleSpreaders[i].x, possibleSpreaders[i].y, x, y); 
                    tempBoard = calculateMove(board, tempMove);
                    if ((rounds != MAX_ROUNDS - 1) && (rounds == 0 || Math.random() < skip)) {
                        tempScore = calculateScore(tempBoard, MAX_ROUNDS - rounds - 1);
                    } else {
                        tempScore = getScore(getBestMove(tempBoard, player%PLAYERS + 1, rounds - 1));
                    }

                    if (tempScore > bestScore) {
                        bestMove = tempMove;
                    }
                    bestScore = Math.max(tempScore, bestScore);
                    worstScore = Math.min(tempScore, worstScore);

                    scores++;
                    averageScore = (averageScore*(scores - 1) + tempScore)/scores;
                    
                    i++;
                }
                Point[] possibleJumpers = getNextNeighboringMatches(board, new Point(x, y), playerChar);
                i = 0;
                while (i < possibleJumpers.length && possibleJumpers[i] != null) {
                    tempMove = getMove(possibleJumpers[i].x, possibleJumpers[i].y, x, y); 
                    tempBoard = calculateMove(board, tempMove);
                    if ((rounds != MAX_ROUNDS - 1) && (rounds == 0 || Math.random() < skip)) {
                        tempScore = calculateScore(tempBoard, MAX_ROUNDS - rounds - 1);
                    } else {
                        tempScore = getScore(getBestMove(tempBoard, player%PLAYERS + 1, rounds - 1));
                    }

                    if (tempScore > bestScore) {
                        bestMove = tempMove;
                    }
                    bestScore = Math.max(tempScore, bestScore);
                    worstScore = Math.min(tempScore, worstScore);

                    scores++;
                    averageScore = (averageScore*(scores - 1) + tempScore)/scores;
                    
                    i++;
                }
            }
        }
    }

    if (rounds == MAX_ROUNDS - 1) {
        return (bestMove);
    } else {
        return getScoreString(bestScore, worstScore, averageScore);
    }
}

private static int numberOfUs(String board, char playerChar) {
    int us = 0;
    
    for (int i = 0; i < board.length(); i++ ) {
         if (board.charAt(i) == playerChar) {
            us++;
        }
    }
    
    return us;
}

private static float calculateScore(String board, int roundsPassed) {
    int empties = 0;
    int us = 0;
    int enemy1 = 0;
    int enemy2 = 0;
    int enemy3 = 0;
    for (int i = 0; i < board.length(); i++ ) {
        if (board.charAt(i) == '.') {
            empties++;
        } else if (board.charAt(i) == Integer.toString(me).charAt(0)) {
            us++;
        } else if (board.charAt(i) == Integer.toString(me%PLAYERS + 1).charAt(0)) {
            enemy1++;
        } else if (board.charAt(i) == Integer.toString(me%PLAYERS + 2).charAt(0)) {
            enemy2++;
        } else if (board.charAt(i) == Integer.toString(me%PLAYERS + 3).charAt(0)) {
            enemy3++;
        }
    }
    
    if (us != 0) {
        us += roundsPassed;
    }
    
    if (enemy1 != 0) { 
        enemy1 = enemy1 + (roundsPassed + 3)%PLAYERS;
    }
    
    if (enemy2 != 0) { 
        enemy2 = enemy2 + (roundsPassed + 2)%PLAYERS;
    }
    
    if (enemy3 != 0) { 
        enemy3 = enemy3 + (roundsPassed + 1)%PLAYERS;
    }

    return us*(empties + 1)/(Math.max(Math.max(enemy1, enemy2), enemy3) + 1);
}

private static float getScore(String scoreString) {
    float bestScore, worstScore, averageScore;
    String[] scores = new String[3];

    scores = scoreString.split(",");
    bestScore = Float.parseFloat(scores[0]);
    worstScore = Float.parseFloat(scores[1]);
    averageScore = Float.parseFloat(scores[2]);

    return (float) Math.sqrt(Math.sqrt(bestScore*averageScore*worstScore*worstScore));
}

private static String getScoreString(float bestScore, float worstScore, float averageScore) {
    return Float.toString(bestScore) + ',' + Float.toString(worstScore) + ',' + Float.toString(averageScore);
}

private static boolean addIfUnique(String[] boards, String board, int checkedBoards) {
    int i = 0;

    while (i < boards.length && boards[i] != null) {
        if (boards[i].equals(board)) {
            return false;
        }
        i++;
    }
    
    if (i < boards.length) {
        boards[i] = board;
    } else {
        boards[checkedBoards%boards.length] = board;
    }

    return true;
}

private static String calculateMove(String board, String move) {
    int x1 = Integer.parseInt(Character.toString(move.charAt(0)));
    int y1 = Integer.parseInt(Character.toString(move.charAt(2)));
    int x2 = Integer.parseInt(Character.toString(move.charAt(4)));
    int y2 = Integer.parseInt(Character.toString(move.charAt(6)));

    if ((Math.abs(y1 - y2) == 2 || Math.abs(x1 - x2) == 2) 
            &&  getCharAt(board, x2, y2) == '.') {
        Point[] enemies = new Point[8];

        enemies = getNeighboringEnemies(board, new Point(x1, y1), Integer.parseInt(Character.toString(getCharAt(board, x1, y1))));

        board = replace(board, enemies, getCharAt(board, x1, y1));
        Point[] middle = {new Point(x1, y1)};
        board = replace(board, middle, '.');
    }

    if ((Math.abs(y1 - y2) == 1 || Math.abs(x1 - x2) == 1)) { 
        if (getCharAt(board, x2, y2) == '.' || getCharAt(board, x1, y1) == getCharAt(board, x2, y2)) {
            boolean merge = true;
            if (getCharAt(board, x2, y2) == '.') {
                merge = false;
            }

            Point[] spaces = new Point[8];
            spaces = getNeighboringMatches(board, new Point(x1, y1), '.');
            board = replace(board, spaces, getCharAt(board, x1, y1));

            if (merge) {
                Point[] source = {new Point(x1, y1)};
                board = replace(board, source, '.');
            }
        }
    }

    return board;
}

private static String replace(String board, Point[] targets, char source) {
    int i = 0;

    while (i < targets.length && targets[i] != null) {
        if (targets[i].x == 7 && targets[i].y == 7) {
            board = board.substring(0, getIndexAt(targets[i].x, targets[i].y)) + source;
        } else if (targets[i].x == 0 && targets[i].y == 0) {
            board = source + board.substring(getIndexAt(targets[i].x, targets[i].y) + 1);
        } else {
            board = board.substring(0, getIndexAt(targets[i].x, targets[i].y)) + source + board.substring(getIndexAt(targets[i].x, targets[i].y) + 1);
        }
        i++;
    }

    return board;
}

private static Point[] getNeighboringMatches(String board, Point coord, char match) {
    Point[] matches = new Point[8];

    int i = 0;
    for (int x = coord.x - 1; x <= coord.x + 1; x++) {
        for (int y = coord.y - 1; y <= coord.y + 1; y++) {
            if ((y != coord.y || x != coord.x ) && getCharAt(board, x, y) == match){
                matches[i] = new Point(x, y);
                i++;
            }
        }
    }

    return matches;
}

private static Point[] getNeighboringEnemies(String board, Point coord, int player) {
    Point[] enemies = new Point[8];

    for (int i = 1; i <= PLAYERS; i++){
        enemies = mergeArr(enemies, getNeighboringMatches(board, coord, Integer.toString((player + i - 1)%PLAYERS + 1).charAt(0)));
    }

    return enemies;
}

private static Point[] getNextNeighboringMatches(String board, Point coord, char match) {
    Point[] matches = new Point[16];

    int i = 0;
    for (int x = coord.x - 2; x <= coord.x + 2; x++) {
        for (int y = coord.y - 2; y <= coord.y + 2; y++) {
            if ((Math.abs(y - coord.y) == 2 || Math.abs(x - coord.x) == 2) && getCharAt(board, x, y) == match){
                matches[i] = new Point(x, y);
                i++;
            }
        }
    }

    return matches;
}

private static char getCharAt(String board, int x, int y) {

    if (x >= 0 && x < 8 && y >= 0 && y < 8) {
        return board.charAt(9*x + y);
    } else {
        return '\0';
    }
}

private static int getIndexAt(int x, int y) {
    return 9*x + y;
}

private static Point[] mergeArr(Point[] arr1, Point[] arr2) {
    int i = 0;
    int j = 0;

    while (i < arr1.length && arr1[i] != null) {
        i++;
    }

    while (j < arr2.length && arr2[j] != null) {
        arr1[i + j] = arr2[j];
        j++;
    }

    return arr1;
}

private static String getMove(int x1, int y1, int x2, int y2) {
    return Integer.toString(x1) + " " + Integer.toString(y1) + " " + Integer.toString(x2) + " " + Integer.toString(y2);
    }
}

