Alfa-Beta algoritmus pro Walight UI I HW

alfabeta.java

package conquest.bot.playground;

import conquest.bot.state.*;
import conquest.game.Player;
import conquest.game.world.Continent;
import conquest.game.world.Region;

import java.util.*;

interface IApplicable {
    void apply(GameState state);
}

class PCommand extends PlaceCommand implements IApplicable {

    public PCommand(Region region, int armies) {
        super(region, armies);
    }
}

class MCommand extends MoveCommand implements IApplicable {

    public MCommand(Region from, Region to, int armies) {
        super(from, to, armies);
    }
}

class ACommand extends AttackCommand implements IApplicable {

    public ACommand(Region from, Player fromOwner, Region to, Player toOwner, int armies, int attackersCasaulties,
                    int defendersCasaulties) {
        super(from, fromOwner, to, toOwner, armies, attackersCasaulties, defendersCasaulties);
    }
}

class Timeout {
    private boolean timeout = false;

    public void setTimeout() {
        timeout = true;
    }

    public boolean getTimeout() {
        return timeout;
    }
}

class AlphaBetaResult {
    final public int score;
    public Object commands;

    public AlphaBetaResult(int score, Object commands) {
        this.score = score;
        this.commands = commands;
    }
}

class AlphaBetaUtils {
    public static AlphaBetaResult zero = new AlphaBetaResult(Integer.MIN_VALUE, null);

    public static int evaluateState(GameState.PlayerState pl, GameState.PlayerState op) {
        return (pl.regions.size() * 10 + pl.continents.size()) * 1000000 + pl.totalArmies; //-
                //((op.regions.size() * 10 + op.continents.size()) * 1000000 + op.totalArmies);
    }

    public static boolean hasOnlyMyNeighbours(GameState.RegionState from, Player player) {
        for (GameState.RegionState region : from.neighbours) {
            if (!region.owned(player)) return false;
        }
        return true;
    }

    public static List<GameState.RegionState> getBorder(Map<Region, GameState.RegionState> regions, Player player) {
        List<GameState.RegionState> ret = new ArrayList<>();

        for (GameState.RegionState rs : regions.values()) {
            if (hasOnlyMyNeighbours(rs, player))
                continue;

            ret.add(rs);
        }

        return ret;
    }

    public static int getPreferredContinentPriority(Continent continent) {
        switch (continent) {
            case Europe:
                return 1;
            case Africa:
                return 2;
            case Australia:
                return 3;
            case Asia:
                return 4;
            case North_America:
                return 5;
            case South_America:
                return 6;
            default:
                return 7;
        }
    }

    public static float probabilityOfResult(int attackers, int defenders, int defSur, int attSur) {
        if (defSur != 0 && attSur != 0) return 0f;

        int dCau = defenders - defSur;
        int aCau = attackers - attSur;

        // causalities
        // d, a
        // 0, 0 = 12%  --> 0        %
        // 1, 0 = 18%  --> 18+27/11 %
        // 0, 1 = 28%  --> 28+42/11 %
        // 1, 1 = 42%  --> 42+63/11 %

        float d = (18f + 27f / 11f) / 100f;
        float a = (28f + 42f / 11f) / 100f;
        float b = (42f + 63f / 11f) / 100f;

        float prob = 1.0f;

        if (dCau > aCau) {
            prob *= Math.pow(d, dCau - aCau);
            dCau = aCau;
        } else if (aCau > dCau) {
            prob *= Math.pow(a, aCau - dCau);
            aCau = dCau;
        }

        // Now number of causalities are same on both sides

        float p = 0.0f;
        float pp = 1.0f;
        for (int i = 0; i <= aCau; i++) { // number of single causalities
            pp *= Math.pow(d, i);
            pp *= Math.pow(a, i);
            pp *= Math.pow(b, aCau - i);
            p += pp;
            pp = 0.0f;
        }

        prob *= p;

        return prob;
    }
}

/**
 * Created by jakub on 8/26/2018.
 */
public class AlphaBeta {

    ///////////////////////
    /// CHOOSE REGIONS  ///
    ///////////////////////

    public static List<ChooseCommand> chooseRegions(List<Region> choosable) {
        int m = 6;

        // SORT PICKABLE REGIONS ACCORDING TO THE PRIORITY
        Collections.sort(choosable, new Comparator<Region>() {
            @Override
            public int compare(Region o1, Region o2) {
                int priority1 = AlphaBetaUtils.getPreferredContinentPriority(o1.continent);
                int priority2 = AlphaBetaUtils.getPreferredContinentPriority(o2.continent);
                return priority1 - priority2;
            }
        });

        // REMOVE CONTINENT WE DO NOT WANT
        while (choosable.size() > m) choosable.remove(choosable.size() - 1);

        // CREATE COMMANDS
        List<ChooseCommand> result = new ArrayList<ChooseCommand>(choosable.size());
        for (Region region : choosable) {
            result.add(new ChooseCommand(region));
        }

        return result;
    }

    ///////////////////////////
    ///  ALPHA BETA SEARCH  ///
    ///////////////////////////

    private static AlphaBetaResult moveArmy(final GameState state, final int depth, int alpha, int beta,
                                            final boolean max, final Map<Region, Integer> regions,
                                            final Timeout timeout, final int time) {
        if (timeout.getTimeout()) {
            AlphaBetaResult res = AlphaBetaUtils.zero;
            res.commands = new LinkedList<MoveCommand>();
            return res;
        }

        if (depth == 0)
            return new AlphaBetaResult(AlphaBetaUtils.evaluateState(state.me, state.opp), new LinkedList<MoveCommand>());

        boolean end = true;
        for (Region reg : regions.keySet()) {
            if (regions.get(reg) > 1) {
                end = false;
                break;
            }
        }

        if (end) {
            AlphaBetaResult res;

            //if (time == 0) {
            //System.out.println("ending");
            res = placeArmies(state, depth, alpha, beta, true, timeout);
            //} else {
            //    res = moveArmies(state, depth, alpha, beta, !max, timeout, 0);
            //}

            res.commands = new LinkedList<MoveCommand>();
            return res;
        }

        AlphaBetaResult tmp = placeArmies(state, depth - 1, alpha, beta, true, timeout);
        int value = max ? Integer.MIN_VALUE : Integer.MAX_VALUE;

        if (max) {
            value = Math.max(value, tmp.score);
            alpha = Math.max(alpha, value);
        } else {
            value = Math.min(value, tmp.score);
            beta = Math.min(beta, value);
        }

        LinkedList<MoveCommand> moves = new LinkedList<>();

        if (alpha >= beta)
            return new AlphaBetaResult(value, moves);

        GameState.PlayerState player = max ? state.me : state.opp;
        GameState.PlayerState opponent = !max ? state.me : state.opp;

        for (Region region : regions.keySet()) {
            if (regions.get(region) == 1)
                continue;

            for (Region neighbour : region.getNeighbours()) {
                if (timeout.getTimeout()) {
                    AlphaBetaResult res = AlphaBetaUtils.zero;
                    res.commands = new LinkedList<MoveCommand>();
                    return res;
                }

                boolean my = player.regions.containsKey(neighbour);
                int na = state.region(neighbour).armies;
                int ra = regions.get(region);

                if (my) // Moving with army
                {
                    int armies = ra - 1;
                    if (timeout.getTimeout()) {
                        AlphaBetaResult res = AlphaBetaUtils.zero;
                        res.commands = new LinkedList<MoveCommand>();
                        return res;
                    }

                    MCommand cmd = new MCommand(region, neighbour, armies);

                    cmd.apply(state);
                    regions.put(region, ra - armies);

                    AlphaBetaResult result = moveArmy(state, depth - 1, alpha, beta, max, regions, timeout, time);

                    if (max) {
                        value = Math.max(value, result.score);
                        alpha = Math.max(alpha, value);
                    } else {
                        value = Math.min(value, result.score);
                        beta = Math.min(beta, value);
                    }

                    if (value == result.score) {
                        moves = (LinkedList<MoveCommand>) result.commands;
                        moves.addFirst(cmd);
                    }

                    //regions.put(region, ra);
                    cmd.revert(state);

                    if (alpha >= beta)
                        break;
                } else // Attacking with army
                {
                    regions.put(region, 1);

                    if(na >= (6 * ra) / 7)
                        continue;

                    int armies = ra - 1;
                    int a = (int) (na * 7.0 / 6.0);
                    int c = a > armies ? armies : a;
                    int d = c == a ? na : (int) (armies * (6.0 / 7.0));
                    if (d == na && c == armies)
                        d = na - 1;

                    //float score = 0;

                    /*
                    for (int mySur = 1; mySur <= armies; mySur++) {
                        if (timeout.getTimeout()) {
                            AlphaBetaResult res = AlphaBetaUtils.zero;
                            res.commands = new LinkedList<MoveCommand>();
                            return res;
                        }

                        float prob = AlphaBetaUtils.probabilityOfResult(armies, na, 0, mySur);
                        ACommand cmd = new ACommand(region, player.player, neighbour, opponent.player, armies, armies - mySur, na);

                        cmd.apply(state);

                        score += prob * AlphaBetaUtils.evaluateState(state.me, state.opp);

                        cmd.revert(state);
                    }

                    for (int oppSur = 1; oppSur <= na; oppSur++) {
                        if (timeout.getTimeout()) {
                            AlphaBetaResult res = AlphaBetaUtils.zero;
                            res.commands = new LinkedList<MoveCommand>();
                            return res;
                        }

                        float prob = AlphaBetaUtils.probabilityOfResult(armies, na, oppSur, 0);
                        ACommand cmd = new ACommand(region, player.player, neighbour, opponent.player, armies, armies, na - oppSur);

                        cmd.apply(state);

                        score += prob * AlphaBetaUtils.evaluateState(state.me, state.opp);

                        cmd.revert(state);
                    }
                    */
                    ACommand cmd = new ACommand(region, player.player, neighbour, opponent.player, armies, c, d);

                    cmd.apply(state);
                    AlphaBetaResult saved = moveArmy(state, depth - 1, alpha, beta, max, regions, timeout, time);

                    if (timeout.getTimeout()) {
                        AlphaBetaResult res = AlphaBetaUtils.zero;
                        res.commands = new LinkedList<MoveCommand>();
                        return res;
                    }

                    cmd.revert(state);

                    int score = saved.score;

                    if (max) {
                        value = Math.max(value, (int) score);
                        alpha = Math.max(alpha, value);
                    } else {
                        value = Math.min(value, (int) score);
                        beta = Math.min(beta, value);
                    }

                    if (value == score) {
                        moves = (LinkedList<MoveCommand>) saved.commands;
                        moves.addFirst(new MCommand(region, neighbour, armies));
                    }

                    //regions.put(region, ra);
                }

                if (alpha >= beta)
                    break;
            }

            if (alpha >= beta)
                break;
        }

        return new AlphaBetaResult(value, moves);
    }

    private static AlphaBetaResult moveArmies(final GameState state, final int depth, final int alpha, final int beta,
                                              final boolean max, final Timeout timeout, int time) {
        if (timeout.getTimeout()) {
            AlphaBetaResult res = AlphaBetaUtils.zero;
            res.commands = new LinkedList<MoveCommand>();
            return res;
        }

        if (depth == 0)
            return new AlphaBetaResult(AlphaBetaUtils.evaluateState(state.me, state.opp), new LinkedList<MoveCommand>());


        GameState.PlayerState player = max ? state.me : state.opp;

        Map<Region, Integer> regions = new HashMap<>();
        for (Region reg : player.regions.keySet()) {
            int armies = state.region(reg).armies;
            if (armies > 1)
                regions.put(reg, armies);
        }

        return moveArmy(state, depth, alpha, beta, max, regions, timeout, time);
    }

    public static List<MoveCommand> moveArmies(final GameState state, final Timeout timeout) {
        List<MoveCommand> best = new LinkedList<>();

        for (int i = 1; !timeout.getTimeout(); i++) {
            AlphaBetaResult result = moveArmies(state, i, Integer.MIN_VALUE, Integer.MAX_VALUE, true, timeout, 1);

            if (timeout.getTimeout()) {
                System.out.println("Timeout - reached depth " + i);
                if (best.isEmpty())
                    best = (List<MoveCommand>) result.commands;
            } else
                best = (List<MoveCommand>) result.commands;
        }

        System.out.println("completed");
        return best;
    }

    private static AlphaBetaResult placeSoldier(final GameState state, final int depth, int alpha, int beta,
                                                final boolean max, final List<GameState.RegionState> regions,
                                                final int soldiers, final Timeout timeout) {
        if (timeout.getTimeout()) {
            AlphaBetaResult res = AlphaBetaUtils.zero;
            res.commands = new LinkedList<PlaceCommand>();
            return res;
        }

        if (soldiers == 0) {
            //AlphaBetaResult result = max
            //        ? placeArmies(state, depth, alpha, beta, !max, timeout)
            //        : moveArmies(state, depth - 1, alpha, beta, !max, timeout, 1);
            AlphaBetaResult result = moveArmies(state, depth-1, alpha, beta, true, timeout, 1);

            return new AlphaBetaResult(result.score, new LinkedList<PlaceCommand>());
        }

        int value = max ? Integer.MIN_VALUE : Integer.MAX_VALUE;

        LinkedList<PlaceCommand> placings = new LinkedList<>();

        for (GameState.RegionState reg : regions) {
            if (timeout.getTimeout()) {
                AlphaBetaResult res = AlphaBetaUtils.zero;
                res.commands = new LinkedList<PlaceCommand>();
                return res;
            }

            PCommand cmd = new PCommand(reg.region, 1);

            cmd.apply(state);

            AlphaBetaResult result = placeSoldier(state, depth, alpha, beta, max, regions, soldiers - 1, timeout);

            if (max) {
                value = Math.max(value, result.score);
                alpha = Math.max(alpha, value);
            } else {
                value = Math.min(value, result.score);
                beta = Math.min(beta, value);
            }

            if (value == result.score) {
                placings = (LinkedList<PlaceCommand>) result.commands;
                placings.addFirst(cmd);
            }

            state.revert(cmd);

            if (alpha >= beta)
                break;
        }

        return new AlphaBetaResult(value, placings);
    }

    private static AlphaBetaResult placeArmies(final GameState state, final int depth, final int alpha, final int beta,
                                               final boolean max, final Timeout timeout) {
        if (timeout.getTimeout()) {
            AlphaBetaResult res = AlphaBetaUtils.zero;
            res.commands = new LinkedList<PlaceCommand>();
            return res;
        }

        if (depth == 0)
            return new AlphaBetaResult(AlphaBetaUtils.evaluateState(state.me, state.opp), new LinkedList<PlaceCommand>());

        GameState.PlayerState player = max ? state.me : state.opp;

        List<GameState.RegionState> regions = AlphaBetaUtils.getBorder(player.regions, player.player);
        Collections.sort(regions, new Comparator<GameState.RegionState>() {

            private int score(GameState.RegionState state, GameState.PlayerState p1, GameState.PlayerState p2) {
                int score = 0;

                for (GameState.RegionState neigh : state.neighbours)
                    if (neigh.owner == p2)
                        score += 100;
                    else if (neigh.owner != p1)
                        score++;

                return score;
            }

            @Override
            public int compare(GameState.RegionState o1, GameState.RegionState o2) {
                GameState.PlayerState p1 = max ? state.me : state.opp;
                GameState.PlayerState p2 = max ? state.opp : state.me;

                int score1 = score(o1, p1, p2);
                int score2 = score(o2, p1, p2);

                return score1 - score2;
            }
        });

        return placeSoldier(state, depth, alpha, beta, max, regions, player.placeArmies, timeout);
    }

    public static List<PlaceCommand> placeArmies(final GameState state, final Timeout timeout) {
        List<PlaceCommand> best = new LinkedList<>();
        List<PlaceCommand> prev;

        for (int i = 1; !timeout.getTimeout(); i++) {
            AlphaBetaResult result = placeArmies(state, i, Integer.MIN_VALUE, Integer.MAX_VALUE, true, timeout);

            if (timeout.getTimeout()) {
                System.out.println("Timeout - reached depth " + i);
                if (best.isEmpty())
                    best = (List<PlaceCommand>) result.commands;
            } else {
                prev = best;
                best = (List<PlaceCommand>) result.commands;
                if (best.size() < prev.size())
                    best = prev;
            }
        }

        return best;
    }
}