23
\$\begingroup\$

This is a king of the hill challenge for Dots and Boxes (aka Pen the Pig). The game is simple, on your turn just draw a line on an empty fence. Every time you complete a square you get a point. Also, since we are playing by championship rules, if you complete at least one square on your turn you get an extra turn. This is a round robin tournament, where each bot plays each other bot twice 12 times on a 9x9 grid. Check out this match between two heavyweight titans, where ChainCollector makes mince meat of reigning co-champion Asdf: enter image description here

Rules

  1. 0.5 second time limit per move.
  2. No interfering with other bots.
  3. Use PigPen.random() and PigPen.random(int) for randomness.
  4. No writing to files.
  5. Bot and all its persistent data will be reset every time opponent changes (every 12 rounds).

Bots

Every bot extends Player.java:

package pigpen;

public abstract class Player {

public abstract int[] pick(Board board, int id, int round); 

}

Board is the game board, which mainly serves to give you access to Pen classes, and id is your playerID (tells you if you're first or second), round tells you which round your playing against the same opponent (1 or 2). The return value is an int[], where the first element is the penID (1-indexed), and the second element is the fenceID (0-indexed). See Pen.pick(int) for an easy way to generate this return value. See the Github page for example players and JavaDoc. Since we are only using a square grid ignore any functions and fields related to hexagons.

How to Run

  1. Download Source from Github.
  2. Write your controller bot (make sure to include package pigpen.players) and put it in the src/ folder;
  3. Compile with javac -cp src/* -d . src/*.java. Run with java pigpen.Tournament 4 9 9 false (the last two numbers can be changed to adjust grid size. The last variable should only be set to true if you wish to use the pp_record software.)

Scores

  1. ChainCollector: 72
  2. Asdf: 57
  3. Lazybones: 51
  4. Finisher: 36
  5. =LinearPlayer: 18
  6. =BackwardPlayer: 18
  7. RandomPlayer: 0

See Also:

Note: this game is a competitive challenge and not easily solvable, due to giving players an extra turn for completing a box.

Thanks to Nathan Merrill and Darrel Hoffman for consulting on this challenge!

Updates:

  • Added a moves(int player) method to the Board class to get a list of every move a player has made.

Indefinite Bounty (100 Rep):

First person to post a solution that wins every round, and uses strategy (adjusting play based on observing how the opponent plays).

\$\endgroup\$
  • 2
    \$\begingroup\$ GOODNESS. Finisher is waaayyyy OP! :P \$\endgroup\$ – El'endia Starman Dec 12 '15 at 5:49
  • \$\begingroup\$ @El'endiaStarman Lol, all he does is finish a Pen with one fence available, or otherwise picks a Pen with the most fences remaining. RandomPlayer is just random. \$\endgroup\$ – geokavel Dec 12 '15 at 5:53
  • 2
    \$\begingroup\$ Yeah, I know. It's just that the final score is 79-2 and RandomPlayer only got those last two boxes because it had to. :P \$\endgroup\$ – El'endia Starman Dec 12 '15 at 5:54
  • \$\begingroup\$ Hello! I want to make my own bot, but I have a question. will Pen.BOTTOM at row 0 col 0 return the same values as Pen.TOP at row 1 col 0? \$\endgroup\$ – tuskiomi Dec 13 '16 at 17:21
  • \$\begingroup\$ @tusk Yes, it does \$\endgroup\$ – geokavel Dec 13 '16 at 17:26
6
\$\begingroup\$

Lazybones

This bot is lazy. He picks a random spot and direction and continues to build in that direction without moving too much. There are only 2 cases where he does something different:

  • "make money" by closing a peg with only 1 remaining fence
  • choose a new spot and direction if placing the fence is not possible or would allow the other bot to "make money"
package pigpen.players;

import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;

import pigpen.Board;
import pigpen.Pen;
import pigpen.PigPen;
import pigpen.Player;

public class Lazybones extends Player {
    private static class Fence {
        private static boolean isOk(Board board, boolean vertical, int row, int col) {
            if (vertical) {
                Pen left = board.getPenAt(row, col - 1);
                Pen right = board.getPenAt(row, col);
                if (left.id() < 0 && right.id() < 0 ||
                        left.fences()[Pen.RIGHT] > 0 ||
                        right.fences()[Pen.LEFT] > 0 ||
                        left.remaining() == 2 ||
                        right.remaining() == 2) {
                    return false;
                }
            } else {
                Pen top = board.getPenAt(row - 1, col);
                Pen bottom = board.getPenAt(row, col);
                if (top.id() < 0 && bottom.id() < 0 ||
                        top.fences()[Pen.BOTTOM] > 0 ||
                        bottom.fences()[Pen.TOP] > 0 ||
                        top.remaining() == 2 ||
                        bottom.remaining() == 2) {
                    return false;
                }
            }
            return true;
        }

        private static Fence pickRandom(Board board) {
            List<Fence> ok = new ArrayList<>();
            List<Fence> notOk = new ArrayList<>();
            for (int row = 0; row < board.rows; row ++) {
                for (int col = 0; col < board.cols; col ++) {
                    (isOk(board, false, row, col) ? ok : notOk)
                            .add(new Fence(false, row, col));
                    (isOk(board, true, row, col) ? ok : notOk)
                            .add(new Fence(true, row, col));
                }
                (isOk(board, true, row, board.cols) ? ok : notOk)
                        .add(new Fence(true, row, board.cols));
            }
            for (int col = 0; col < board.cols; col ++) {
                (isOk(board, false, board.rows, col) ? ok : notOk)
                        .add(new Fence(false, board.rows, col));
            }
            if (ok.isEmpty()) {
                return notOk.get(PigPen.random(notOk.size()));
            } else {
                return ok.get(PigPen.random(ok.size()));
            }
        }

        private final boolean vertical;
        private final int row;
        private final int col;

        public Fence(boolean vertical, int row, int col) {
            super();
            this.vertical = vertical;
            this.row = row;
            this.col = col;
        }

        private Fence next(Board board, boolean negative) {
            int newRow = vertical ? (negative ? row - 1 : row + 1) : row;
            int newCol = vertical ? col : (negative ? col - 1 : col + 1);
            if (isOk(board, vertical, newRow, newCol)) {
                return new Fence(vertical, newRow, newCol);
            } else {
                return null;
            }
        }

        private int[] getResult(Board board) {
            if (vertical) {
                if (col < board.cols) {
                    return board.getPenAt(row, col).pick(Pen.LEFT);
                } else {
                    return board.getPenAt(row, col - 1).pick(Pen.RIGHT);
                }
            } else {
                if (row < board.rows) {
                    return board.getPenAt(row, col).pick(Pen.TOP);
                } else {
                    return board.getPenAt(row - 1, col).pick(Pen.BOTTOM);
                }
            }
        }
    }

    private Fence lastFence = null;
    private boolean negative = false;

    @Override
    public int[] pick(Board board, int id, int round) {
        List<Pen> money = board.getList().stream()
                .filter(p -> p.remaining() == 1).collect(Collectors.toList());
        if (!money.isEmpty()) {
            return money.get(PigPen.random(money.size())).pick(Pen.TOP);
        }
        if (lastFence != null) {
            lastFence = lastFence.next(board, negative);
        }
        if (lastFence == null) {
            lastFence = Fence.pickRandom(board);
            negative = PigPen.random(2) == 0;
        }
        return lastFence.getResult(board);
    }
}
\$\endgroup\$
  • \$\begingroup\$ Wow, nice job! LazyBones owns finisher (see new animation). \$\endgroup\$ – geokavel Dec 13 '15 at 20:56
  • \$\begingroup\$ By the way, just so everyone knows, another way to get the Pen to the left of a given pen is pen.n(Pen.LEFT) (neighbor function). \$\endgroup\$ – geokavel Dec 13 '15 at 21:01
  • \$\begingroup\$ Also, I think it's unnecessary when you check the bottom fence of a Pen and the top fence of the one below it, they are guaranteed to have the same value! \$\endgroup\$ – geokavel Dec 13 '15 at 22:20
  • \$\begingroup\$ The pick() method now has an int round parameter at the end, so if you could please add that. \$\endgroup\$ – geokavel Dec 14 '15 at 0:06
  • \$\begingroup\$ I have to check both fences, because any of the pen objects can be outside of the board (id == -1). For the same reason I can't use the neighbor function. \$\endgroup\$ – Sleafar Dec 14 '15 at 5:58
6
\$\begingroup\$

ChainCollector

This bot likes chains1. He wants as much of them as possible. Sometimes he even sacrifices a small part of a chain to win a bigger one.

[1] A chain consists of pens connected by open fences, where each pen has 1 or 2 open fences. If a single pen belonging to the chain can be finished, then because of the championship rule the whole chain can be finished as well.

package pigpen.players;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.TreeMap;

import pigpen.Board;
import pigpen.Pen;
import pigpen.Player;

public class ChainCollector extends Player {
    private enum Direction {
        TOP, RIGHT, BOTTOM, LEFT;

        public Direction opposite() {
            return values()[(ordinal() + 2) % 4];
        }
    }

    private enum ChainEndType {
        OPEN, CLOSED, LOOP
    }

    private static class PenEx {
        private final int id;
        private final List<Fence> openFences = new ArrayList<>();
        private boolean used = false;

        public PenEx(int id) {
            super();
            this.id = id;
        }

        public void addOpenFence(Direction direction, PenEx child) {
            openFences.add(new Fence(this, direction, child));
            if (child != null) {
                child.openFences.add(new Fence(child, direction.opposite(), this));
            }
        }
    }

    private static class Fence {
        public final PenEx parent;
        public final Direction direction;
        public final PenEx child;

        public Fence(PenEx parent, Direction direction, PenEx child) {
            super();
            this.parent = parent;
            this.direction = direction;
            this.child = child;
        }

        public int[] getMove() {
            if (parent == null) {
                return new int[] { child.id, direction.opposite().ordinal() };
            } else {
                return new int[] { parent.id, direction.ordinal() };
            }
        }
    }

    private static class Moves {
        private final TreeMap<Integer, List<Fence>> map = new TreeMap<>();

        public void add(int score, Fence move) {
            List<Fence> list = map.get(score);
            if (list == null) {
                list = new ArrayList<>();
                map.put(score, list);
            }
            list.add(move);
        }

        public boolean isEmpty() {
            return map.isEmpty();
        }

        public boolean hasExactlyOne() {
            return map.size() == 1 && map.firstEntry().getValue().size() == 1;
        }

        public int getLowestScore() {
            return map.firstKey();
        }

        public int[] getLowMove() {
            return map.firstEntry().getValue().get(0).getMove();
        }

        public int[] getHighMove() {
            return map.lastEntry().getValue().get(0).getMove();
        }
    }

    private static class BoardEx {
        private final List<PenEx> pens = new ArrayList<>();
        private final Moves neutralMoves = new Moves();
        private final Moves finisherMoves = new Moves();
        private final Moves safeFinisherMoves = new Moves();
        private final Moves sacrificeMoves = new Moves();
        private final Moves badMoves = new Moves();

        public BoardEx(Board board) {
            super();
            PenEx[][] tmp = new PenEx[board.rows][board.cols];
            for (int row = 0; row < board.rows; ++row) {
                for (int col = 0; col < board.cols; ++col) {
                    Pen pen = board.getPenAt(row, col);
                    int[] fences = pen.fences();
                    PenEx penEx = new PenEx(pen.id());
                    tmp[row][col] = penEx;
                    pens.add(penEx);
                    if (fences[Pen.TOP] == 0) {
                        penEx.addOpenFence(Direction.TOP, row == 0 ? null : tmp[row - 1][col]);
                    }
                    if (row == board.rows - 1 && fences[Pen.BOTTOM] == 0) {
                        penEx.addOpenFence(Direction.BOTTOM, null);
                    }
                    if (fences[Pen.LEFT] == 0) {
                        penEx.addOpenFence(Direction.LEFT, col == 0 ? null : tmp[row][col - 1]);
                    }
                    if (col == board.cols - 1 && fences[Pen.RIGHT] == 0) {
                        penEx.addOpenFence(Direction.RIGHT, null);
                    }
                }
            }
        }

        private ChainEndType followChain(Fence begin, List<Fence> result) {
            Fence current = begin;
            for (;;) {
                current.parent.used = true;
                result.add(current);
                if (current.child == null) {
                    return ChainEndType.OPEN;
                }
                List<Fence> childFences = current.child.openFences;
                switch (childFences.size()) {
                    case 1:
                        current.child.used = true;
                        return ChainEndType.CLOSED;
                    case 2:
                        if (current.child == begin.parent) {
                            return ChainEndType.LOOP;
                        } else {
                            current = current.direction.opposite() == childFences.get(0).direction ?
                                    childFences.get(1) : childFences.get(0);
                        }
                        break;
                    case 3:
                    case 4:
                        return ChainEndType.OPEN;
                    default:
                        throw new IllegalStateException();
                }
            }
        }

        public void findChains() {
            for (PenEx pen : pens) {
                if (!pen.used && pen.openFences.size() > 0) {
                    if (pen.openFences.size() < 3) {
                        List<Fence> fences = new ArrayList<>();
                        ChainEndType type1 = pen.openFences.size() == 1 ?
                                ChainEndType.CLOSED : followChain(pen.openFences.get(1), fences);
                        if (type1 == ChainEndType.LOOP) {
                            badMoves.add(fences.size(), fences.get(0));
                        } else {
                            Collections.reverse(fences);
                            ChainEndType type2 = followChain(pen.openFences.get(0), fences);
                            if (type1 == ChainEndType.OPEN && type2 == ChainEndType.CLOSED) {
                                type1 = ChainEndType.CLOSED;
                                type2 = ChainEndType.OPEN;
                                Collections.reverse(fences);
                            }
                            if (type1 == ChainEndType.OPEN) {
                                badMoves.add(fences.size() - 1, fences.get(fences.size() / 2));
                            } else if (type2 == ChainEndType.CLOSED) {
                                finisherMoves.add(fences.size() + 1, fences.get(0));
                                if (fences.size() == 3) {
                                    sacrificeMoves.add(fences.size() + 1, fences.get(1));
                                } else {
                                    safeFinisherMoves.add(fences.size() + 1, fences.get(0));
                                }

                            } else {
                                finisherMoves.add(fences.size(), fences.get(0));
                                if (fences.size() == 2) {
                                    sacrificeMoves.add(fences.size(), fences.get(1));
                                } else {
                                    safeFinisherMoves.add(fences.size(), fences.get(0));
                                }
                            }
                        }
                    } else {
                        pen.used = true;
                        for (Fence fence : pen.openFences) {
                            if (fence.child == null || fence.child.openFences.size() > 2) {
                                neutralMoves.add(fence.child == null ? 0 : fence.child.openFences.size(), fence);
                            }
                        }
                    }
                }
            }
        }

        public int[] bestMove() {
            if (!neutralMoves.isEmpty()) {
                if (!finisherMoves.isEmpty()) {
                    return finisherMoves.getHighMove();
                }
                return neutralMoves.getHighMove();
            }
            if (!safeFinisherMoves.isEmpty()) {
                return safeFinisherMoves.getHighMove();
            }
            if (badMoves.isEmpty() && !finisherMoves.isEmpty()) {
                return finisherMoves.getHighMove();
            }
            if (!sacrificeMoves.isEmpty()) {
                if (sacrificeMoves.hasExactlyOne()) {
                    if (badMoves.getLowestScore() - sacrificeMoves.getLowestScore() >= 2) {
                        return sacrificeMoves.getLowMove();
                    } else {
                        return finisherMoves.getHighMove();
                    }
                } else {
                    return finisherMoves.getHighMove();
                }
            }
            if (!badMoves.isEmpty()) {
                return badMoves.getLowMove();
            }
            return null;
        }
    }

    @Override
    public int[] pick(Board board, int id, int round) {
        BoardEx boardEx = new BoardEx(board);
        boardEx.findChains();
        return boardEx.bestMove();
    }
}
\$\endgroup\$
  • \$\begingroup\$ Wow, thank you for your entry. I am humbled that someone has put in so much time into a project I created. I think the introduction of this bot has affected the random number generation, such that Asdf now beats Lazybones both times by a slight margin. \$\endgroup\$ – geokavel Dec 17 '15 at 23:54
  • \$\begingroup\$ Well, the idea for the bot looked pretty simple before I started, and then I wanted to finish it. ;) With randomness involved you should probably let the bots play more than 2 games to get more accurate results. \$\endgroup\$ – Sleafar Dec 18 '15 at 0:00
  • \$\begingroup\$ Good thought. I increased it to 12 rounds per matchup, and now, as you can see, Asdf has a slight edge. Even at 100 rounds, it only wins 13 more games than Lazybones. \$\endgroup\$ – geokavel Dec 18 '15 at 0:25
3
\$\begingroup\$

Finisher

package pigpen.players;

import pigpen.*;

import java.util.*;

/**
 * Picks a Pen with only one fence remaining. 
 * Otherwise picks one with the most fences remaining
 */
public class Finisher extends Player implements Comparator<Pen> {


  public int[] pick(Board board, int id) {
     return Collections.max(board.getList(),this).pick(Pen.TOP);

  }

  @Override
  public int compare(Pen p1, Pen p2) {
    //1 remaining is best, all remaining is second.
    int r1 = p1.remaining();
    int r2 = p2.remaining();
    if(r1 == 1) r1 = 7;
    if(r2 == 1) r2 = 7;
    return Integer.compare(r1,r2);
 }


}

Uses a Comparator to pick the Pen with the most available fences, but gives priority to Pen's with only 1 fence available. (7 is used rather than 5 to allow this code to work in hexagon mode as well)

\$\endgroup\$
3
\$\begingroup\$

Asdf

Assigns a score to each fence and then picks the best out of them. For example: A pen with one open fence has a score of 10, while a pen with 2 open fences has a score of -8.

It seems like Lazybones uses a similar strategy, because it ties with this bot.

package pigpen.players;

import java.util.*;
import pigpen.*;

public class Asdf extends Player {
    private final List<Score> scores = new ArrayList<>();

    @Override
    public int[] pick(Board board, int id, int round) {
        scores.clear();
        List<Pen> pens = board.getList();

        pens.stream().filter(x -> !x.closed()).forEach((Pen p) -> evaluate(p));
        Optional<Score> best = scores.stream().max(Comparator.comparingInt(p -> p.points));

        if (best.isPresent()) {
            Score score = best.get();
            return score.pen.pick(score.fence);
        }
        return null;
    }

    private void evaluate(Pen pen) {
        int[] fences = pen.fences();
        for (int i = 0; i < fences.length; i++) {
            if (fences[i] == 0) {
                int points = getPoints(pen);
                Pen neighbour = pen.n(i);
                if (neighbour.id() != -1) {
                    points += getPoints(neighbour);
                }
                scores.add(new Score(pen, i, points));
            }
        }
    }

    private int getPoints(Pen pen) {
        switch (pen.remaining()) {
            case 1: return 10;
            case 2: return -1;
            case 3: return 1;
        }
        return 0;
    }

    class Score {
        private Pen pen;
        private int fence;
        private int points;

        Score(Pen pen, int fence, int points) {
            this.pen = pen;
            this.fence = fence;
            this.points = points;
        }
    }
}
\$\endgroup\$
  • \$\begingroup\$ Here are the scores. It's interesting that whoever goes second gets twice as many points. Asdf vs. Lazybones: 27 - 54; Lazybones vs. Asdf: 27 - 54 \$\endgroup\$ – geokavel Dec 14 '15 at 15:44
  • \$\begingroup\$ @geokavel Yes, because then the bots are forced to do a "bad turn", so the opponent can close a pen. \$\endgroup\$ – CommonGuy Dec 14 '15 at 15:51
  • \$\begingroup\$ Is this the best possible algorithm, then? \$\endgroup\$ – justhalf Dec 15 '15 at 1:07
  • \$\begingroup\$ @justhalf It's not, because people play this game in championships. I think these algorithms can definitely be expanded on. See the links I provided for more info. \$\endgroup\$ – geokavel Dec 16 '15 at 17:17
0
\$\begingroup\$

LinearPlayer

package pigpen.players;

import pigpen.*;

/**
 * Picks the first available fence in the first available Pen
 */ 
public class LinearPlayer extends Player {


@Override
public int[] pick(Board board, int id) {
    for(int p = 1;p<=board.size;p++) {
        Pen pen = board.get(p);
            if(!pen.closed()) {
                int[] fences = pen.fences();
                    for(int i =0;i<fences.length;i++) {
                        if(fences[i] == 0) {
                            return new int[]{pen.id(),i};
                        }
                    }
                }
        }
    return new int[]{1,0};
    } 
}

The easiest way to write this bot is actually return null, because an invalid entry will automatically select the first available fence. This code does not use any shortcut methods and manually generates the return value.

\$\endgroup\$
0
\$\begingroup\$

BackwardPlayer

package pigpen.players;

import pigpen.*;

/**
 * Picks the first available fence in the last available Pen
 */
 public class BackwardPlayer extends Player {

public int[] pick(Board board, int id) {
    for(int i = board.size;i>0;i--) {
        Pen p = board.get(i);
        if(!p.closed()) {
            return p.pick(Pen.TOP);
        }
    }
    return new int[] {1,0};
}
}

This code uses the shortcut method Pen.pick(int) to generate the return value. If the top fence is unavailable, it will pick the closest available fence going clockwise.

\$\endgroup\$
0
\$\begingroup\$

RandomPlayer

package pigpen.players;

import pigpen.*;


/** 
 * Picks the first available fence in a random Pen 
 */
public class RandomPlayer extends Player {
    public int[] pick(Board board, int id) {
        int pen = PigPen.random(board.size)+1;
        return board.get(pen).pick(Pen.TOP);
    }
}

Same idea as BackwardPlayer, but randomly selects a pen. Note the +1 because Pen's are 1-indexed.

\$\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.