17
\$\begingroup\$

Asymmetrical KOTH: Catch the Cat

UPDATE: The gist-files are updated (including new submisisons) 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 catcher thread, the cat 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 seperate 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:

enter image description here

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 --> befor your sourcecode 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              Score      Rank   Author

RandCatcher       191674     8      flawr   
StupidFill        214246     9      flawr
Achilles          76820      6      The E
Agamemnon         74844      5      The E
CloseCatcher      54920      4      randomra
ForwordCatcher    94246      7      MegaTom  
Dijkstra          46500      2      TheNumberOne
HexCatcher        48832      3      randomra
ChoiceCatcher     43828      1      randomra

RandCat           77928      7      flawr
StupidRightCat    81794      6      flawr
SpiralCat         93868      5      CoolGuy
StraightCat       82452      9      CoolGuy
FreeCat           106304     3      randomra
RabidCat          77770      8      cain
Dijkstra's Cat    114670     1      TheNumberOne
MaxCat            97768      4      Manu
ChoiceCat         113356     2      randomra
\$\endgroup\$
  • \$\begingroup\$ What program makes the animations? \$\endgroup\$ – MegaTom Jun 2 '15 at 13:41
  • \$\begingroup\$ The animation is just the GUI (when starting the controller you have to set PRINT_STEPS = true , more detailed settings in the file MyFrame.java). Then I recorded this with LICEcap and edited it with GIMP. If you have further questions just ask! \$\endgroup\$ – flawr Jun 2 '15 at 14:12
  • \$\begingroup\$ If you add user input to the controller, it could make a nice software with the GUI and the bots already written. It would be also interesting to see how much can humans crack/abuse the specific bot strategies. \$\endgroup\$ – randomra Jun 4 '15 at 4:54
  • \$\begingroup\$ Also, can my bot keep information from the previous match to try to find a better move-sequence against the same bot? I suppose not because it gets better the more rounds you do. It would also have to guess if it is playing against a new bot, so the running order would matter too. \$\endgroup\$ – randomra Jun 4 '15 at 4:58
  • 1
    \$\begingroup\$ Why is the scores of the cats un-ordered? \$\endgroup\$ – Spikatrix Jun 5 '15 at 5:54
6
\$\begingroup\$

Achilles

Achilles isn't too bright but he is ruthlessly efficient. First he stops the cat from using the wrap around of the board, then he divides the board into two. Then he keeps on dividing the part of the board the cat is in into half until the cat is trapped.

Demonstration RandCat vs Achilles

randcat vs achilles

package players;
/**
 * @author The E
 */
import main.*;



public class Achilles implements Catcher
{
    public Achilles() {

    }
    @Override
    public String getName() {

        return "Achilles";
    }

    @Override
    public int[] takeTurn(Field f) {
        try{
        if(f.read(0, f.SIZE-1)!=Field.BUCKET)
        {
            //Make the first line

            for(int j = 0; j<f.SIZE; j++)
            {
                if(f.read(0, j) == Field.EMPTY)
                {
                    return new int[]{0,j};
                }
            }
            return WasteGo(f);

        }
        else if (f.read(f.SIZE-1, 0)!=Field.BUCKET)
        {
            //Make the second line
            for(int i = 0; i<f.SIZE; i++)
            {
                if(f.read(i, 0) == Field.EMPTY)
                {
                    return new int[]{i,0};
                }
            }
            //The cat got in the way
            for(int j = 0; j<f.SIZE; j++)
            {
                if(f.read(1, j) == Field.EMPTY)
                {
                    return new int[]{1,j};
                }
            }
            return WasteGo(f);
        }
        else
        {
            return TrapCat(1,1,f.SIZE-1, f.SIZE-1, false, f);

        }
        }
        catch (Exception e)
        {
            return WasteGo(f);
        }
    }
    private int[] TrapCat(int i1, int j1, int i2, int j2, Boolean direction, Field f) {
        for(int a = 0; a<f.SIZE+10; a++)
        {
            if(direction)
            {

                int height = j2-j1+1;
                int row = j1 + height/2;
                for(int i = i1; i<=i2; i++)
                {
                    if(f.read(i, row)==Field.EMPTY)
                    {
                        return new int[]{i,row};
                    }
                }

                    //Done that Row
                    //Find cat
                    if(f.findCat()[1]>row)
                    {
                        //he's above the line
                        j1 = row+1;
                        direction = !direction;
                        //return TrapCat(i1, row+1, i2, j2, !direction, f);
                    }
                    else
                    {
                        //he's below the line
                        j2 = row - 1;
                        direction = !direction;
                        //return TrapCat(i1, j1, i2, row-1, !direction, f);
                    }


            }
            else
            {
                int bredth = i2-i1+1;
                int column = i1 + bredth/2;
                //Continue making the line
                for(int j = j1; j<=j2; j++)
                {
                    if(f.read(column,j)==Field.EMPTY)
                    {
                        return new int[]{column,j};
                    }
                }

                    //Done that Column
                    //Find cat
                    if(f.findCat()[0]>column)
                    {
                        //he's right of the line
                        i1 = column + 1;
                        direction = !direction;
                        //return TrapCat(column+1, j1, i2, j2, !direction, f);
                    }
                    else
                    {
                        //he's left of the line
                        i2 = column -1;
                        direction = !direction;
                        //return TrapCat(i1, j1, column-1, j2, !direction, f);
                    }

            }
        }
        return WasteGo(f);
    }
    private int[] WasteGo(Field f) {
        for (int i = 0; i<f.SIZE;i++)
        {
            for(int j=0;j<f.SIZE;j++)
            {
                if(f.read(i,j)==Field.EMPTY)
                {
                    return new int[]{i,j};
                }
            }
        }
        //Something drastic happened
        return new int[]{0,0};
    }



}
\$\endgroup\$
  • \$\begingroup\$ Well which one is it now, Achilles or Hector? (Or someone with a dissiociative identity disorder?=) \$\endgroup\$ – flawr May 30 '15 at 19:25
  • \$\begingroup\$ @flawr Achilles, lol I changed the name half way through (it's more apt to name the catcher Achilles and the cat Hector) but forgot to change the java - it's what happens when you program after tea :( \$\endgroup\$ – euanjt May 30 '15 at 19:32
  • \$\begingroup\$ But Hector would rather be a dogs name=) Thanks for your submission works great. I hope you do not mind that I also include the 'preamble' in your code. \$\endgroup\$ – flawr May 30 '15 at 19:40
  • \$\begingroup\$ Yeah no problem. Hector does sound like a dogs name... \$\endgroup\$ – euanjt May 30 '15 at 19:47
  • \$\begingroup\$ I just ran a simulation (10000 games for each pairing) and Achilles was disqualified, due to repeated StackOverflowError. I think the recursion did not end: pastebin.com/9n6SQQnd \$\endgroup\$ – flawr Jun 1 '15 at 11:31
5
\$\begingroup\$

Agamemnon

Agamemnon splits the cats area in half with a vertical line until the cat only has a strip of width 2 to move in, at which point he traps the cat.

Agamemnon vs RandCat:

enter image description here

package players;
/**
 * @author The E
 */
import main.*;



    public class Agamemnon implements Catcher {
        boolean up = true;
        @Override
        public String getName() {
            return "Agamemnon";
        }

        @Override
        public int[] takeTurn(Field f) {
            //First Make Line in column 1
            for(int j = 0; j<f.SIZE; j++)
            {
                if(f.read(0, j)==Field.EMPTY)
                {
                    return new int[]{0,j};
                }
            }
            //Then in column SIZE/2
            for(int j = 0; j<f.SIZE; j++)
            {
                if(f.read(f.SIZE/2, j)==Field.EMPTY)
                {
                    return new int[]{f.SIZE/2,j};
                }
            }
            //Then work out where the cat is
            int left, right;
            int cati = f.findCat()[0];
            if(cati<f.SIZE/2)
            {
                left = 1;
                right = f.SIZE/2-1;
            }
            else
            {
                left = f.SIZE/2+1;
                right = f.SIZE-1;
            }
            while(right-left>1)
            {
                //If the cat is not in a two width column
                //Split the area the cat is in in half
                int middleColumn = (left+right)/2;
                for(int j = 0; j<f.SIZE; j++)
                {
                    if(f.read(middleColumn, j)==Field.EMPTY)
                    {
                        return new int[]{middleColumn,j};
                    }
                }
                //If we got here we had finished that column
                //So update left and/or right
                if(cati<middleColumn)
                {
                    //he's left of the middle Column
                    right = middleColumn - 1;
                }
                else
                {
                    //he's right of the middle Column
                    left = middleColumn+1;
                }
                //Repeat
            }
            //Otherwise try to trap the cat
            //Make a line up and down on the opposite side of the cat
            int catj = f.findCat()[1];
            if(left!=right){
                if(cati==left)
                {
                    if(f.read(right, catj)==Field.EMPTY)
                    {
                        return new int[]{right, catj};
                    }
                    if(f.read(right, catj-1)==Field.EMPTY)
                    {
                        return new int[]{right, catj-1};
                    }
                    if(f.read(right, catj+1)==Field.EMPTY)
                    {
                        return new int[]{right, catj+1};
                    }


                }
                else
                {
                    if(f.read(left, catj)==Field.EMPTY)
                    {
                        return new int[]{left, catj};
                    }
                    if(f.read(left, catj-1)==Field.EMPTY)
                    {
                        return new int[]{left, catj-1};
                    }
                    if(f.read(left, catj+1)==Field.EMPTY)
                    {
                        return new int[]{left, catj+1};
                    }

                }
            }
            //Alternate between above and below
            if(up)
            {
                up = !up;
                if(f.read(cati, catj+1)==Field.EMPTY)
                {

                    return new int[]{cati, catj+1};
                }
            }
            up = !up;
            if(f.read(cati, catj-1)==Field.EMPTY)
            {

                return new int[]{cati, catj-1};
            }
            return WasteGo(f);
        }

        private int[] WasteGo(Field f) {
            for (int i = 0; i<f.SIZE;i++)
            {
                for(int j=0;j<f.SIZE;j++)
                {
                    if(f.read(i,j)==Field.EMPTY)
                    {
                        return new int[]{i,j};
                    }
                }
            }
            //Something drastic happened
            return new int[]{0,0};
        }
    }

This catcher does consistently better than Achilles and I think he's different enough to warrant a new answer.

\$\endgroup\$
  • \$\begingroup\$ Very nice solution, I was sure Achilles was close to optimal, but now I think even Agamemnon could be improved slightly=) \$\endgroup\$ – flawr May 31 '15 at 12:06
  • \$\begingroup\$ Yes, Agamemnon has a much better end game trapping algorithm than Achilles, but I'm pretty sure there are some tweaks... Now I'll try and work on a cat :) \$\endgroup\$ – euanjt May 31 '15 at 12:39
  • \$\begingroup\$ @flawr very tiny tweak added to speed up catching in some special cases, this doesn't affect the animation here (elthough I think it might affect SpiralCat's animation) \$\endgroup\$ – euanjt May 31 '15 at 12:46
  • \$\begingroup\$ Question! What happens if you're about to close a line, but the cat is standing in the last spot? \$\endgroup\$ – Mr. Llama Jun 3 '15 at 16:28
  • \$\begingroup\$ @Mr.Llama it starts making the next line as if that line had been filled (ie. the cat was in fact a bucket)- not the most effective use of a turn but happens very rarely that it doesn't really matter- the cat has to then move away on its next turn so I can place my bucket there \$\endgroup\$ – euanjt Jun 3 '15 at 16:48
5
\$\begingroup\$

HexCatcher

If the catcher can get the cat in the inside of a big hexagon with 3 units sides where the corners of the hexagon are already occupied by buckets, the catcher can keep the cat in this area and catch him. The hexagon looks like this:

enter image description here

This is what HexCatcher tries to achieve. It mentally tiles the field with these big hexagons in a way that each corner cell is part of 3 big hexagons.

If there is a chance to keep the cat in the current area by connecting two corners next to the cat, the bot will do that. (E.g. in the image if the cat is at 7,5 we choose 7,6 even if only the 6,6 and 8,5 cells are occupied yet.)

If the previous is not an option we chooses to play a corner which is a part of the area where the cat is. If all such corners are already chosen (like in the image) we choose a cell next to the cat.

Multiple small improvements are possible such as handling wrap-around better (the tiling breaks there) or doing the last couple moves optimally. I might do some of these. If it is not allowed, I will just append it (out of competition) for the ones interested.

DijkstrasCat vs HexCatcher:

enter image description here

package players;
/**
 * @author randomra
 */
import main.Field;

public class HexCatcher implements Catcher {
    public String getName() {
        return "HexCatcher";
    }

    final int[][] o = { { -1, 1 }, { 0, 1 }, { -1, 0 }, { 1, 0 }, { 0, -1 },
            { 1, -1 } };// all valid moves
    final int[][] t = { { -2, 2 }, { 0, 2 }, { -2, 0 }, { 2, 0 }, { 0, -2 },
            { 2, -2 } };// all valid double moves in one direction
    final int[][] h = { { -1, 2 }, { -2, 1 }, { -1, -1 }, { 1, -2 }, { 2, -1 },
            { 1, 1 } };// all valid moves in not one direction
    int opp = 0;

    public int[] takeTurn(Field f) {
        int[] p = f.findCat();
        // center of the hexagon the cat is in
        int[] c = { ((int) p[0] / 3) * 3 + 1, ((int) p[1] / 3) * 3 + 1 };
        // change priority of catching direction at every turn
        opp = 1 - opp;

        // check missing corner piece next to cat
        for (int i = 0; i < 6; i++) {
            int ind = (i + opp * 3) % 6;
            boolean close = false;
            for (int k = 0; k < 6; k++) {
                if (c[0] + h[ind][0] == p[0] + o[k][0]
                        && c[1] + h[ind][1] == p[1] + o[k][1]) {
                    close = true;
                }
            }
            if (f.read(c[0] + h[ind][0], c[1] + h[ind][1]) == 0 && close) {
                return new int[] { c[0] + h[ind][0], c[1] + h[ind][1] };
            }
        }
        // cut off escape route if needed
        for (int i = 0; i < 6; i++) {
            int ind = (i + opp * 3) % 6;
            if (f.read(c[0] + o[ind][0], c[1] + o[ind][1]) == -1
                    && f.read(c[0] + t[ind][0], c[1] + t[ind][1]) == 0) {
                return new int[] { c[0] + t[ind][0], c[1] + t[ind][1] };
            }
        }
        // check any missing corner piece in the area
        for (int i = 0; i < 6; i++) {
            int ind = (i + opp * 3) % 6;
            if (f.read(c[0] + h[ind][0], c[1] + h[ind][1]) == 0) {
                return new int[] { c[0] + h[ind][0], c[1] + h[ind][1] };
            }
        }
        // choose an empty cell next to the cat
        for (int i = 0; i < 6; i++) {
            int ind = (i + opp * 3) % 6;
            if (f.read(p[0] + o[ind][0], p[1] + o[ind][1]) == 0) {
                return new int[] { p[0] + o[ind][0], p[1] + o[ind][1] };
            }
        }
        return null;
    }
}
\$\endgroup\$
3
\$\begingroup\$

CloseCatcher

Chooses one of the positions where the cat could step in the next step. It chooses the one which would give the most possible paths after 3 steps for the cat if it would move there and the field wouldn't change.

Code is almost identical to my Cat entry, FreeCat, which chooses the direction in a very similar way.

SpiralCat vs CloseCatcher:

SpiralCat vs CloseCatcher

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

import main.Field;
import java.util.Arrays;

public class CloseCatcher implements Catcher {
    public String getName() {
        return "CloseCatcher";
    }

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

    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;
            }
        }
        int[] bestPos = { pos[0] + bestMove[0], pos[1] + bestMove[1] };
        return bestPos;
    }

    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;
    }

}
\$\endgroup\$
  • \$\begingroup\$ Nice +1. CloseCatcher easily captures StraightCat \$\endgroup\$ – Spikatrix Jun 1 '15 at 13:04
3
\$\begingroup\$

Dijkstra

He doesn't like cats very much (:v{ >

FreeCat vs Dijkstra (needs updated):

enter image description here

package players;

import main.Controller;
import main.Field;

import java.util.*;

/**
 * @author TheNumberOne
 *
 * Catches the cat.
 */

public class Dijkstra implements Catcher{

    private static final int[][][] CACHE;

    static {
        CACHE = new int[Controller.FIELD_SIZE][Controller.FIELD_SIZE][2];
        for (int x = 0; x < Controller.FIELD_SIZE; x++){
            for (int y = 0; y < Controller.FIELD_SIZE; y++){
                CACHE[x][y] = new int[]{x,y};
            }
        }
    }

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

    @Override
    public int[] takeTurn(Field f) {
        long startTime = System.nanoTime();

        final int[] theCat = f.findCat();
        int[] bestMove = {-1,1};
        int[] bestOpenness = {Integer.MAX_VALUE, 0};
        List<int[]> possiblePositions = new ArrayList<>();
        for (int x = 0; x < 11; x++){
            for (int y = 0; y < 11; y++){
                int[] pos = {x,y};
                if (f.isValidPosition(pos)){
                    possiblePositions.add(pos);
                }
            }
        }
        Collections.sort(possiblePositions, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return distance(o1, theCat) - distance(o2, theCat);
            }
        });
        for (int i = 0; i < possiblePositions.size() && System.nanoTime() - startTime < Controller.MAX_TURN_TIME/2; i++){
            int[] pos = possiblePositions.get(i);
            int before = f.field[pos[0]][pos[1]];
            f.placeBucket(pos);
            int[] openness = openness(theCat, f, true);
            if (openness[0] < bestOpenness[0] ||
                    (openness[0] == bestOpenness[0] &&
                            (openness[1] > bestOpenness[1])
                    )
                    ){
                bestOpenness = openness;
                bestMove = pos;
            }
            f.field[pos[0]][pos[1]] = before;
        }
        return bestMove;
    }


    /**
     *
     * @param pos The pos to calculate the openness of.
     * @param f The field to use.
     * @return Two integers. The first integer represents the number of reachable hexagons.
     * The second integer represents how strung out the squares are relative to the pos.
     */
    public static int[] openness(int[] pos, Field f, boolean catZeroWeight){
        Map<int[], Integer> lengths = new HashMap<>();
        PriorityQueue<int[]> open = new PriorityQueue<>(10,new Comparator<int[]>() {
            Map<int[], Integer> lengths;
            @Override
            public int compare(int[] o1, int[] o2) {
                return lengths.get(o1) - lengths.get(o2);
            }
            public Comparator<int[]> init(Map<int[], Integer> lengths){
                this.lengths = lengths;
                return this;
            }
        }.init(lengths));
        Set<int[]> closed = new HashSet<>();
        lengths.put(pos, catZeroWeight ? 0 : 6 - pointsAround(pos, f).size());
        open.add(pos);
        while (open.size() > 0){
            int[] top = open.remove();
            if (closed.contains(top)){
                continue;
            }
            closed.add(top);
            int l = lengths.get(top);
            List<int[]> pointsAround = pointsAround(top, f);

            for (ListIterator<int[]> iter = pointsAround.listIterator(); iter.hasNext();){
                int[] point = iter.next();
                if (closed.contains(point)){
                    iter.remove();
                }
            }

            for (int[] p : pointsAround){
                int length = l + 7 - pointsAround(p, f).size();
                if (lengths.containsKey(p)){
                    length = Math.min(length, lengths.get(p));
                }
                lengths.put(p, length);
                open.add(p);
            }
        }
        int sum = 0;
        for (int integer : lengths.values()){
            sum += integer;
        }
        return new int[]{lengths.size(),sum};
    }

    public static int distance(int[] p1, int[] p2){
        p2 = Arrays.copyOf(p2, 2);
        while (p2[0] < p1[0]){
            p2[0] += 11;
        }
        while (p2[1] < p2[0]){
            p2[1] += 11;
        }
        int lowestDistance = 0;
        for (int dx = 0; dx == 0; dx -= 11){
            for (int dy = 0; dy == 0; dy -= 11){
                lowestDistance = Math.min(lowestDistance,Math.min(Math.abs(p1[0]-p2[0]-dx),Math.min(Math.abs(p1[1]-p2[1]-dy),Math.abs(p1[0]+p1[1]-p2[0]-dx-p2[1]-dy))));
            }
        }
        return Math.min(Math.abs(p1[0]-p2[0]),Math.min(Math.abs(p1[1]-p2[1]),Math.abs(p1[0]+p1[1]-p2[0]-p2[1])));
    }

    public static int[] normalize(int[] p){
        return CACHE[(p[0]%11+11)%11][(p[1]%11+11)%11];
    }

    public static List<int[]> pointsAround(int[] p, Field f){
        int[] cat = f.findCat();
        List<int[]> locations = new ArrayList<>();
        for (int[] move : possibleMoves){
            int[] location = normalize(new int[]{p[0]+move[0], p[1] + move[1]});
            if (f.isValidPosition(location) || Arrays.equals(cat, location)){
                locations.add(location);
            }
        }
        return locations;
    }
}

How he tries to catch the cat:

He analyzes all squares of the board and tries to find the square that minimizes the openness of the board, and maximizes how much the board is strung out; in relation to the cat. The openness and stringiness of a board are computed using a modification of his famous algorithm.

Openness:

The openness of a board relative to a position is the number of reachable positions from that position.

Stringiness:

The stringiness of a board relative to a position is the sum of the distances between the reachable positions and the position.

With last update:

Now, he is much better at catching FreeCat and his own cat all cats. Unfortunately, he is also much worse at catching the crazy uncooperative cats. He could be improved by detecting if the cat is one of the crazy ones and then acting as CloseCatcher.

Bug fixed.

\$\endgroup\$
  • \$\begingroup\$ Can confirm it works so far, but by far the slowest but one of the best so far I think. Needs 134 seconds for 100 games against RandCat while doing a total of only 4406 moves! I think I'm gonna have to let my pc run overnight in one of the next days... Can you tell us a bit mor on how it works? \$\endgroup\$ – flawr Jun 2 '15 at 21:44
  • \$\begingroup\$ @flawr Added a description. \$\endgroup\$ – TheNumberOne Jun 2 '15 at 23:15
  • \$\begingroup\$ Still doesn't work for me. Gives me one error: error: cannot infer type arguments for PriorityQueue<> on this line PriorityQueue<int[]> open = new PriorityQueue<>(new Comparator<int[]>() {. \$\endgroup\$ – Spikatrix Jun 3 '15 at 5:57
  • \$\begingroup\$ @CoolGuy Are you using java 6? I think you need to update your JDK. \$\endgroup\$ – TheNumberOne Jun 3 '15 at 15:04
  • \$\begingroup\$ @CoolGuy You can also put an int[] between the two empty diamonds after PriorityQueue. \$\endgroup\$ – TheNumberOne Jun 3 '15 at 16:03
2
\$\begingroup\$

ForwordCatcher

Places a bucket in front of the cat, or if that is taken, places behind.

RabidCat vs ForwordCatcher:

RabidCat vs ForwordCatcher:

package players;

import main.Field;
import java.util.Arrays;

public class ForwordCatcher implements Catcher {
    public String getName() {
        return "ForwordCatcher";
    }

    private int[] lastPos = {0,0};

    public int[] takeTurn(Field f) {
        int[] temp = lastPos;
        int[] pos = f.findCat();
        lastPos = pos;
        int[] Move = {pos[0]*2-temp[0], pos[1]*2-temp[1]};
        if(f.isValidPosition(Move)){return Move;}
        if(f.isValidPosition(temp)){return temp;}
        Move[0] = pos[0];Move[1] = pos[1]+1;
        return Move;
    }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ There are quite a few errors, which lead me to the assumption that you did not test your program. Please fix those... \$\endgroup\$ – flawr Jun 1 '15 at 16:34
  • \$\begingroup\$ @flawr fixed. sorry about the errors. I did not test it and my Java is not to good. \$\endgroup\$ – MegaTom Jun 1 '15 at 19:53
  • \$\begingroup\$ Nice, so far everything runs smoothely, but I am still unsure whether it will always produce valid moves=) \$\endgroup\$ – flawr Jun 1 '15 at 20:34
  • 1
    \$\begingroup\$ @flawr The space behind a cat will always be empty for the catcher :) \$\endgroup\$ – TheNumberOne Jun 3 '15 at 3:07
2
\$\begingroup\$

ChoiceCatcher

Uses the same scoring mechanism as my ChoiceCat entry. There is a little modification which helps to choose relevant cells at the first few steps as ChoiceCat doesn't care about the first few buckets as it doesn't see them as threat.

ChoiceCatcher seems to score considerably better than the current catchers.

ChoiceCat vs ChoiceCatcher:

ChoiceCat vs ChoiceCatcher

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

import main.Field;

public class ChoiceCatcher implements Catcher {

    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 "ChoiceCatcher";
    }

    @Override
    public int[] takeTurn(Field f) {
        int[] bestPos = null;
        double bestPosValue = Double.MAX_VALUE;
        for (int i = 0; i < f.SIZE; i++) {
            for (int j = 0; j < f.SIZE; j++) {
                if (f.read(i, j) == Field.EMPTY) {
                    Field myField = new Field(f);
                    myField.placeBucket(new int[] { i, j });
                    double posValue = catTurnValue(myField);
                    if (posValue < bestPosValue) {
                        bestPosValue = posValue;
                        bestPos = new int[] { i, j };
                    }
                }
            }
        }
        return bestPos;
    }

    private double catTurnValue(Field f) {

        int[] pos = f.findCat();
        double[] values = new double[6];
        int count=0;
        for (int[] t : turns) {
            int[] currPos = { pos[0] + t[0], pos[1] + t[1] };
            double moveValue = movePosValue(currPos, f);
            values[count++]=moveValue;
        }
        Arrays.sort(values);
        return values[5];
    }

    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;
        int maxRoutes = 2;
        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, maxRoutes); i++) {
            fp *= product[5 - i];
        }
        double fp2 = 1;
        for (int i = 0; i < Math.min(count, 6); i++) {
            fp2 *= product[5 - i];
        }
        double retValue = Math.min(count, maxRoutes) + fp;
        double retValue2 = Math.min(count, 6) + fp2;
        return -retValue - retValue2 / 1000000;
    }

}
\$\endgroup\$
1
\$\begingroup\$

RandCatcher

This was made just for testing the controller and just randomly places the buckets (very inefficiently).

package players;

import main.Field;

public class RandCatcher implements Catcher {
    public String getName(){
        return "RandCatcher";
    }
    public int[] takeTurn(Field f){
        int[] pos = {0,0};
        do {
            pos[0] = (int) (Math.random()*f.SIZE);
            pos[1] = (int) (Math.random()*f.SIZE);
        } while( f.isValidPosition(pos)==false );
        return pos;
    }

}
\$\endgroup\$
1
\$\begingroup\$

StupidFillCatcher

This was made just for testing the controller. It just fills up column by column until the cat is caught.

package players;

import main.Field;

public class StupidFillCatcher implements Catcher {
    public String getName(){
        return "StupidFillCatcher";
    }
    public int[] takeTurn(Field f){
        for(int i=0; i < f.SIZE; i++){
            for(int j=0; j < f.SIZE; j++){
                if(f.isValidPosition(new int[] {i,j})){
                    return new int[] {i,j};
                }
            }
        }
        return new int[] {0,0};
    }

}
\$\endgroup\$

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.