Asymmetrical KOTH: Catch the Cat (Cat Thread)

Question

UPDATE: The gist-files are updated (including new submissions) as the Controller.java did not catch Exceptions (only errors). It does now catch errors and exceptions and also prints them.

This challenge consists of two threads, this is the cat thread, the catcher thread can be found here.

The controller can be downloaded here.

This is an asymmetrical KOTH: Each submission is either a cat or a catcher. There are games between each pair of each a cat and a catcher. The cats and the catchers have separate rankings.

Catcher

There is a cat on a hexagonal grid. Your task is to catch it as fast as possible. Every turn, you can place a water bucket on one grid cell in order to prevent the cat from being able to go there. But the cat is not (perhaps) that dumb, and whenever you place a bucket, the cat will move to another grid cell. Since the grid is hexagonal, the cat can go in 6 different directions. Your goal is to surround the cat with water buckets, the faster the better.

Cat

You know the catcher wants to catch you by placing water buckets around you. Of course you try to evade, but as you are a lazy cat (as cats are) you exactly take one step at the time. This means you cannot stay on the same place you, but you have to move to one of the six surrounding spots. Whenever you see that the catcher placed a new water bucket you go to another cell. Of course you try to evade as long as possible.

Grid

The grid is hexagonal, but as we do not have hexagonal data structures, we take a 11 x 11 square 2d array and mimic the hexagonal 'behavior' that the cat can only move in 6 directions:

The topology is toroidal, that means if you step on a cell 'outside' of the array, you will just be transferred to the corresponding cell on the other side of the array.

Game

The cat starts out at given position in the grid. The catcher can do the first move, then the cat and its catcher alternate moves until the cat is caught. The number of steps is the score for that game. The cat tries to get a score as great as possible, the catcher tries to get a score as low as possible. The average sum over all the games you participated in will be the score of your submission. There are two separate rankings, one for the cat, one for the catchers.

Controller

The given controller is written in Java. As a catcher or a cat you each have to each complete implement a Java class (there are already some primitive examples) and place it in the players package (and update the list of cats/catchers in the Controller class), but you also may write additional functions within that class. The controller comes with each two working examples of simple cats/catcher classes.

The field is a 11 x 11 2D- int array that stores the values of the current states of the cells. If a cell is empty, it has value 0, if there is a cat it has value -1 and if there is a bucket there is a 1.

There are a few given functions you can use: isValidMove()/isValidPosition() are for checking whether your move (cat) / position (catcher) is valid.

Each time it is your turn, your function takeTurn() is called. The argument contains the a copy of the current grid an has methods like read(i,j) for reading the cell at (i,j), as well as isValidMove()/ isValidPosition() that checks the validity of your answer. This also manages the wrapping over of the toroidal topology, that means even if the grid is only 11 x 11, you still can access the cell (-5,13).

The method should return a int array of two elements, which represent possible moves. For the cats these are {-1,1},{0,1},{-1,0},{1,0},{0,-1},{1,-1} which represent the relative position of where the cat wants to go, and the catchers return the absolute coordinates of where they want to place a bucket {i,j}.

If your method produces an invalid move, your submission will be disqualified. The move is considered as invalid, if at your destination is already a bucket or the move is not allowed / destination already occupied (as a cat), or if there is already a bucket/cat (as a catcher). You can check that before hand with the given functions.

Your submission should work reasonably fast. If your method takes longer than 200ms for each step it will also be disqualified. (Preferably much less...)

The programs are allowed to store information between the steps.

Submissions

• You can make as many submissions as you want.
• Please do not significantly alter submissions you've already submitted.
• Please each submissions in a new answer.
• Each submission should preferably have it's unique name.
• The submission should consist of the code of your class as well as a description that tells us how your submission works.
• You can write the line <!-- language: lang-java --> before your source code in order to get automatic syntax highlighting.

Scoring

All cats will compete against all catchers the same number of times. I'll try to update the current scores frequently, the winners will be determined when the activity has decreased.

This challenge is inspired by this old flash game

Thanks @PhiNotPi for testing and giving some constructive feedback.

Current Scores (100 Games per pairing)

Name (Catcher)	Score	Rank	Author
RandCatcher	191962	8	flawr
StupidFill	212688	9	flawr
Achilles	77214	6	The E
Agamemnon	74896	5	The E
CloseCatcher	54776	4	randomra
ForwordCatcher	93814	7	MegaTom
Dijkstra	47558	2	TheNumberOne
HexCatcher	48644	3	randomra
ChoiceCatcher	43834	1	randomra

Name (Cat)	Score	Rank	Author
RandCat	77490	9	flawr
StupidRightCat	81566	6	flawr
SpiralCat	93384	5	CoolGuy
StraightCat	80930	7	CoolGuy
FreeCat	106294	3	randomra
RabidCat	78616	8	cain
Dijkstra's Cat	115094	1	TheNumberOne
MaxCat	98400	4	Manu
ChoiceCat	113612	2	randomra

Answer 1

FreeCat

Chooses the move which would give it the most possible paths after 3 steps if the field wouldn't change.

FreeCat vs Achilles:

package players;
/**
 * @author randomra
 */

import java.util.Arrays;

import main.Field;

public class FreeCat implements Cat {

    final int[][] turns = { { -1, 1 }, { 0, 1 }, { -1, 0 }, { 1, 0 },
            { 0, -1 }, { 1, -1 } };// all valid moves
    final int turnCheck = 3;

    public String getName() {
        return "FreeCat";
    }

    public int[] takeTurn(Field f) {

        int[] pos = f.findCat();
        int[] bestMove = { 0, 1 };
        int bestMoveCount = -1;
        for (int[] t : turns) {
            int[] currPos = { pos[0] + t[0], pos[1] + t[1] };
            int moveCount = free_count(currPos, turnCheck, f);
            if (moveCount > bestMoveCount) {
                bestMoveCount = moveCount;
                bestMove = t;
            }
        }
        return bestMove;
    }

    private int free_count(int[] pos, int turnsLeft, Field f) {
        if (f.isValidPosition(pos) || Arrays.equals(pos, f.findCat())) {
            if (turnsLeft == 0) {
                return 1;
            }
            int routeCount = 0;
            for (int[] t : turns) {
                int[] currPos = { pos[0] + t[0], pos[1] + t[1] };
                int moveCount = free_count(currPos, turnsLeft - 1, f);
                routeCount += moveCount;
            }
            return routeCount;
        }
        return 0;
    }
}

Answer 2

Dijkstra's Cat

He learned and applies his master's master algorithm. Note that he is dependent on some of the methods in his corresponding catcher's class.

Dijkstra's Cat vs Hexcatcher(needs updated):

package players;

import main.Field;
import players.Dijkstra; //Not needed import. Should already be available.

/**
 * @author TheNumberOne
 *
 * Escapes from the catcher.
 * Uses Dijkstras methods.
 */

public class DijkstrasCat implements Cat{

    private static final int[][] possibleMoves = {{-1,1},{0,1},{-1,0},{1,0},{0,-1},{1,-1}};
    @Override
    public String getName() {
        return "Dijkstra's Cat";
    }

    @Override
    public int[] takeTurn(Field f) {
        int[] me = f.findCat();
        int[] bestMove = {-1,1};
        int bestOpenness = Integer.MAX_VALUE;
        for (int[] move : possibleMoves){
            int[] newPos = Dijkstra.normalize(new int[]{me[0]+move[0],me[1]+move[1]});
            if (!f.isValidMove(move)){
                continue;
            }
            int openness = Dijkstra.openness(newPos, f, true)[1];
            if (openness < bestOpenness || (openness == bestOpenness && Math.random() < .5)){
                bestOpenness = openness;
                bestMove = move;
            }
        }
        return bestMove;
    }
}

How he works:

He tries to find the move that minimizes the stringiness of the board in relation to himself. For more information, see the corresponding catcher's post.

With update:

He now avoids the strange geometric shapes that the water buckets sometimes form.

Answer 3

MaxCat

I tried implementing the Minimax algorithm. However, it doesn't perform very well because of the limited time. Edit: It now uses multithreading, but (atleast on my computer) I can't set the depth any higher. Otherwise a timeout occurs. Using a PC with 6 or more cores, this submission would be much better :)

MaxCat vs Dijkstra:

package players;

import java.util.ArrayList;
import java.util.List;

import main.Field;

public class MaxCat implements Cat {
    final int[][] turns = { { -1, 1 }, { 0, 1 }, { -1, 0 }, { 1, 0 }, { 0, -1 }, { 1, -1 } };

    public String getName() {
        return "MaxCat";
    }

    public int[] takeTurn(Field f) {
        List<CatThread> threads = new ArrayList<>();
        int[] pos = f.findCat();
        for (int[] turn : turns) {
            if(f.read(pos[0]+turn[0], pos[1]+turn[1]) == Field.EMPTY){
                CatThread thread = new CatThread();
                thread.bestMove = turn;
                thread.field = new Field(f);
                thread.start();
                threads.add(thread);
            }
        }
        for (CatThread thread : threads) {
            try {
                thread.join();
            } catch (InterruptedException e) {}
        }
        int best = Integer.MIN_VALUE;
        int[] bestMove = { -1, 1 };
        for (CatThread thread : threads) {
            if (thread.score > best) {
                best = thread.score;
                bestMove = thread.bestMove;
            }
        }
        return bestMove;
    }
    
    class CatThread extends Thread {
        private Field field;
        private int[] bestMove;
        private int score;
        private final int DEPTH = 3;
        
        @Override
        public void run() {
            score = max(DEPTH, Integer.MIN_VALUE, Integer.MAX_VALUE);       
        }
        
        int max(int depth, int alpha, int beta) {
            int pos[] = field.findCat();
            if (depth == 0 || field.isFinished()) {
                int moveCount = 0;
                for (int[] turn : turns) {
                    if(field.read(pos[0]+turn[0], pos[1]+turn[1]) == Field.EMPTY)
                        moveCount++;
                }
                return DEPTH-depth + moveCount;
            }
            int maxValue = alpha;
            for (int[] turn : turns) {
                if(field.read(pos[0]+turn[0], pos[1]+turn[1]) == Field.EMPTY) {
                    field.executeMove(turn);
                    int value = min(depth-1, maxValue, beta);
                    field.executeMove(new int[]{-turn[0], -turn[1]});
                    if (value > maxValue) {
                        maxValue = value;
                        if (maxValue >= beta)
                            break;
                    }
                }
            }
            return maxValue;
        }
        
        int min(int depth, int alpha, int beta) {
            if (depth == 0 || field.isFinished()) {
                int moveCount = 0;
                for (int[] turn : turns) {
                    int pos[] = field.findCat();
                    if(field.read(pos[0]+turn[0], pos[1]+turn[1]) == Field.EMPTY)
                        moveCount++;
                }   
                return -depth - moveCount;
            }
            int[][] f = field.field;
            int minValue = beta;
            List<int[]> moves = generateBucketMoves();
            for (int[] move : moves) {
                f[move[0]][move[1]] = Field.BUCKET;
                int value = max(depth-1, alpha, minValue);
                f[move[0]][move[1]] = Field.EMPTY;
                if (value < minValue) {
                    minValue = value;
                    if (minValue <= alpha)
                        break;
                }
            }
            return minValue;
        }
        
        private List<int[]> generateBucketMoves() {
            int[][] f = field.field;
            List<int[]> list = new ArrayList<>();
            for (int i = 0; i < f.length; i++) {
                for (int j = 0; j < f[i].length; j++) {
                    if (f[i][j] == Field.EMPTY) {
                        list.add(new int[]{i,j});
                    }
                }
            }
            return list;
        }
    }
}

Answer 4

SpiralCat

Moves in a spiral way. It

• Tries to move to the top-left circle
• If not possible, tries to move to the top right circle
• If not possible, tries to move to the right circle
• If not possible, tries to move to the bottom right circle
• If not possible, tries to move to the bottom left circle

SpiralCat vs Agamemnon:

package players;
/**
 * @author Cool Guy
 */

import main.Field;

public class SpiralCat implements Cat{
    public String getName(){
        return "SpiralCat";
    }
    public int[] takeTurn(Field f){
        int[][] turns = {{-1,1},{0,1},{1,0},{1,-1},{0,-1},{-1,0}};//all valid moves
        int[] move;
        int i = -1;
        do {
            i++;
            move = turns[i];
        } while(f.isValidMove(move) == false);
        return move;
    }
}

Answer 5

RabidCat

RabidCat has hydrophobia, so he is afraid of the water buckets. He finds the nearest one and runs in the opposite direction.

RabidCat vs ForwordCatcher:

package players;

import java.util.Random;

import main.Field;

/**
* Run away from water buckets
* @author cain
*
*/

public class RabidCat implements Cat {

public RabidCat() {
}

@Override
public String getName() {
    return "RabidCat";
}

@Override
public int[] takeTurn(Field f) {
    int[][] directions = {{-1,1},{0,1},{-1,0},{1,0},{0,-1},{1,-1}};

    //where am I?
    int[] position = {0,0};
    for(int i = 0; i < 12; i++){
        for(int j = 0; j < 12; j++){
            if(f.read(i,j) == -1){
                position[0] = i;
                position[1] = j;
            }
        }
    }

    //Find the closest water
    int direction = 0;
    for(int d = 0; d < 10; d++){
        if(f.read(position[0] + d, position[1] - d) == 1 && f.isValidMove(directions[0])){
            direction = 1;
            break;
        }
        if(f.read(position[0], position[1] - d) == 1 && f.isValidMove(directions[1])){
            direction = 2;
            break;
        }
        if(f.read(position[0] + d, position[1]) == 1 && f.isValidMove(directions[2])){
            direction = 3;
            break;
        }
        if(f.read(position[0] - d, position[1]) == 1 && f.isValidMove(directions[3])){
            direction = 4;
            break;
        }
        if(f.read(position[0], position[1] + d) == 1 && f.isValidMove(directions[4])){
            direction = 5;
            break;
        }
        if(f.read(position[0] - d, position[1] + d) == 1 && f.isValidMove(directions[5])){
            direction = 6;
            break;
        }
    }

    //If there is no water near, wander
    while(direction == 0){
        Random rand = new Random();
        direction = rand.nextInt(6) + 1;
        if(!f.isValidMove(directions[direction - 1])){
            direction = 0;
        }
    }
    return directions[direction - 1];
}

}

Answer 6

ChoiceCat

For every possible new cat positions we check its goodness and choose the best one. Goodness is the function of the two best neighbour cells who are further away from the cat position than the position whose score we calculate. We use only two cells because one can be blocked and the cat only needs one more to get away. Our function prefers two fairly good cells than one great and one bad. Positions with buckets have a score of 0 and the furthest free cells have a score of 1.

ChoiceCat seems to score better than the current cats.

ChoiceCat vs ChoiceCatcher:

package players;
/**
 * @author randomra
 */
import java.util.Arrays;

import main.Field;

public class ChoiceCat implements Cat {

    private class Values {
        public final int size;
        private double[][] f;

        Values(int size) {
            this.size = size;
            f = new double[size][size];
        }

        public double read(int[] p) {
            int i = p[0];
            int j = p[1];
            i = (i % size + size) % size;
            j = (j % size + size) % size;
            return f[i][j];
        }

        private double write(int[] p, double v) {
            int i = p[0];
            int j = p[1];
            i = (i % size + size) % size;
            j = (j % size + size) % size;
            return f[i][j] = v;
        }
    }

    final int[][] turns = { { -1, 1 }, { 0, 1 }, { 1, 0 }, { 1, -1 },
            { 0, -1 }, { -1, 0 } };// all valid moves CW order
    final int stepCheck = 5;

    public String getName() {
        return "ChoiceCat";
    }

    public int[] takeTurn(Field f) {

        int[] pos = f.findCat();
        int[] bestMove = { 0, 1 };
        double bestMoveValue = -1;
        for (int[] t : turns) {
            int[] currPos = { pos[0] + t[0], pos[1] + t[1] };
            double moveValue = movePosValue(currPos, f);
            if (moveValue > bestMoveValue) {
                bestMoveValue = moveValue;
                bestMove = t;
            }
        }
        return bestMove;
    }

    private double movePosValue(int[] pos, Field f) {

        Values v = new Values(f.SIZE);

        for (int ring = stepCheck; ring >= 0; ring--) {
            for (int phase = 0; phase < 2; phase++) {
                for (int sidepos = 0; sidepos < Math.max(1, ring); sidepos++) {
                    for (int side = 0; side < 6; side++) {
                        int[] evalPos = new int[2];
                        for (int coord = 0; coord < 2; coord++) {
                            evalPos[coord] = pos[coord] + turns[side][coord]
                                    * sidepos + turns[(side + 1) % 6][coord]
                                    * (ring - sidepos);
                        }
                        if (phase == 0) {
                            if (ring == stepCheck) {
                                // on outmost ring, init value
                                v.write(evalPos, -1);
                            } else {
                                v.write(evalPos, posValue(evalPos, v, f));
                            }
                        } else {
                            // finalize position value for next turn
                            v.write(evalPos, -v.read(evalPos));
                        }
                    }
                }
            }
        }

        return -v.read(pos);
    }

    private double posValue(int[] pos, Values v, Field f) {
        if (f.read(pos[0], pos[1]) == Field.BUCKET) {
            return 0;
        }
        int count = 0;
        double[] product = new double[6];
        for (int[] t : turns) {
            int[] tPos = new int[] { pos[0] + t[0], pos[1] + t[1] };
            if (v.read(tPos) > 0) {
                product[count] = 1 - 1 / (v.read(tPos) + 1);
                count++;
            }
        }
        Arrays.sort(product);
        double fp = 1;
        for (int i = 0; i < Math.min(count,2); i++) {
            fp *= product[5-i];
        }
        double retValue = Math.min(count,2) + fp;
        return -retValue;
    }
}

Answer 7

StupidRightCat

This was made just for testing the controller. The cat move right whenever possible, otherwise moves in a random direction.

package players;

import main.Field;

public class StupidRightCat implements Cat{
    public String getName(){
        return "StupidRightCat";
    }
    public int[] takeTurn(Field f){
        int[][] turns = {{-1,1},{0,1},{-1,0},{1,0},{0,-1},{1,-1}};//all valid moves
        int[] move;
        
        if(f.isValidMove(turns[3])){
            return turns[3];
        } else {
            do {
                move = turns[(int) (turns.length * Math.random())];
            } while(f.isValidMove(move)==false);
            return move;//chose one at random
        }
    }
}

Answer 8

RandCat

This was made just for testing the controller. The cat just moves randomly.

package players;

import main.Field;

public class RandCat implements Cat{
    public String getName(){
        return "RandCat";
    }
    public int[] takeTurn(Field f){
        int[][] turns = {{-1,1},{0,1},{-1,0},{1,0},{0,-1},{1,-1}};//all valid moves
        int[] move;
        do {
            move = turns[(int) (turns.length * Math.random())];
        } while(f.isValidMove(move)==false);
        return move;//chose one at random
    }
}

Answer 9

StraightCat

This cat moves straight.

At the start, it chooses a random direction and keeps moving in this direction until it cannot in which case, it shifts the direction in a clockwise manner to the next valid direction and repeats this process.

StraightCat vs Agamemnon:

package players;
/**
 * @author Cool Guy
 */

import main.Field;

public class StraightCat implements Cat{

    int lastDirection = -1; //Holds the last direction the cat moved
    public String getName(){
        return "StraightCat";
    }
    public int[] takeTurn(Field f){
        int[][] turns = {{-1,1},{0,1},{1,0},{1,-1},{0,-1},{-1,0}};//all valid moves

        if(lastDirection == -1)
          lastDirection = (int) (turns.length * Math.random());

        int[] move = turns[lastDirection];
        int i = lastDirection;

        while(true)
        {
            if(f.isValidMove(move))
                break;
            i = (i+1)%6;
            lastDirection = i;
            move = turns[i];
        }
        return move;
    }
}