Turnamen Catur

24

Ini adalah catur-KOTH dengan aturan yang disederhanakan (karena catur itu sendiri sudah rumit, memainkannya melalui program sederhana tidak membuatnya lebih mudah). Saat ini terbatas pada java (versi 8), tetapi membuat kelas wrapper tidak terlalu sulit (jika seseorang ingin melakukan ini).

Papan catur

Papan catur dalam program kontrol menggunakan versi notasi numerik ICCF yang dimodifikasi . Berbasis nol, artinya bidang kiri bawah adalah posisi 0,0, sedangkan bidang kanan atas adalah posisi 7,7.

Aturan yang dimodifikasi

  • Orang yang lewat akan diabaikan.
  • Castling tidak mungkin.
  • Aturan Fifty-move berlaku secara otomatis (artinya permainan berakhir imbang).
  • Promosi pion ke ratu terjadi secara otomatis ketika mereka mencapai ujung papan.
  • Jika seorang pemain membutuhkan lebih dari 2 detik untuk bergerak, ia akan kehilangan permainan.
  • Mengembalikan langkah yang tidak valid akan menghasilkan kekalahan dalam permainan.
  • Untuk menang, Anda harus menangkap raja musuh . Tidak cukup hanya dengan skakmat musuh.
  • Ini juga memungkinkan Anda untuk memindahkan raja Anda ke bidang di mana musuh dapat menangkap Anda.
  • Putih memulai permainan.
  • Putih ditempatkan "di bagian bawah" bidang (y = 0), hitam terletak di bagian atas (y = 7).
  • Mengakses sumber daya lain selain bot Anda (internet, file, bot lain, ...) dilarang.

Mencetak gol

  • Menang memberi Anda 3 poin, satu imbang 1 poin dan kehilangan 0 poin.
  • Setiap kiriman akan bermain melawan kiriman lainnya 10 kali (5 kali putih, 5 sebagai hitam).

Pengendali

Anda dapat menemukan program kontrol di github .
Untuk berpartisipasi, Anda harus membuat kelas di dalamplayerpaket dan harus berupa subkelas dariPlayer. Sebagai contoh, lihat TestPlayer (yang juga akan dimasukkan dalam penilaian).

Setiap game, controller akan membuat instance baru dari pemain Anda. Kemudian, setiap belokan Anda harus mengembalikan gerakan. Kontroler memberi Anda salinan Dewan , yang berisi larik Bidang 8x8 . Bidang berisi informasi tentang warnanya, posisinya, dan bagian di atasnya, jika ada.
Pengontrol juga memberi Anda informasi tentang pemain musuh, seperti isCheckdan getPieces(). Memanggil getMove()musuh akan membuat Anda didiskualifikasi.

Papan angka

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

Kontes ini terbatas pada java karena membuat membuat jawaban lebih mudah, karena Anda dapat mengambil untung dari metode yang disediakan oleh controller. Namun, jika seseorang membuat pembungkus, saya akan menyertakan bahasa lain.

CommonGuy
sumber
2
Ini juga mengubah kebuntuan menjadi kerugian :(
Geobits
2
you can profit from the methods provided by the controller: Ini tidak sepenuhnya benar. Sebagian besar metode yang berguna adalah paket pribadi, sehingga tidak dapat digunakan. Maukah Anda menambahkan simulateMovemetode ke Boardkelas, yang mengembalikan salinan papan dengan langkah yang diberikan diterapkan? Dengan begitu, kita tidak harus menulis sendiri (atau menyalin-rekatkan seluruh kode Anda ^^).
tim
4
Aturan kedua adalah fantastis. Alih-alih menjadi bot optimal catur yang keras, tantangannya adalah seperti: Membuat bot catur terbaik yang tidak terlalu cerdas
Mark Gabriel
2
@ Geobits saya memperbarui controller. Sebagian besar metode yang berguna publicsekarang;)
CommonGuy
3
Saya hampir cenderung menulis bot yang melempar Throwableatau bahkan Errorkarena itu akan menghindari kehilangan. Saya akan menyebutnya BoardTipper.
Ingo Bürk

Jawaban:

4

AlphaBetaPV

AlphaBetaPV adalah singkatan dari Alpha Beta dengan Principal Variation (ini bukan pencarian variasi-utama). Dengan hanya beberapa baris yang dijalin ke dalam kode AlphaBeta.java, itu mengalahkan AlphaBeta.java. Dan sekali lagi, maaf, untuk hanya mengubah dan menggabungkan kode dari sumber internet lain ke dalam kode JAVA ini.

  • Variasi utama disimpan dan digunakan untuk prioritas perpindahan paling sederhana untuk mempercepat pemutusan alpha beta:
    • sementara memperdalam berulang dan
    • untuk langkah selanjutnya.
  • Evaluasi posisi sederhana:
    • Jumlah gerakan masing-masing pihak memiliki (tingkat kebebasan) untuk mendukung pembukaan.
    • Promosi gadai untuk mendukung permainan akhir.
  • Masih tidak ada pencarian diam.

Masih bermain membosankan.

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;
    }
}
Bob Genom
sumber
11

PieceTaker

Kode sedikit berantakan, tetapi tidak berfungsi. Saat ini ia menang melawan semua pemain lain, bahkan jika itu hanya diberikan 400ms, bukan 2000ms yang diizinkan.

Saya menggunakan pemangkasan alpha beta dengan pendalaman berulang untuk memastikan bahwa AI tidak melampaui batas waktu. Heuristik saat ini sangat sederhana (hanya bagian yang hilang / diambil yang dipertimbangkan; bukan posisi di papan tulis, dll).

Di masa depan saya mungkin juga menambahkan heuristik pembunuh dan menyortir gerakan sebelum memeriksanya.

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();
        }
    }
}
tim
sumber
Bot ini tangguh!
Mark Gabriel
@MarkGabriel terima kasih :) jujur, saya tidak terlalu senang dengan itu pada awalnya. Itu hanya bisa berpikir ke depan 2-4 gerakan, yang tidak cukup dalam banyak situasi. Saya memiliki versi yang ditingkatkan kalau saya tidak menyalin bidang tetapi membatalkan gerakan yang jauh lebih cepat, tapi itu buggy dan saya tidak bisa memperbaikinya :(
tim
11

StretchPlayer

Bot ini dimainkan sama seperti saya!

Ngomong-ngomong, aku mengerikan di catur.

Komentar menjelaskan apa yang sebenarnya dilakukannya. Ini seperti proses pemikiran saya.

Sebagai bonus tambahan, hajar semua bot lainnya dengan selisih yang cukup besar. (sejauh ini)

EDIT: sekarang memprediksi lawan dengan menjalankan dirinya sebagai musuh!

EDIT 2: Program membuat kesalahan dengan tidak benar-benar membunuh raja ketika terbuka lebar. Itu ditegur sesuai.

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

}
Regangkan Maniac
sumber
Apakah berlari sendiri sebagai musuh membantu skor?
haskeller bangga
Tidak juga, tapi kelihatannya keren! Itu tidak banyak mengubah skor, tetapi itu mungkin juga karena kurangnya kemiripan bot lain dengan saya.
Stretch Maniac
8

Tiga Pindahkan Monte

Orang ini melihat tiga gerakan berikutnya (milikku, milikmu, milikku) dan mengambil langkah yang memberikan skor tertinggi. Jika ada lebih dari 60 gerakan yang tersedia, itu hanya akan memilih 60 acak pada setiap langkah. Tentu saja, jika ada satu gerakan (dari semuanya, bukan 60 yang dipilih) yang akan mengakhiri permainan, saya akan segera menerimanya.

Untuk mencetak papan, saya memberi masing-masing nilai dasar. Ini kemudian dimodifikasi oleh mobilitas potongan itu, berapa banyak (dan mana) potongan yang mengancamnya, dan berapa banyak potongan yang mengancamnya.

Tentu saja, raja seluler belum tentu bagus di awal permainan, jadi saya berikan nilai khusus untuk mereka.

Ini berjalan cukup cepat, dan dapat menyelesaikan game dengan hasil saat ini dalam 3-4 detik. Sepertinya ada ruang untuk menumbuhkannya jika perlu.

memperbarui:

  • menambahkan skor untuk "kontrol pusat" di awal pertandingan
  • skor raja kasus khusus
  • memperbaiki bug skor ganda dalam simulasi gerakan
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);
    }
}
Geobit
sumber
Keren! Anda bisa menggunakan color.opposite()bukannya getOpponent();)
CommonGuy
@ Manu Tidak melihat metode itu jujur. Saya menulis sebagian besar dari ini kemarin sebelum controller diperbarui, jadi mungkin ada beberapa metode pembantu lain yang bisa saya gunakan alih-alih mencoba menyiasati kurangnya visibilitas sekarang: p
Geobits
@ Manu Diperbarui, harus kembali ke atas lagi sekarang :)
Geobits
5

AlphaBeta

Maaf, hanya kode morf dan menyatu dari sumber internet lain ke dalam kode JAVA ini. Tapi itu mengalahkan semua lawan lain (termasuk PieceMaker) ... sejauh ini.

  • Tidak ada pemesanan bergerak.
  • Tidak ada pencarian ketenangan.
  • Tidak ada evaluasi posisi.
  • Hanya kekuatan kasar mentah dari pencarian alpha beta.
  • Menggunakan pendalaman berulang hanya untuk manajemen waktu.

Dan maaf, karena bermain jadi mesin membosankan.

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;
    }       
}
Bob Genom
sumber
5

Bukan jawaban, tetapi simulasi untuk membantu

Saya menambahkan kelas baru: GamePanel dan diedit Game and Controller

Itu tidak terlalu cantik ... belum. Tahukah Anda Unicode memiliki karakter catur!?!? (benar-benar hebat!)
Ngomong-ngomong, Anda perlu menampilkan UTF-8 agar karakter-karakter ini ditampilkan. Ini bekerja untuk saya, tetapi tidak yakin bagaimana ini akan bekerja pada sistem operasi lain.

Memperbaiki bug akhir game (terima kasih kepada tim karena telah menunjukkannya).

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

}

Permainan:

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

Pengendali:

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);
        }
    }
}
Regangkan Maniac
sumber
Terima kasih, ini cukup rapi. Hanya dua yang berpikir: Anda lupa menghapus SimulationListener, dan jika tidak ada lagi game pengecualian dilemparkan. Dan saya akan menempatkan putih di bagian bawah, tapi saya kira cara Anda juga bekerja :)
tim
4

DontThinkAhead

'AI' ini tidak suka berpikir ke depan. Jika melihat bahwa ia dapat menangkap bagian musuh, ia akan segera melakukannya. Jika tidak bisa, itu hanya akan memindahkan sepotong secara acak.

Itu sedikit lebih baik daripada SimplePlayerdan TestPlayerdan saya terutama menulisnya untuk merasakan kode pengontrol dan memiliki sesuatu untuk diuji.

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();
        }
    }
}
tim
sumber
2

Keju

Ya, Anda membacanya dengan benar. Satu blok keju, bermain catur.

Algoritma

Keju memeriksa semua gerakan yang mungkin dan memberi skor yang sesuai. Dia (keju, dan ya itu laki-laki) menggunakan panduan berikut untuk mencetak pilihan-pilihannya:

Makan

  • Raja = LEBIH DARI 9000 !!!!!!!!!!
  • Ratu = 18
  • Benteng = 10
  • Uskup = 6
  • Ksatria = 6
  • Gadai = 2

Risiko dimakan

  • King = UNDER -9000 !!!!!!!!!!!
  • Ratu = -16
  • Benteng = -8
  • Uskup = -5
  • Ksatria = -5
  • Gadai = 0

Peluang makan giliran berikutnya

  • Raja = 5
  • Ratu = 3
  • Benteng = 2
  • Uskup = 1
  • Ksatria = 1
  • Gadai = 0

Perbaikan yang Menunggu

  • TIDAK CUKUP SWAG (akan memeriksa kemungkinan ini segera)
  • Saya memeriksa waktu saya dan sepertinya saya berlari dalam 0-1 milidetik. Saya pikir saya bisa lebih agresif dengan algoritma saya.

Bug diperbaiki

  • Ketika memeriksa skor untuk kemungkinan target makan, saya menghitung unit saya sendiri. Sekarang, saya hanya mencetak gol jika saya bisa memakan sepotong musuh .
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;
    }

}
Mark Gabriel
sumber
Dengan kode ini, sepertinya Anda akan dengan senang hati kehilangan ratu Anda untuk mengambil pion. Sepertinya itu tidak benar.
overactor
Ya, saya masih mengutak-atik nilai prioritas. Terima kasih sudah membahasnya. :)
Mark Gabriel
2

SimplePlayer

Pemain ini hanya memastikan dia menggunakan gerakan yang valid, tetapi sebaliknya cukup bodoh.

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

}
CommonGuy
sumber