24
\$\begingroup\$

This is a chess-KOTH with simplified rules (because chess itself is already complicated, playing it via a simple program doesn't make it easier). At the moment it is limited to java (version 8), but creating a wrapper-class isn't that difficult (in case someone wants to do this).

Chessboard

The chessboard in the control program uses a modified version of the ICCF numeric notation. It is zero-based, meaning the bottom-left field is the position 0,0, while the upper-right field is the position 7,7.

Modified rules

  • En passant will be ignored.
  • Castling isn't possible.
  • The Fifty-move rule applies automatically (meaning the game ends in a draw).
  • Promotion of pawns to queens happen automatically when they reach the end of the board.
  • If a player needs longer than 2 seconds to move, he will lose the game.
  • Returning an invalid move will result in losing the game.
  • To win, you have to capture the enemy king. It isn't enough to checkmate the enemy.
  • This also allows you to move your king to fields where the enemy can capture you.
  • White begins the game.
  • White is placed "at the bottom" of the field (y=0), black is located at the top (y=7).
  • Accessing other ressources than your bot (internet, files, other bots, ...) is prohibited.

Scoring

  • Winning grants you 3 points, a draw 1 point and losing 0 points.
  • Each submission will play against each other submission 10 times (5 times as white, 5 as black).

Controller

You can find the control program on github.
To participate, you have to create a class inside the player package and it has to be a subclass of Player. As an example, look at TestPlayer (which will also be included in the scoring).

Each game, the controller will create a new instance of your player. Then, each turn you have to return a move. The controller provides you with a copy of the Board, which contains a 8x8 array of Fields. A field contains information about its color, its position and the piece on it, if there is one.
The controller also provides you with information about the enemy player, such as isCheck and getPieces(). Calling getMove() on the enemy will get you disqualified.

Scoreboard

01) AlphaBetaPV:         229
02) AlphaBeta:           218
03) PieceTaker:          173
04) Cheese:              115
05) ThreeMoveMonte:      114
06) StretchPlayer:        93
07) DontThinkAhead:       81
08) SimplePlayer:         27
09) TestPlayer:           13

The contest is limited to java because it makes creating answers easier, since you can profit from the methods provided by the controller. However, if someone creates a wrapper, I will include other languages.

\$\endgroup\$
  • 2
    \$\begingroup\$ It also turns a stalemate into a loss :( \$\endgroup\$ – Geobits Sep 3 '14 at 12:50
  • 2
    \$\begingroup\$ you can profit from the methods provided by the controller: This isn't all that true. Most of the useful methods are package private, so they cannot be used. Would you mind maybe adding a simulateMove method to the Board class, which returns a deep copy of the board with the given move applied? That way, we don't have to write it ourselves (or copy-paste your entire code^^). \$\endgroup\$ – tim Sep 3 '14 at 15:55
  • 4
    \$\begingroup\$ The 2 second rule is fantastic. Rather than being a hard-on chess optimal bots, the challenge is like : Create the best not-so intelligent chess bot \$\endgroup\$ – Mark Gabriel Sep 4 '14 at 5:45
  • 2
    \$\begingroup\$ @Geobits I updated the controller. Most of the useful methods are public now ;) \$\endgroup\$ – CommonGuy Sep 4 '14 at 9:16
  • 3
    \$\begingroup\$ I'm almost inclined to write a bot that throws a Throwable or even Error since it will avoid losing. I'd call it the BoardTipper. \$\endgroup\$ – Ingo Bürk Sep 6 '14 at 14:14
4
\$\begingroup\$

AlphaBetaPV

AlphaBetaPV stands for Alpha Beta with Principal Variation (it's not principal-variation search). With only a few more lines woven into the code of AlphaBeta.java, it beats AlphaBeta.java. And again, sorry, for only morphing and fusing codes from other internet sources into this JAVA code.

  • The principal variation is stored and used for the simplest move priority to accelerate the alpha beta cut off:
    • while iterative deepening and
    • for the next move.
  • Simple position evaluation:
    • Number of moves each party has (degree of freedom) to support the opening.
    • Pawn promotion to support the end game.
  • Still no quiescence search.

Still playing boring.

package player;

import java.util.Random;
import controller.*;

public class AlphaBetaPV extends Player {
    private static final int INFINITY = Integer.MAX_VALUE;
    private static final int MAXTIME = 1800; // max time for evaluation
    private static final Random random=new Random();
    private static int seed=1;

    private long time; // time taken this turn
    private int iterativeDepth;
    private Player myOpponent;
    private int commitedDepth;

    private static Piece[] pieces = new Piece[20000];
    private static Point[] points = new Point[20000];
    private static int[] freedom = new int[20];

    private static class PV {
        Move move;
        PV next;
    }       
    private PV pv= new PV();

    @Override
    public Move getMove(Board root, Player min) {
        time=System.currentTimeMillis();
        seed++; myOpponent=min;
        // use last PV for an estimate of this move
        if (pv.next!=null) pv=pv.next;
        if (pv.next!=null) pv=pv.next;
        iterative_deepening(root);
        return pv.move;
    }

    private void iterative_deepening(Board root) {
        try {
            for (iterativeDepth = (commitedDepth=Math.max(2, commitedDepth-2));; iterativeDepth++) {
                alphaBeta(root, -INFINITY, +INFINITY, iterativeDepth, this, myOpponent, 0, 0, pv, pv);
                commitedDepth=iterativeDepth;
            }
        } catch (InterruptedException e) {}
    }

    //http://chessprogramming.wikispaces.com/Alpha-Beta
    private int alphaBeta(Board root, int alpha, int beta, int d, Player max, Player min, int begin, int level, PV pv, PV pline) throws InterruptedException {
        if (d==0 || root.getKing(max) == null) return evaluate(root, d, level);
        int end = allMoves(root, max, begin, level, pv);
        PV line= new PV();
        for (int m=begin; m<end; m++) {
            Board board = root.copy();
            board.movePiece(new Move(pieces[m].copy(), points[m]));
            int score = -alphaBeta(board, -beta, -alpha, d - 1, min, max, end, level+1, pline==null?null:pline.next, line);
            if (score >= beta)
                return beta; // fail hard beta-cutoff
            if (score > alpha) {
                pline.move=new Move(pieces[m].copy(), points[m]); // store as principal variation
                pline.next=line; line=new PV();
                alpha = score; // alpha acts like max in MiniMax
            }
        }
        return alpha;
    }

    private int evaluate(Board board, int d, int level) throws InterruptedException {
        if ((System.currentTimeMillis() - time) > MAXTIME)  throw new InterruptedException();
        int minmax=2*((iterativeDepth-d)&1)-1;
        int king = 0, value=(level>1)?minmax*(freedom[level-1]-freedom[level-2]):0;
        Field[][] field = board.getFields();
        for (int x = 0; x < 8; x++) {
            for (int y = 0; y < 8; y++) {
                Piece piece = field[x][y].getPiece();
                if (piece==null) continue;

                int sign=(piece.getTeam()==getTeam())?-minmax:minmax;
                switch (piece.getType()) {
                case PAWN:      value += (  1000+2*(piece.getTeam()==Color.WHITE?y:7-y))*sign; break;
                case KNIGHT:    value +=    3000*sign; break;
                case BISHOP:    value +=    3000*sign; break;
                case ROOK:      value +=    5000*sign; break;
                case QUEEN:     value +=    9000*sign; break;
                case KING:      king  += (100000-(iterativeDepth-d))*sign; break;
                default: // value += 0;
                }
            }
        }
        return king==0?value:king;
    }

    private int allMoves(Board board, Player player, int begin, int level, PV pv) {
        random.setSeed(seed);
        int m=0;
        for (Piece piece : player.getPieces(board)) {
            for (Point point: piece.getValidDestinationSet(board)) {
                // shuffle and store
                int r=begin+random.nextInt(++m);
                points[begin+m-1]=points[r];    pieces[begin+m-1]=pieces[r];
                points[r]=point;                pieces[r]=piece;
            }
        }
        freedom[level]=m;
        if (pv!=null && pv.move!=null)  { // push PV to front
            for (int i = 0; i < m; i++) {
                if (pv.move.getPiece().equals(pieces[begin+i]) && pv.move.getDestination().equals(points[begin+i])) {
                    Point point = points[begin];    Piece piece = pieces[begin];
                    points[begin]=points[begin+i];  pieces[begin]=pieces[begin+i];
                    points[begin+i]=point;          pieces[begin+i]=piece;  
                    break;
                }
            }
        }
        return begin+m;
    }
}
\$\endgroup\$
11
+100
\$\begingroup\$

PieceTaker

The code is a little bit of a mess, but it does work. Right now it wins against all other players, even if it is only given 400ms instead of the allowed 2000ms.

I'm using alpha beta pruning with iterative deepening to make sure that the AI doesn't go over the time limit. The current heuristic is very simple (only lost/taken pieces are taken into considerations; not position on the board, etc).

In the future I might also add killer heuristics and sort the moves before examining them.

package player;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Random;

import controller.*;

public class PieceTaker extends Player {

    private boolean DEBUG = false;
    private Player pieceTaker;
    private static final int MAXINT = Integer.MAX_VALUE / 2;
    private static final int MININT = Integer.MIN_VALUE / 2;
    private static final boolean ITERATIVE_DEEPENING = true;
    private static final int MAX_DEPTH = 6; // max depth if not using iterative
                                            // deepening
    private static int MAXTIME = 400; // max time for evaluation (if using
                                        // iterativeDeepening). We still need to
                                        // evaluate moves, so save time for
                                        // that.
    private long time; // time taken this turn

    @Override
    public Move getMove(Board board, Player enemy) {
        pieceTaker = this;
        // generate all possible moves
        List<Move> possibleMoves = new ArrayList<>();
        List<Piece> pieces = this.getPieces(board);
        for (Piece piece : pieces) {
            Point[] destinations = piece.getValidDestinations(board);
            for (Point point : destinations) {
                possibleMoves.add(new Move(piece, point));
            }
        }

        // rate moves
        Move best = getNextMove(board, possibleMoves, enemy);
        return best;
    }

    private Move getNextMove(Board board, List<Move> possibleMoves, Player enemy) {
        time = System.currentTimeMillis();

        // wrap moves in node class and apply move
        List<Node> children = new ArrayList<>();
        for (Move move : possibleMoves) {
            Node newNode = new Node(move, board, this, enemy, 0);
            newNode.applyAndRateMove();
            children.add(newNode);
        }

        if (ITERATIVE_DEEPENING) {
            for (int depth = 1;; depth++) {
                List<Node> copy = new ArrayList<>();
                // copy nodes (so that in case time is over we still have a valid set)
                for (Node node : children) {
                    copy.add(node.copy());
                }
                // rate copy
                rateMoves(copy, depth);
                if ((System.currentTimeMillis() - time) > MAXTIME) {
                    break;
                }
                // copy rated nodes back
                children = new ArrayList<>();
                for (Node node : copy) {
                    children.add(node.copy());
                }
            }
        } else {
            rateMoves(children, MAX_DEPTH);
        }

        return getBestMove(children);
    }

    // returns node with the highest score
    private Move getBestMove(List<Node> nodes) {
        if (DEBUG) {
            System.out.println("\n");
            for (Node node : nodes) {
                System.out.println(node.toString());
            }
        }

        Collections.sort(nodes, new ComparatorNode());

        // get all nodes with top rating
        List<Node> best = new ArrayList<>();
        int bestValue = nodes.get(0).getRating();
        for (Node node : nodes) {
            if (node.getRating() == bestValue) {
                best.add(node);
            }
        }

        Random random = new Random();
        Node bestNode = best.get(random.nextInt(best.size()));
        if (DEBUG) {
            System.out.println("using: " + bestNode.toString());
        }
        return bestNode.getMove();
    }

    private void rateMoves(List<Node> nodes, int depth) {
        if (nodes.size() == 1) {
            // nothing to rate. one possible move, take it.
            return;
        }

        for (Node node : nodes) {
            int alphaBeta = alphaBeta(node, depth, MININT, MAXINT);
            node.setRating(alphaBeta);
        }
    }

    protected int alphaBeta(Node node, int depth, int alpha, int beta) {
        Player currentPlayer = node.getCurrentPlayer();
        Player otherPlayer = node.getOtherPlayer();
        // game over
        if (node.getBoard().getKing(currentPlayer) == null) {
            if (currentPlayer == this) {
                return node.getRating() - 999;
            } else {
                return node.getRating() + 999;
            }
        } else {
            // TODO check for draw and rate draw (might be good to take it)
        }
        if (depth <= 0) {
            return node.getRating(); // the rating in the move is always as seen
                                        // for player, not current player
        }

        List<Node> children = getPossibleMoves(node);
        if (otherPlayer == this) {
            for (Node child : children) {
                if ((System.currentTimeMillis() - time) > MAXTIME) {
                    break; // time over.
                }
                alpha = Math.max(alpha,
                        alphaBeta(child, depth - 1, alpha, beta));
                if (beta <= alpha) {
                    break; // cutoff
                }
            }
            return alpha;
        } else {
            for (Node child : children) {
                if ((System.currentTimeMillis() - time) > MAXTIME) {
                    break; // time over.
                }
                beta = Math.min(beta, alphaBeta(child, depth - 1, alpha, beta));
                if (beta <= alpha) {
                    break; // cutoff
                }
            }
            return beta;
        }
    }

    private List<Node> getPossibleMoves(Node node) {
        List<Node> possibleMoves = new ArrayList<>();
        List<Piece> pieces = node.getOtherPlayer().getPieces(node.getBoard());
        for (Piece piece : pieces) {
            Point[] destinations = piece.getValidDestinations(node.getBoard());
            for (Point point : destinations) {
                Node newNode = new Node(new Move(piece, point),
                        node.getBoard(), node.getOtherPlayer(),
                        node.getCurrentPlayer(), node.getRating());
                if (newNode.applyAndRateMove()) {
                    possibleMoves.clear();
                    possibleMoves.add(newNode);
                    return possibleMoves; // we won, return wining move
                }
                possibleMoves.add(newNode);
            }
        }
        return possibleMoves;
    }

    private class Node {
        private Move move;
        private Move originalMove;
        private Board board;
        private Player currentPlayer;
        private Player otherPlayer;
        private int rating;

        public Node(Move move, Board board, Player currentPlayer,
                Player otherPlayer, int rating) {
            super();
            this.move = new Move(move.getPiece().copy(), move.getDestination()
                    .copy());
            this.originalMove = new Move(move.getPiece().copy(), move
                    .getDestination().copy());
            // copy board so changes only affect this node
            this.board = board.copy();
            this.currentPlayer = currentPlayer;
            this.otherPlayer = otherPlayer;
            this.rating = rating;
        }

        @Override
        public String toString() {
            return " [" + originalMove.toString() + " (r: " + rating + ")] ";
        }

        public Node copy() {
            Node copy = new Node(new Move(originalMove.getPiece().copy(),
                    originalMove.getDestination().copy()), board.copy(),
                    currentPlayer, otherPlayer, rating);
            return copy;
        }

        public boolean applyAndRateMove() {
            // call rate before apply as it needs the unchanged board
            rateMove();
            board.movePiece(move);
            if (getBoard().getKing(currentPlayer) == null) {
                return true;
            } else {
                return false;
            }
        }

        private void rateMove() {
            Point dest = move.getDestination();
            Field destField = board.getFields()[dest.getX()][dest.getY()];

            int value = 0;
            if (destField.hasPiece()) {
                PieceType type = destField.getPiece().getType();
                switch (type) {
                case PAWN:
                    value = 1;
                    break;
                case KNIGHT:
                    value = 3;
                    break;
                case BISHOP:
                    value = 3;
                    break;
                case ROOK:
                    value = 5;
                    break;
                case QUEEN:
                    value = 9;
                    break;
                case KING:
                    value = 111;
                    break;
                default:
                    value = 0;
                }
            }

            if (currentPlayer == pieceTaker) {
                this.rating += value;
            } else {
                this.rating -= value;
            }
        }

        public Player getOtherPlayer() {
            return otherPlayer;
        }

        public Player getCurrentPlayer() {
            return currentPlayer;
        }

        public Board getBoard() {
            return board;
        }

        public int getRating() {
            return rating;
        }

        public void setRating(int r) {
            this.rating = r;
        }

        public Move getMove() {
            return originalMove;
        }
    }

    private class ComparatorNode implements Comparator<Node> {
        @Override
        public int compare(Node t, Node t1) {
            return t1.getRating() - t.getRating();
        }
    }
}
\$\endgroup\$
  • \$\begingroup\$ This bot is tough! \$\endgroup\$ – Mark Gabriel Sep 8 '14 at 12:56
  • \$\begingroup\$ @MarkGabriel thanks :) honestly, I wasn't too happy with it at first. It can only think ahead 2-4 moves, which isn't enough in a lot of situations. I have an improved version were I don't copy the field but undo moves which is a lot faster, but it's buggy and I cannot seem to fix it :( \$\endgroup\$ – tim Sep 8 '14 at 19:58
11
\$\begingroup\$

StretchPlayer

This bot plays just like me!

By the way I am terrible at chess.

The comments explain what it is actually doing. It's a lot like my thought process.

As an added bonus, beats all other bots by a considerable margin. (so far)

EDIT: now predicts opponent by running itself as the enemy!

EDIT 2: The program made the mistake of not actually killing the king when it was wide open. It was reprimanded accordingly.

import java.util.List;
import java.util.Set;

import controller.*;

public class StretchPlayer extends Player{

    boolean avoidStackOverflow = false;
    @Override
    public Move getMove(Board board, Player enemy) {
        List<Piece> pieces = this.getPieces(board);
        for(Piece piece:pieces){
            //first order of business: kill the enemy king if possible
            if(piece.getValidDestinationSet(board).contains(board.getKing(enemy).getPos())){
                return new Move(piece,board.getKing(enemy).getPos());
                }
        }
        //I suppose I should protect my king.
        for(Piece ePiece:enemy.getPieces(board)){
            if(ePiece.getValidDestinationSet(board).contains(board.getKing(this).getPos())){
                //ideally I would move my king.
                for(Point p:board.getKing(this).getValidDestinationSet(board)){
                    //but I don't want it to move into a spot where the enemy can get to. That would be suicide.
                    boolean moveHere=true;
                    for(Piece enemyPiece:enemy.getPieces(board)){
                        if(enemyPiece.getValidDestinationSet(board).contains(p)){
                            moveHere=false;
                        }
                    }
                    if(moveHere){
                        return new Move(board.getKing(this),p);
                    }
                }
                //so the king can't move. But I can fix this. There has to be a way!
                for(Piece myPiece:pieces){
                    for(Point possMove:myPiece.getValidDestinationSet(board)){
                        Board newBoard = board.copy();
                        newBoard.movePiece(new Move(myPiece,possMove));
                        if(!newBoard.isCheck(this, enemy)){
                            //Aha! found it!
                            return new Move(myPiece,possMove);
                        }
                    }

                }
                //uh-oh. Better just go with the flow. I'll lose anyway.
            }
        }
        for(Piece piece:pieces){
            Set<Point> moves = piece.getValidDestinationSet(board);
            for(Piece opponentPiece:enemy.getPieces(board)){
                if(moves.contains(opponentPiece.getPos())){
                    Point futurePosition = null;
                    //search for this illusive move (no indexOf(...)?)
                    for(Point p:moves){
                        if(p.getX()==opponentPiece.getPos().getX()&&p.getY()==opponentPiece.getPos().getY()){
                            futurePosition = p;
                        }
                    }
                    //it can now kill the enemies piece. But first, it should probably check if it is going to get killed if it moves there.
                    boolean safe = true;
                    for(Piece nextMoveOpponent:enemy.getPieces(board)){
                        if(nextMoveOpponent.getValidDestinationSet(board).contains(futurePosition)&&piece.getType()!=PieceType.PAWN){
                            safe = false;
                        }
                        //it would also be beneficial if the enemy didn't kill my king next round.
                        if(nextMoveOpponent.getValidDestinationSet(board).contains(board.getKing(this).getPos())){
                            safe = false;
                        }
                    }
                    if(safe){
                        return new Move(piece, futurePosition);
                    }

                }
            }
        }
        //ok, so I couldn't kill anything. I'll just put the enemy king in check!
        for(Piece piece:pieces){
            for(Point p:piece.getValidDestinationSet(board)){
                Piece simulatedMove = piece.copy();
                simulatedMove.setPos(p);
                if(simulatedMove.getValidDestinationSet(board).contains(board.getKing(enemy).getPos())){
                    return new Move(piece,p);
                }
            }
        }
        //hmmmm... What would I do if I was the enemy?
        if(!avoidStackOverflow){
            avoidStackOverflow = true;
            Board copy = board.copy();
            Move thinkingLikeTheEnemy = this.getMove(copy, this);
            avoidStackOverflow = false;
            Board newBoard = copy;
            //I wonder what piece it's targeting...
            Piece targeted =null;
            for(Piece p:pieces){
                if(p.getPos().getX()==thinkingLikeTheEnemy.getDestination().getX()&&p.getPos().getY()==thinkingLikeTheEnemy.getDestination().getY()){
                    targeted=p;
                }
            }
            //better move that piece out of the way, if it doesn't hurt my king
            if(targeted!=null){
                for(Point p:targeted.getValidDestinations(newBoard)){
                    newBoard = board.copy();
                    newBoard.movePiece(new Move(targeted,p));
                    for(Piece enemy2:enemy.getPieces(newBoard)){
                        if(!enemy2.getValidDestinationSet(newBoard).contains(p) && !newBoard.isCheck(this, enemy)){
                            return new Move(targeted,p);
                        }
                    }
                }
                newBoard.movePiece(new Move(targeted,thinkingLikeTheEnemy.getPiece().getPos()));
                if(!newBoard.isCheck(this, enemy)){
                    return new Move(targeted,thinkingLikeTheEnemy.getPiece().getPos());
                }
            }
        }

        //well, I guess this means I couldn't kill anything. Or put the enemy in check. And the enemy didn't have anything interesting to do
        //I guess I should just push a pawn or something
        for(Piece piece:pieces){
            if(piece.getType()==PieceType.PAWN){
                if(piece.getValidDestinationSet(board).size()>0){
                    return new Move(piece,piece.getValidDestinations(board)[0]);
                }
            }
        }
        //What!?!? No Pawns? guess I'll just move the first thing that comes to mind.
        for(Piece piece:pieces){
            if(piece.getValidDestinations(board).length>0){
                //providing that doesn't put my king in danger
                Board newBoard = board.copy();
                newBoard.movePiece(new Move(piece,piece.getValidDestinations(board)[0]));
                if(!newBoard.isCheck(this, enemy)){
                    return new Move(piece,piece.getValidDestinations(board)[0]);
                }
            }
        }
        //Oh no! I can make no moves that can save me from imminent death. Better hope for a miracle!
        for(Piece p:pieces){
            if(p.getValidDestinations(board).length>0){
                return new Move(p,p.getValidDestinations(board)[0]);
            }
        }
        //a miracle happened! (if it made it here)
        return null;
    }

}
\$\endgroup\$
  • \$\begingroup\$ Does running itself as the enemy help the score? \$\endgroup\$ – proud haskeller Sep 5 '14 at 12:12
  • \$\begingroup\$ Not really, but it looks cool! It doesn't change the scores much, but that might also be because of the lack of resemblance of other bots to my own. \$\endgroup\$ – Stretch Maniac Sep 6 '14 at 14:58
8
\$\begingroup\$

Three Move Monte

This guy looks at the next three moves (mine,yours,mine) and picks the move that gives the highest score. If there are more than 60 available moves, it will just choose a random 60 on each step. Of course, if any single move (out of all of them, not the chosen 60) will end the game, I'll take it immediately.

To score a board, I give each piece a base value. It's then modified by the piece's mobility, how many (and which) pieces it threatens, and how many pieces threaten it.

Of course, mobile kings are not necessarily good in the early game, so I special case the values for them a bit.

This runs fairly quickly, and can finish a game with the current crop in 3-4 seconds. It looks like there's room to bump it up a couple moves if need be.

update:

  • adding scoring for "control the center" in early game
  • special case king scores
  • fixed a double-scoring bug in move simulation
package player;

import java.util.*;
import pieces.*;
import controller.*;

public class ThreeMoveMonte extends Player{
    final static int TOSSES = 60;
    Random rand = new Random();

    @Override
    public Move getMove(Board board, Player them){
        List<Move> moves = getMoves(board, getTeam(), 0);
        for(Move move : moves)
            if(gameOver(apply(board, move)))
                return move;

        moves = getMoves(board, getTeam(), TOSSES);
        int highest = Integer.MIN_VALUE;
        Move best = moves.get(0);
        for(Move move : moves){
            Board applied = apply(board, move);
            Move oBest = getBestMove(applied, getOpponent(getTeam()), 0);
            applied = apply(applied, oBest);
            if(!gameOver(applied)){
                Move lBest = getBestMove(applied, getTeam(), TOSSES);
                Board lApplied = apply(applied, lBest);
                int score = eval(lApplied, getTeam());
                if(score > highest){
                    best = move;
                    highest = score;
                }
            }
        }
        return best;
    }

    boolean gameOver(Board board){
        Field[][] fields = board.getFields();
        int kings = 0;
        for(int x=0;x<fields.length;x++)
            for(int y=0;y<fields[x].length;y++){
                Piece p = fields[x][y].getPiece();
                if(p!=null&&p.getType().equals(PieceType.KING))
                    kings++;
            }
        return kings==2?false:true;
    }

    Move getBestMove(Board board, Color color, int breadth){
        int highest = Integer.MIN_VALUE;
        Move best = null;
        List<Move> moves = getMoves(board, color, breadth);
        for(Move move : moves){
            Board applied = apply(board, move);
            int score = eval(applied, color);
            if(score > highest){
                best = move;
                highest = score;
            }
        }
        return best;
    }

    List<Move> getMoves(Board board, Color color, int breadth){
        List<Move> moves = new ArrayList<Move>();
        Set<Piece> pieces = getPiecesOfColor(board, color);
        for(Piece piece : pieces){
            Set<Point> points = piece.getValidDestinationSet(board);
            for(Point point : points){
                moves.add(new Move(piece, point));
            }
        }
        Collections.shuffle(moves);
        if(breadth > 0)
            while(moves.size()>breadth)
                moves.remove(moves.size()-1);
        return moves;
    }

    Board apply(Board board, Move move){
        Board copy = board.copy();
        Piece piece = move.getPiece().copy();
        Point src = piece.getPos(); 
        Point dest = move.getDestination();
        if(piece.getType().equals(PieceType.PAWN)){
            if(piece.getTeam().equals(Color.WHITE)&&dest.getY()==7 || 
                    piece.getTeam().equals(Color.BLACK)&&dest.getY()==0)
                piece = new Queen(piece.getTeam(), piece.getPos());
        }
        piece.setPos(dest);
        copy.getFields()[src.getX()][src.getY()].setPiece(null);
        copy.getFields()[dest.getX()][dest.getY()].setPiece(piece);
        return copy;
    }

    int eval(Board board, Color color){
        int score = 0;
        List<Piece> mine = getPieces(board);
        Field[][] fields = board.getFields();
        for(Piece piece : mine){
            int value = getValueModified(board, piece);

            Set<Point> moves = piece.getValidDestinationSet(board);
            for(Point move : moves){
                int x = move.getX(),y=move.getY();
                if(fields[x][y].hasPiece()){
                    Piece other = fields[x][y].getPiece();
                    if(!other.getTeam().equals(getTeam()))
                        value += getValue(other) / (other.getType()==PieceType.KING ? 1 : 30); 
                }
                if(mine.size()>10)
                    value += (int)(8 - (Math.abs(3.5-x) + Math.abs(3.5-y)));
            }

            int attackerCount = getAttackers(board, piece, false).size();
            if(piece.getType()==PieceType.KING){
                if(attackerCount > 0)
                    value = -value;
            } else {
                for(int i=0;i<attackerCount;i++)
                    value = (value * 90) / 100;
            }
            score += value;
        }

        return score;
    }

    Set<Piece> getPiecesOfColor(Board board, Color color){
        Field[][] fields = board.getFields();
        Set<Piece> out = new HashSet<Piece>();
        for(int x=0;x<fields.length;x++){
            for(int y=0;y<fields[x].length;y++){
                Piece p = fields[x][y].getPiece();
                if(p!=null&&p.getTeam().equals(color))
                        out.add(p);
            }
        }
        return out;
    }

    Set<Piece> getAttackers(Board board, Piece piece, boolean all){
        Set<Piece> out = new HashSet<Piece>();
        Color color = piece.getTeam();
        Set<Piece> others = getPiecesOfColor(board, getOpponent(color));
        if(all)
            others.addAll(getPiecesOfColor(board, color));
        for(Piece other : others){
            if(other.getValidDestinationSet(board).contains(piece.getPos()))
                out.add(other);
        }
        return out;
    }

    Color getOpponent(Color color){
        return color.equals(Color.BLACK)?Color.WHITE:Color.BLACK;
    }

    int[] pieceValues = {100, 500, 300, 320, 880, 1500};
    int getValue(Piece piece){
        return pieceValues[piece.getType().ordinal()];
    }

    int[] maxMoves = {3, 14, 8, 13, 27, 8};
    int getValueModified(Board board, Piece piece){
        int moves = piece.getValidDestinationSet(board).size();
        double value = getValue(piece)*.9;
        double mod = getValue(piece)*.1*((double)moves/maxMoves[piece.getType().ordinal()]);
        if(piece.getType()==PieceType.KING)
            if(getPieces(board).size()>10)
                mod = -mod;

        return (int)(value + mod);
    }
}
\$\endgroup\$
  • \$\begingroup\$ Cool! You could use color.opposite() instead of getOpponent() ;) \$\endgroup\$ – CommonGuy Sep 4 '14 at 15:24
  • \$\begingroup\$ @Manu Didn't notice that method to be honest. I wrote most of this yesterday before the controller was updated, so there may be some other helper methods I could use instead of trying to get around the lack of visibility now :p \$\endgroup\$ – Geobits Sep 4 '14 at 15:34
  • \$\begingroup\$ @Manu Updated, should be back on top again for now :) \$\endgroup\$ – Geobits Sep 5 '14 at 19:30
5
\$\begingroup\$

AlphaBeta

Sorry, for having only morphed and fused code from other internet sources into this JAVA code. But it beats all other opponents (including PieceMaker) ... so far.

  • No move ordering.
  • No quiescence search.
  • No position evaluation.
  • Just raw brute force of alpha beta search.
  • Uses iterative deepening only for time management.

And sorry, for playing so machine boring.

package player;

import java.util.Random;
import controller.*;

public class AlphaBeta extends Player {
    private static final int INFINITY = Integer.MAX_VALUE;
    private static final int MAXTIME = 1800; // max time for evaluation
    private static final Random random=new Random();
    private static int seed=1;

    private long time; // time taken this turn
    private int iterativeDepth;
    private Player myOpponent;
    private int best, candidate;

    @Override
    public Move getMove(Board root, Player min) {
        time=System.currentTimeMillis();
        seed++; myOpponent=min; best=0;
        iterative_deepening(root);
        return allMoves(root, this)[best];
    }

    private void iterative_deepening(Board root) {
        try {
            for (iterativeDepth = 2;; iterativeDepth++) {
                alphaBeta(root, -INFINITY, +INFINITY, iterativeDepth, this, myOpponent);
                best=candidate;
            }
        } catch (InterruptedException e) {}
    }

    //http://chessprogramming.wikispaces.com/Alpha-Beta
    private int alphaBeta(Board root, int alpha, int beta, int d, Player max, Player min) throws InterruptedException {
        if ((System.currentTimeMillis() - time) > MAXTIME)  throw new InterruptedException();
        if (d==0 || root.getKing(max) == null) return evaluate(root, d);
        Move[] allMoves = allMoves(root, max);
        Move move;
        for (int m=0; (move = allMoves[m])!=null; m++) {
            Board board = root.copy();
            board.movePiece(move);
            int score = -alphaBeta(board, -beta, -alpha, d - 1, min, max);
            if (score >= beta)
                return beta; // fail hard beta-cutoff
            if (score > alpha) {
                alpha = score; // alpha acts like max in MiniMax
                if (d == iterativeDepth) candidate = m;
            }
        }
        return alpha;
    }

    private int evaluate(Board board, int d) {
        int minmax=2*((iterativeDepth-d)&1)-1;
        int value = 0, king=0;
        Field[][] field = board.getFields();
        for (int x = 0; x < 8; x++) {
            for (int y = 0; y < 8; y++) {
                Piece piece = field[x][y].getPiece();
                if (piece==null) continue;

                int sign=(piece.getTeam()==getTeam())?-minmax:minmax;
                switch (piece.getType()) {
                case PAWN:      value += 1*sign; break;
                case KNIGHT:    value += 3*sign; break;
                case BISHOP:    value += 3*sign; break;
                case ROOK:      value += 5*sign; break;
                case QUEEN:     value += 9*sign; break;
                case KING:      king  += (100-(iterativeDepth-d))*sign; break;
                default: // value += 0;
                }
            }
        }
        return king==0?value:king;
    }

    private Move[] allMoves(Board board, Player player) {
        random.setSeed(seed);
        Move[] move = new Move[200];
        int m=0;
        for (Piece piece : player.getPieces(board)) {
            for (Point point: piece.getValidDestinationSet(board)) {
                // shuffle
                int r=random.nextInt(++m);
                move[m-1]=move[r];
                move[r]=new Move(piece.copy(), point);
            }
        }
        return move;
    }       
}
\$\endgroup\$
5
\$\begingroup\$

Not an answer, but a simulation to help

I added a new class: GamePanel and edited Game and Controller

It isn't very pretty...yet. Did you know Unicode had chess characters!?!? (totally awesome!)
By the way, you need UTF-8 for these characters to show. It worked for me, but not sure how it will work on other operating systems.

Fixed end of games bug (thanks to tim for pointing that out).

GamePanel:

import java.awt.BorderLayout;
import java.awt.Dimension;
import java.awt.FlowLayout;
import java.awt.Font;
import java.awt.Graphics;
import java.awt.event.MouseEvent;
import java.awt.event.MouseListener;
import java.util.ArrayList;

import javax.swing.JButton;
import javax.swing.JFrame;
import javax.swing.JPanel;

public class GamePanel extends JPanel{
    private static final long serialVersionUID = 1L;
    JFrame container;
    Board currentBoard;
    Game currentGame;
    ArrayList<Game> games;
    public GamePanel(ArrayList<Game> Games){
        games = Games;
        currentGame = games.get(0);
        currentBoard = currentGame.allBoards.get(0);
        container = new JFrame();
        container.setSize(new Dimension(500,500));
        container.setMinimumSize(new Dimension(150,150));
        this.setMinimumSize(new Dimension(150,150));
        JButton skipButton = new JButton("skip game");
        skipButton.addMouseListener(new MouseListener(){
            @Override
            public void mouseClicked(MouseEvent arg0) {
                nextGame();
            }
            @Override
            public void mouseEntered(MouseEvent arg0) {
                // TODO Auto-generated method stub

            }
            @Override
            public void mouseExited(MouseEvent arg0) {
                // TODO Auto-generated method stub

            }
            @Override
            public void mousePressed(MouseEvent arg0) {
                // TODO Auto-generated method stub

            }
            @Override
            public void mouseReleased(MouseEvent arg0) {
                // TODO Auto-generated method stub

            }

        });
        JButton undoButton = new JButton("go back");
        undoButton.addMouseListener(new MouseListener(){
            @Override
            public void mouseClicked(MouseEvent e) {
                unStep();
            }

            @Override
            public void mouseEntered(MouseEvent e) {
                // TODO Auto-generated method stub

            }
            @Override
            public void mouseExited(MouseEvent e) {
                // TODO Auto-generated method stub

            }
            @Override
            public void mousePressed(MouseEvent e) {
                // TODO Auto-generated method stub

            }
            @Override
            public void mouseReleased(MouseEvent e) {
                // TODO Auto-generated method stub

            }

        });
        JButton continueButton = new JButton("continue");
        undoButton.setSize(40,40);
        skipButton.setSize(40,40);
        continueButton.setSize(40,40);
        continueButton.addMouseListener(new MouseListener(){
            @Override
            public void mouseClicked(MouseEvent arg0) {
                step();
            }
            @Override
            public void mouseEntered(MouseEvent arg0) { 
            }
            @Override
            public void mouseExited(MouseEvent arg0) {  
            }
            @Override
            public void mousePressed(MouseEvent arg0) {     
            }
            @Override
            public void mouseReleased(MouseEvent arg0) {    
            }
        });
        JPanel buttonPanel = new JPanel();
        buttonPanel.setLayout(new FlowLayout());
        buttonPanel.add(continueButton);
        buttonPanel.add(undoButton);
        buttonPanel.add(skipButton);
        container.setLayout(new BorderLayout());
        container.getContentPane().add(this,BorderLayout.CENTER);
        container.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        container.getContentPane().add(buttonPanel,BorderLayout.NORTH);
        container.setTitle("White: " + currentGame.players[0].getClass().getSimpleName() 
                + " vs "+ "Black: " + currentGame.players[1].getClass().getSimpleName());
        container.setVisible(true);
        container.invalidate();
        container.repaint();
    }
    private void unStep(){
        if(currentBoard!=currentGame.allBoards.get(0)){
            currentBoard=currentGame.allBoards.get(currentGame.allBoards.indexOf(currentBoard)-1);
        }
        container.invalidate();
        container.repaint();
    }
    private void unGame(){
        if(currentGame != games.get(0)){
            currentGame = games.get(games.indexOf(currentGame)-1);
            currentBoard = currentGame.allBoards.get(0);
        }
        container.invalidate();
        container.repaint();
    }
    private void step(){
        if(currentGame.allBoards.indexOf(currentBoard)==currentGame.allBoards.size()-1){
            nextGame();
        }
        else{
            currentBoard = currentGame.allBoards.get(currentGame.allBoards.indexOf(currentBoard)+1);
        }
        container.invalidate();
        container.repaint();
    }
    private void nextGame(){
        container.setTitle("White: " + currentGame.players[0].getClass().getSimpleName() 
                + " vs "+ "Black: " + currentGame.players[1].getClass().getSimpleName());
        if(currentGame != games.get(games.size()-1)){
            currentGame = games.get(games.indexOf(currentGame)+1);
        }
        else{
            //games complete
            container.dispose();
        }
        currentBoard = currentGame.allBoards.get(0);
        container.invalidate();
        container.repaint();
    }
    @Override
    public void paintComponent(Graphics g){
        if(getWidth()>150 && getHeight() > 150){
        int leftBounds,topBounds,width,height;
        topBounds = 50;
        leftBounds = 50;
        if(getWidth() > getHeight()){
            width = (int) (getHeight()-100);
            height = (int) (getHeight()-100);
        }
        else{
            width = (int) (getWidth()-100);
            height = (int) (getWidth()-100);
        }
        //draw grid
        java.awt.Color dark = new java.awt.Color(128, 78, 41);
        java.awt.Color light = new java.awt.Color(250, 223, 173);
        Field[][] feilds = currentBoard.getFields();
        for(int x = leftBounds; x < leftBounds+width-width/8; x+=width/8){
            for(int y = topBounds; y < topBounds+height-height/8; y+=height/8){
                int xPos = (int)Math.round(((double)(x-leftBounds)/(double)width)*8);
                int yPos = (int)Math.round(((double)(y-topBounds)/(double)height)*8);
                String piece = "";
                java.awt.Color stringColor = java.awt.Color.black;
                if(feilds[xPos][yPos].hasPiece()){
                    piece = getPiece(feilds[xPos][yPos].getPiece());
                    if(feilds[xPos][yPos].getPiece().getTeam()==Color.WHITE){stringColor = java.awt.Color.WHITE;}
                }
                if(yPos % 2 == 1){
                    if(xPos % 2 == 1){
                        g.setColor(dark);
                        g.fillRect(x, y, width/8, height/8);
                    }
                    else{
                        g.setColor(light);
                        g.fillRect(x, y, width/8, height/8);
                    }
                }
                else{
                    if(xPos % 2 == 1){
                        g.setColor(light);
                        g.fillRect(x, y, width/8, height/8);
                    }
                    else{
                        g.setColor(dark);
                        g.fillRect(x, y, width/8, height/8);
                    }
                }
                g.setColor(java.awt.Color.black);
                g.setFont(new Font(Font.SANS_SERIF, Font.BOLD, width/8));
                g.drawString(piece, x, y+width/8);
            }
        }
        }

    }
    public String getPiece(Piece p){
        if(p.getTeam() == Color.WHITE){
            if(p.getType() == PieceType.BISHOP){return "\u2657";}
            if(p.getType() == PieceType.PAWN){return "\u2659";}
            if(p.getType() == PieceType.KING){return "\u2654";}
            if(p.getType() == PieceType.QUEEN){return "\u2655";}
            if(p.getType() == PieceType.ROOK){return "\u2656";}
            if(p.getType() == PieceType.KNIGHT){return "\u2658";}
        }
        else{
            if(p.getType() == PieceType.BISHOP){return "\u265D";}
            if(p.getType() == PieceType.PAWN){return "\u265F";}
            if(p.getType() == PieceType.KING){return "\u265A";}
            if(p.getType() == PieceType.QUEEN){return "\u265B";}
            if(p.getType() == PieceType.ROOK){return "\u265C";}
            if(p.getType() == PieceType.KNIGHT){return "\u265E";}
        }
        return p.toString();
    }

}

Game:

import java.util.ArrayList;

public class Game {
    private static final int MAX_TURNS_WITHOUT_CAPTURES = 100; //=50, counts for both teams
    private static final int MAX_MILLISECONDS = 2000;
    private Board board;
    Player[] players = new Player[2];
    private int turnsWithoutCaptures = 0;
    private boolean draw = false;
    ArrayList<Board> allBoards = new ArrayList<Board>();

    public Game(Player player1, Player player2) {
        board = new Board();
        board.initialize();
        players[0] = player1;
        players[0].setTeam(Color.WHITE);
        players[1] = player2;
        players[1].setTeam(Color.BLACK);
        allBoards.add(board.copy());
    }
    int run() {
        int i = 0;
        while (!gameOver()) {
            if (!turnAvailable(players[i])) {
                draw = true;
            } else {
                makeTurn(players[i], players[(i+1) % 2]);
                i = (i + 1) % 2;
            }
        }
        if (loses(players[0]) && !loses(players[1])) {
            return Controller.LOSE_POINTS;
        } else if (loses(players[1]) && !loses(players[0])) {
            return Controller.WIN_POINTS;
        } else {
            return Controller.DRAW_POINTS;
        }
    }

    private boolean loses(Player player) {
        if (player.isDisqualified() || board.getKing(player) == null) {
            return true;
        }
        return false;
    }

    // player can make a turn
    private boolean turnAvailable(Player player) {
        for (Piece piece : player.getPieces(board)) {
            if (piece.getValidDestinationSet(board).size() > 0) {
                return true;
            }
        }
        return false;
    }

    private void makeTurn(Player player, Player enemy) {
        player.setCheck(board.isCheck(player, enemy));
        enemy.setCheck(board.isCheck(enemy, player));
        try {
            long start = System.currentTimeMillis();

            Move move = player.getMove(board.copy(), enemy);
            if ((System.currentTimeMillis() - start) > MAX_MILLISECONDS) {
                player.setDisqualified();
            }
            if (move.isValid(board, player)) {
                if (board.movePiece(move) || move.getPiece().getType() == PieceType.PAWN) {
                    turnsWithoutCaptures = 0;
                } else {
                    turnsWithoutCaptures++;
                }
            } else {
                player.setDisqualified(); //invalid move
            }
        } catch (Exception e) {
            player.setDisqualified();
            e.printStackTrace();
            System.out.println("Exception while moving " + player);
        }
        allBoards.add(board.copy());
    }
    public boolean gameOver() {
        for (Player player : players) {
            if (player.isDisqualified() || board.getKing(player) == null
                    || turnsWithoutCaptures >= MAX_TURNS_WITHOUT_CAPTURES || draw) {
                return true;
            }
        }
        return false;
    }
}

Controller:

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;

import players.*;

public class Controller {
    public static final int WIN_POINTS = 3;
    public static final int DRAW_POINTS = 1;
    public static final int LOSE_POINTS = 0;
    private static final int GAMES_PER_PAIR = 10;
    private final Class[] classes = {StretchPlayer.class,TestPlayer.class};
    private final Map<Class<? extends Player>, Integer> scores = new HashMap<Class<? extends Player>, Integer>();

    public static void main(String... args) {
        new Controller().generateResult();
    }

    public Controller() {
        for (Class player : classes) {
            scores.put(player, 0);
        }
    }
    ArrayList<Game> games = new ArrayList<Game>();
    private void generateResult() {

        for (int i = 0; i < classes.length - 1; i++) {
            for (int j = i + 1; j < classes.length; j++) {
                for (int k = 0; k < GAMES_PER_PAIR; k++) {
                    runGame(classes[i], classes[j], k>=GAMES_PER_PAIR);
                }
            }
        }
        GamePanel panel = new GamePanel(games);
        printScores();
    }

    private void runGame(Class class1, Class class2, boolean switchSides) {
        if (switchSides) { //switch sides
            Class tempClass = class2;
            class2 = class1;
            class1 = tempClass;
        }
        try {
            Player player1 = (Player) class1.newInstance();
            Player player2 = (Player) class2.newInstance();
            Game game = new Game(player1, player2);
            games.add(game);
            int result = game.run();
            addResult(class1, result, false);
            addResult(class2, result, true);
        } catch (Exception e) {
            System.out.println("Error in game between " + class1 + " and " + class2);
        }
    }

    private void addResult(Class player, int result, boolean reverse) {
        if (reverse) {
            if (result == WIN_POINTS) {
                result = LOSE_POINTS;
            } else if (result == LOSE_POINTS) {
                result = WIN_POINTS;
            }
        }
        int newScore = scores.get(player) + result;
        scores.put(player, newScore);
    }

    private void printScores() {
        int bestScore = 0;
        Class currPlayer = null;
        int place = 1;

        while (scores.size() > 0) {
            bestScore = 0;
            currPlayer = null;
            for (Class player : scores.keySet()) {
                int playerScore = scores.get(player);
                if (scores.get(player) >= bestScore) {
                    bestScore = playerScore;
                    currPlayer = player;
                }
            }
            System.out.println(String.format("%02d", place++) + ") " + currPlayer + ": " + bestScore);
            scores.remove(currPlayer);
        }
    }
}
\$\endgroup\$
  • \$\begingroup\$ Thanks, this is pretty neat. Just two thinks: You forgot to remove the SimulationListener, and if there are no more games an exception is thrown. And I would've put white at the bottom, but I guess your way works as well :) \$\endgroup\$ – tim Sep 6 '14 at 19:34
4
\$\begingroup\$

DontThinkAhead

This 'AI' doesn't like thinking ahead. If it sees that it can catch an enemy piece, it will do so immediately. If it cannot, it will just move a piece at random.

It is slightly better than SimplePlayer and TestPlayer and I mainly wrote it to get a feel for the controller code and have something to test against.

package player;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Random;

import controller.*;
/**
 * Thinking ahead is hard, so lets not do it.
 */
public class DontThinkAhead extends Player {

    @Override
    public Move getMove(Board board, Player enemy) {
        List<Move> moves = new ArrayList<>();
        List<Piece> pieces = this.getPieces(board);
        for (Piece piece : pieces) {
            Point[] destinations = piece.getValidDestinations(board);
            for (Point point : destinations) {
                moves.add(new Move(piece, point));
            }
        }

        List<Node> ratedMoves = new ArrayList<>();
        for (Move move : moves) {
            Point dest = move.getDestination();
            Field destField = board.getFields()[dest.getX()][dest.getY()];

            if (destField.hasPiece()) {
                int rating = 0;
                PieceType type = destField.getPiece().getType();
                switch (type) {
                case PAWN:
                    rating = 1;
                    break;
                case KNIGHT:
                    rating = 3;
                    break;
                case BISHOP:
                    rating = 3;
                    break;
                case ROOK:
                    rating = 5;
                    break;
                case QUEEN:
                    rating = 9;
                    break;
                case KING:
                    rating = 9999;
                    break;
                default:
                    rating = 0;
                }
                ratedMoves.add(new Node(move, rating));
            }           
        }

        if (!ratedMoves.isEmpty()) {
            Collections.sort(ratedMoves, new ComparatorNode());
            return ratedMoves.get(0).getMove();
        } else {
            // no good move possible, return random move
            return moves.get(new Random().nextInt(moves.size()));
        }
    }

    private class Node {
        private Move move;
        private int rating;

        public Node(Move move, int rating) {
            this.move = move;
            this.rating = rating;
        }

        public int getRating() {
            return rating;
        }

        public Move getMove() {
            return move;
        }
    }

    private class ComparatorNode implements Comparator<Node> {

        @Override
        public int compare(Node t, Node t1) {
            return t1.getRating() - t.getRating();
        }
    }
}
\$\endgroup\$
2
\$\begingroup\$

Cheese

Yes, you read it right. A block of cheese, playing chess.

Algorithm

The cheese checks all possible moves and scores them accordingly. He (the cheese, and yes it's a male) uses the following guide to scoring his choices :

Eating

  • King = OVER 9000!!!!!!!!!!
  • Queen = 18
  • Rook = 10
  • Bishop = 6
  • Knight = 6
  • Pawn = 2

Risk of getting eaten

  • King = UNDER -9000!!!!!!!!!!!
  • Queen = -16
  • Rook = -8
  • Bishop = -5
  • Knight = -5
  • Pawn = 0

Chance of eating next turn

  • King = 5
  • Queen = 3
  • Rook = 2
  • Bishop = 1
  • Knight = 1
  • Pawn = 0

Pending Improvements

  • NOT ENOUGH SWAG (going to check on this possibility soon)
  • I checked my time and it seems that I run in 0-1 milliseconds. I think I can be more aggressive with my algorithms then.

Bugs fixed

  • When checking for scores for possible targets to eat, I counted my own units. Now, I'm only scoring if I can eat an enemy piece.
package player;

import pieces.Queen;
import controller.*;

public class Cheese extends Player {
    private final int[] eatingPriorities = { 9999, 18, 10, 6, 6, 2, 0 };
    private final int[] gettingEatenPriorities = { -9000, -16, -8, -5, -5, 0, 0 };
    private final int[] chanceToEatPriorities = {5,3,2,1,1,0,0};

    @Override
    public Move getMove(Board board, Player enemy) {
        int maxScore = -10000;
        Move bestMove = null;

        int score = 0;

        Field[][] field = board.getFields();
        Field fieldDest;

        // get best move
        for (Piece myPiece : this.getPieces(board)) {
            for (Point possibleDest : myPiece.getValidDestinationSet(board)) {
                score=0;
                fieldDest = field[possibleDest.getX()][possibleDest.getY()];

                //if you're eating an enemy piece, SCORE!
                if(fieldDest.hasPiece() && fieldDest.getPiece().getTeam()!=this.getTeam()){
                    score += eatingPriorities[getPriorityIndex(fieldDest.getPiece().getType())];
                }
                score+=getAftermoveRisk(board, enemy, new Move(myPiece, possibleDest));
                if (maxScore < score) {
                    maxScore = score;
                    bestMove = new Move(myPiece,possibleDest);
                }
            }
        }

        return bestMove;
    }

    private int getAftermoveRisk(Board board, Player enemy, Move move){
        int gettingEatenRisk=0, chanceToEatScore=0;
        Field[][] simField;
        Field field;
        Board simBoard = board.copy();

        simField = simBoard.getFields();
        this.simulateMovePiece(simField, move);

        //gettingEaten risk
        for (Piece enemyPiece : enemy.getPieces(simBoard)) {
            for (Point possibleDest : enemyPiece.getValidDestinationSet(simBoard)) {
                field = simField[possibleDest.getX()][possibleDest.getY()];

                //if it's my piece that's in the line of fire, increase gettingEatenRisk
                if(field.hasPiece() && field.getPiece().getTeam()==this.getTeam()){
                    gettingEatenRisk += gettingEatenPriorities[getPriorityIndex(field.getPiece().getType())];
                }
            }
        }

        //chanceToEat score
        for (Piece myPiece : this.getPieces(simBoard)) {
            for (Point possibleDest : myPiece.getValidDestinationSet(simBoard)) {
                field = simField[possibleDest.getX()][possibleDest.getY()];

                //if it's their piece that's in the line of fire, increase chanceToEatScore
                if(field.hasPiece() && field.getPiece().getTeam()!=this.getTeam()){
                    chanceToEatScore += chanceToEatPriorities[getPriorityIndex(field.getPiece().getType())];
                }
            }
        }

        return gettingEatenRisk + chanceToEatScore;
    }

    // Copied and edited from Board.movePiece
    public void simulateMovePiece(Field[][] fields, Move move) {
        Piece piece = move.getPiece();
        Point dest = move.getDestination();
        if (!dest.isOutside()) {
            // upgrade pawn
            if (piece.getType() == PieceType.PAWN && (dest.getY() == 0 || dest.getY() == 7)) {
                fields[dest.getX()][dest.getY()].setPiece(new Queen(piece.getTeam(), dest));
            } else {
                fields[dest.getX()][dest.getY()].setPiece(piece);
            }
            //remove piece on old field
            fields[piece.getPos().getX()][piece.getPos().getY()].setPiece(null);
        }
    }

    private int getPriorityIndex(PieceType type) {
        int index = 0;
        switch (type) {
        case KING:
            index = 0;
            break;
        case QUEEN:
            index = 1;
            break;
        case ROOK:
            index = 2;
            break;
        case BISHOP:
            index = 3;
            break;
        case KNIGHT:
            index = 4;
            break;
        case PAWN:
            index = 5;
            break;
        default:
            index = 6;
        }
        return index;
    }

}
\$\endgroup\$
  • \$\begingroup\$ With this code, it seems like you'll gladly lose your queen to take a pawn. That doesn't seem quite right. \$\endgroup\$ – overactor Sep 10 '14 at 8:59
  • \$\begingroup\$ Yeah, I'm still tweaking around the priority values. Thanks for bringing that up though. :) \$\endgroup\$ – Mark Gabriel Sep 10 '14 at 9:04
2
\$\begingroup\$

SimplePlayer

This player just makes sure he uses valid moves, but otherwise is pretty dumb.

package player;

import java.util.List;
import controller.*;

public class SimplePlayer extends Player {

    @Override
    public Move getMove(Board board, Player enemy) {
        //get all pieces of this player
        List<Piece> pieces = this.getPieces(board);
        for (Piece piece : pieces) {
            Point[] destinations = piece.getValidDestinations(board);
            if (destinations.length > 0) {
                return new Move(piece, destinations[0]);
            }
        }

        //should never happen, because the game is over then
        return null;
    }

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