war

war.java

import java.io.*;
import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * User: pradeepnayak
 * Date: 28/03/14
 * Time: 3:27 PM
 * To change this template use File | Settings | File Templates.
 */
public class war {
    public static final int UNION_PLAYER = 1;
    public static final int CONFEDERACY_PLAYER = -1;
    public static final int NO_OCCUPANCY = 0;
    private Graph g = new Graph();
    private int cutOffDepth;
    PrintWriter resultFile;
    PrintWriter logFile;


    public war(int cutOffDepth, BufferedReader mapFile, BufferedReader initFile) throws IOException {
        this.cutOffDepth = cutOffDepth;
        readNodes(initFile);
        assignEdges(mapFile);
    }

    public static void main(String[] args) throws IOException {
        int taskNumber = Integer.parseInt(args[1]);
        int cutOffDepth = Integer.parseInt(args[3]);

        BufferedReader mapFile = new BufferedReader(new FileReader(args[5]));
        BufferedReader initFile = new BufferedReader(new FileReader(args[7]));
        war w = new war(cutOffDepth, mapFile, initFile);
        w.logFile = new PrintWriter(new FileWriter(args[11]));
        w.resultFile = new PrintWriter(new FileWriter(args[9]));
        w.logFile.println("Player,Action,Destination,Depth,Value");
        Turn startingTurn = new Turn(0, new State(w.g, war.UNION_PLAYER), war.UNION_PLAYER, "N/A", "N/A");
        System.out.println(startingTurn);
        w.resultFile.println(startingTurn);
        switch (taskNumber) {
            case 1:
                w.minmaxTask(1, startingTurn);
                break;
            case 2:
                w.minmaxTask(startingTurn);
                break;
            case 3:
                w.alphaBetaPruningTask();
                break;
            case 4:
            default:
                w.resultFile.close();
                w.logFile.close();

                System.out.println("Error!");
                System.exit(-1);
        }
        w.resultFile.close();
        w.logFile.close();
    }

    private void minmaxTask(int cutOffDepth, Turn startingTurn) {
        State startState = new State(g, UNION_PLAYER);

        State currentState = startState;
        Turn currentTurn = startingTurn;
        Turn nextTurn = null;
        int currentDepth = 2;
        while (!currentState.isGameOver()) {
            for (Turn turn : currentState.nextTurns(currentTurn.turnNo)) {

                if (nextTurn == null) {
                    nextTurn = turn;
                } else {
                    if (maxValue(nextTurn, cutOffDepth - 1, currentDepth).utilValue > maxValue(turn, cutOffDepth - 1, currentDepth).utilValue) {
                        nextTurn = turn;
                    }
                }
            }
            currentState = nextTurn.s;
            currentTurn = nextTurn;
            System.out.println("Turn" + nextTurn);
            resultFile.println(nextTurn);
            nextTurn = null;
        }
        System.out.println("Minmax with cutoff depth " + cutOffDepth);
    }

    class TurnAndValue {

        Turn turn;
        double utilValue;

        public TurnAndValue(Turn turn, double utilValue) {
            this.turn = turn;
            this.utilValue = utilValue;
        }
    }

    private TurnAndValue minValue(Turn nextTurn, int depthsRemaining, int currentDepth) {
        if (terminalTest(nextTurn, depthsRemaining)) {
            System.out.println("TLOG: " + nextTurn.tlog(currentDepth));
            logFile.println(nextTurn.tlog(currentDepth));
            return new TurnAndValue(nextTurn, nextTurn.utilityValue());
        }

        double value = Double.POSITIVE_INFINITY;
        TurnAndValue result = null;

        for (Turn turn : nextTurn.s.nextTurns(nextTurn.turnNo)) {
            TurnAndValue turnAndValue = maxValue(turn, depthsRemaining - 1, currentDepth + 1);
            double newVal = turnAndValue.utilValue;
            if (value > newVal) {
                value = newVal;
                result = turnAndValue;
            }
        }
        System.out.println("TLOG: " + result.turn.tlog(currentDepth));
        //logFile.println(result.turn.tlog(currentDepth));

        return result;
    }

    private TurnAndValue maxValue(Turn nextTurn, int depthsRemaining, int currentDepth) {
        if (terminalTest(nextTurn, depthsRemaining)) {
            System.out.println("TLOG: " + nextTurn.tlog(currentDepth));
            logFile.println(nextTurn.tlog(currentDepth));
            return new TurnAndValue(nextTurn, nextTurn.utilityValue());
        }

        double value = Double.NEGATIVE_INFINITY;
        TurnAndValue result = null;
        for (Turn turn : nextTurn.s.nextTurns(nextTurn.turnNo)) {
            TurnAndValue turnAndValue = minValue(turn, depthsRemaining - 1, currentDepth + 1);
            double newVal = turnAndValue.utilValue;
            if (value < newVal) {
                value = newVal;
                result = turnAndValue;
            }
        }
        System.out.println("TLOG: " + result.turn.tlog(currentDepth));
        //logFile.println(result.turn.tlog(currentDepth));
        return result;
    }

    private boolean terminalTest(Turn nextTurn, int depthsRemaining) {
        return nextTurn.s.isGameOver() || depthsRemaining == 0;
    }

    private void minmaxTask(Turn startingTurn) {
        minmaxTask(cutOffDepth, startingTurn);
    }

    private void alphaBetaPruningTask() {
        System.out.println("alpha beta pruning");
    }


    private void assignEdges(BufferedReader mapFile) throws IOException {
        String str = null;
        while ((str = mapFile.readLine()) != null) {
            StringTokenizer tokenizer = new StringTokenizer(str, ",");
            String from = tokenizer.nextToken();
            String to = tokenizer.nextToken();
            g.addEdge(from, to);
        }
    }

    private void readNodes(BufferedReader initFile) throws IOException {
        String str = null;
        while ((str = initFile.readLine()) != null) {
            StringTokenizer tokenizer = new StringTokenizer(str, ",");
            String node = tokenizer.nextToken();
            double cost = Double.parseDouble(tokenizer.nextToken());
            int playerType = Integer.parseInt(tokenizer.nextToken());
            g.addNode(node, cost, playerType);
        }
    }
}

class Graph {

    Map<String, City> cities = new TreeMap<String, City>(new Comparator<String>() {
        @Override
        public int compare(String o1, String o2) {
            //so that we get in alphabetical order when we ask for list of cities
            return o1.compareTo(o2);
        }
    });

    public void addEdge(String from, String to) {
        City fromCity = cities.get(from);
        City toCity = cities.get(to);
        fromCity.addEdge(toCity);
        toCity.addEdge(fromCity);
    }

    public void addNode(String sourceNode, double cost, int occupiedBy) {
        City city = new City(sourceNode, cost, occupiedBy);
        city.resourcesQuantity = cost;
        city.occupiedBy = occupiedBy;
        cities.put(sourceNode, city);
    }


    public List<City> getCitiesOccupiedBy(int currentPlayer) {
        List<City> citiesOccupied = new ArrayList<City>();
        for (City c : cities.values())
            if (c.isOccupiedBy(currentPlayer))
                citiesOccupied.add(c);
        return citiesOccupied;
    }

    public Graph copy() {
        Graph copiedGraph = new Graph();
        for (String cityName : cities.keySet()) {
            City city = cities.get(cityName);
            copiedGraph.cities.put(cityName, city.copy());
        }
        return copiedGraph;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;

        Graph graph = (Graph) o;

        if (!cities.equals(graph.cities)) return false;

        return true;
    }

    @Override
    public int hashCode() {
        return cities.hashCode();
    }

    public Collection<City> getUnoccoupiedCities() {
        Collection<City> unoccupiedCities = new ArrayList<City>();
        for (String cityName : cities.keySet()) {
            City c = cities.get(cityName);
            if (!c.isOccupied())
                unoccupiedCities.add(c);
        }
        return unoccupiedCities;
    }

    public City getCity(String city) {
        return cities.get(city);
    }

    @Override
    public String toString() {
        return "Graph" +
                cities;
    }
}

class City {

    public String cityName;
    public double resourcesQuantity;
    public int occupiedBy;


    City(String name) {
        this.cityName = name;
    }

    private Collection<OutgoingEdge> edges = new TreeSet<OutgoingEdge>(new Comparator<OutgoingEdge>() {
        @Override
        public int compare(OutgoingEdge o1, OutgoingEdge o2) {
            //this forces list to store in alphabetical order so that when we ask for it, it gives in alphabetical order always.
            return o1.destination.compareTo(o2.destination);
        }
    });

    public City(String cityName, double resourcesQuantity, int occupiedBy) {
        this.cityName = cityName;
        this.resourcesQuantity = resourcesQuantity;
        this.occupiedBy = occupiedBy;
    }


    public void addEdge(City otherCity) {
        edges.add(new OutgoingEdge(otherCity.cityName));
    }

    public boolean isOccupiedBy(int playerType) {
        return (this.occupiedBy == playerType);
    }


    public List<City> getNeighbouringUnoccupiedCities(Graph graph) {
        List<City> cities = new ArrayList<City>();
        for (OutgoingEdge edge : edges) {
            City outgoingCity = graph.cities.get(edge.destination);
            if (!outgoingCity.isOccupied())
                cities.add(outgoingCity);
        }
        return cities;
    }

    public List<City> getNeighbouringCitiesOccupiedBy(Graph graph, int player) {
        List<City> cities = new ArrayList<City>();
        for (OutgoingEdge edge : this.edges) {
            City outgoingCity = graph.cities.get(edge.destination);
            if (outgoingCity.isOccupiedBy(player))
                cities.add(outgoingCity);
        }
        return cities;
    }

    public boolean isOccupied() {
        return occupiedBy != war.NO_OCCUPANCY;
    }

    public City copy() {
        City city = new City(this.cityName, this.resourcesQuantity, this.occupiedBy);
        for (OutgoingEdge edge : edges) {
            city.edges.add(edge.copy());
        }
        return city;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;

        City city = (City) o;

        if (!cityName.equals(city.cityName)) return false;

        return true;
    }

    @Override
    public int hashCode() {
        return cityName.hashCode();
    }

    @Override
    public String toString() {
        return "{" +
                "'" + cityName + '\'' +
                "," + occupiedBy +
                '}';
    }
}

class OutgoingEdge {
    String destination;

    public OutgoingEdge(String destination) {
        this.destination = destination;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;

        OutgoingEdge that = (OutgoingEdge) o;

        if (!destination.equals(that.destination)) return false;

        return true;
    }

    @Override
    public int hashCode() {
        return destination.hashCode();
    }

    public OutgoingEdge copy() {
        return new OutgoingEdge(destination);
    }
}

class Turn {
    int turnNo;
    State s;
    String action;
    private String destination;
    private int playerNo;

    Turn(int turnNo, State s, int player, String action, String destination) {
        this.turnNo = turnNo;
        this.s = s;
        this.playerNo = player;
        this.action = action;
        this.destination = destination;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("TURN = " + turnNo);
        sb.append("\nPlayer = " + State.playerName(playerNo));
        sb.append("\nAction = " + action);
        sb.append("\nDestination = " + destination);
        sb.append("\n" + s.citysInfoFor(war.UNION_PLAYER));
        sb.append("\n" + s.citysInfoFor(war.CONFEDERACY_PLAYER));
        sb.append("\n----------------------------------------------");
        return sb.toString();
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;

        Turn turn = (Turn) o;

        if (turnNo != turn.turnNo) return false;
        if (action != null ? !action.equals(turn.action) : turn.action != null) return false;
        if (destination != null ? !destination.equals(turn.destination) : turn.destination != null) return false;
        if (State.playerName(playerNo) != null ? !State.playerName(playerNo).equals(State.playerName(turn.playerNo)) : State.playerName(turn.playerNo) != null)
            return false;
        if (s != null ? !s.equals(turn.s) : turn.s != null) return false;

        return true;
    }

    @Override
    public int hashCode() {
        int result = turnNo;
        result = 31 * result + (s != null ? s.hashCode() : 0);
        result = 31 * result + (State.playerName(playerNo) != null ? State.playerName(playerNo).hashCode() : 0);
        result = 31 * result + (action != null ? action.hashCode() : 0);
        result = 31 * result + (destination != null ? destination.hashCode() : 0);
        return result;
    }

    double utilityValue() {
        return s.getScoreForPlayer(s.currentPlayer);
    }

    public String tlog(int depth) {
        return State.playerName(playerNo) + "," + action + "," + destination + "," + depth + "," + s.getScoreForPlayer(playerNo);
    }
}

class State {
    Graph g;
    int currentPlayer;

    public State(Graph g, int player) {
        this.g = g;
        this.currentPlayer = player;
    }

    public List<Turn> nextTurns(int turnNo) {
        List<Turn> states = new ArrayList<Turn>();

        // 1.force march
        for (City c : g.getCitiesOccupiedBy(currentPlayer))
            for (City unoccupiedCity : c.getNeighbouringUnoccupiedCities(g)) {
                Turn t = new Turn(turnNo + 1,
                        stateAfterForceMarchInto(unoccupiedCity),
                        currentPlayer,
                        "Force March",
                        unoccupiedCity.cityName
                );
                if (!states.contains(t))
                    states.add(t);
            }

        // 2.paratroop drop
        for (City unoccupiedCity : g.getUnoccoupiedCities()) {
            Turn t = new Turn(turnNo + 1,
                    stateAfterParatroopInto(unoccupiedCity),
                    (currentPlayer),
                    "Paratroop Drop",
                    unoccupiedCity.cityName
            );
            if (!states.contains(t))
                states.add(t);
        }

        return states;
    }

    public static String playerName(int player) {
        switch (player) {
            case war.UNION_PLAYER:
                return "Union";
            case war.CONFEDERACY_PLAYER:
                return "Confederacy";
        }
        return null;
    }

    State stateAfterParatroopInto(City city) {
        State s = copy();
        s.getCity(city).occupiedBy = s.currentPlayer;
        s.switchPlayer();

        return s;
    }

    State stateAfterForceMarchInto(City city) {
        State s = copy();
        s.getCity(city).occupiedBy = s.currentPlayer;

        List<City> forceMarchedCites = city.getNeighbouringCitiesOccupiedBy(s.g, otherPlayer());
        for (City c : forceMarchedCites) {
            s.getCity(c).occupiedBy = s.currentPlayer;
        }

        s.switchPlayer();
        return s;
    }

    private City getCity(City c) {
        return g.cities.get(c.cityName);
    }

    private void switchPlayer() {
        this.currentPlayer = otherPlayer();
    }

    private int otherPlayer() {
        switch (currentPlayer) {
            case war.UNION_PLAYER:
                return war.CONFEDERACY_PLAYER;
            case war.CONFEDERACY_PLAYER:
                return war.UNION_PLAYER;
            default:
                throw new RuntimeException("No other player when current player is zero");
        }
    }

    private State copy() {
        State copiedState = new State(g, currentPlayer);
        copiedState.currentPlayer = this.currentPlayer;
        copiedState.g = g.copy();
        return copiedState;
    }

    public double getScoreForPlayer(int i) {
        return getResourceCountForPlayer(i) - getResourceCountForPlayer(-i);

    }

    private double getResourceCountForPlayer(int currentPlayer) {
        int val = 0;
        for (Map.Entry<String, City> entry : g.cities.entrySet()) {
            City city = entry.getValue();
            if (city.occupiedBy == currentPlayer)
                val += city.resourcesQuantity;
        }
        return val;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;

        State state = (State) o;

        if (currentPlayer != state.currentPlayer) return false;
        if (!g.equals(state.g)) return false;

        return true;
    }

    @Override
    public int hashCode() {
        int result = g.hashCode();
        result = 31 * result + currentPlayer;
        return result;
    }

    public boolean isGameOver() {
        return nextTurns(0).isEmpty();
    }

    public String citysInfoFor(int playerNumber) {
        //        Union,{E,G,H,J,K,M},46.0
        StringBuilder sb = new StringBuilder();
        switch (playerNumber) {
            case war.UNION_PLAYER:
                sb.append("Union,{");
                break;
            case war.CONFEDERACY_PLAYER:
                sb.append("Confederacy,{");
                break;
        }
        if (this.g.getCitiesOccupiedBy(playerNumber).size() > 0) {
            for (City c : this.g.getCitiesOccupiedBy(playerNumber))
                sb.append(c.cityName + ",");
            sb.deleteCharAt(sb.length() - 1);
        }

        sb.append("}," + this.getResourceCountForPlayer(playerNumber));
        return sb.toString();  //To change body of created methods use File | Settings | File Templates.
    }
}

class State1 {
    String destination;
    String action;
    String player;
    Graph currGraph = new Graph();
    public int union_cost;
    public int confideracy_cost;

    public State1(String action, Graph currGraph) {
        this.action = action;
        this.currGraph = currGraph;
        this.destination = "N/A";
        this.player = "N/A";
    }

    public int getConfederacyVal() {
        int tmpval = 0;
        for (Map.Entry<String, City> myTempObj : currGraph.cities.entrySet()) {
            if (myTempObj.getValue().occupiedBy == war.CONFEDERACY_PLAYER) {
                tmpval += myTempObj.getValue().resourcesQuantity;
            }
        }
        return tmpval;
    }

    public int getUnionVal() {
        int tmpval = 0;
        for (Map.Entry<String, City> myTempObj : currGraph.cities.entrySet()) {
            if (myTempObj.getValue().occupiedBy == 1) {
                tmpval += myTempObj.getValue().resourcesQuantity;
            }
        }
        return tmpval;
    }

}

/*class MinMax {
    int cutOffDepth;
    State1 myState;

    public MinMax(State1 currState) {
        this.cutOffDepth = 1;
        this.myState = currState;
    }

    public List<State1> getAllPossibleMoves(State1 currState) {
        ArrayList<State1> listOfMoves = new ArrayList<State1>();
        //get all confederacy moves
        if (currState.player == "Union") {
            //try force march
            for (Map.Entry<String, City> obj : currState.currGraph.cities.entrySet()) {
                //if the position is empty and the neighbour is confederacy
                if (obj.getValue().occupiedBy == 0) {
                    //check if you can do a force march
                    if (obj.getValue().isOccupiedBy(this, war.CONFEDERACY_PLAYER)) {
                        State1 tmpState = currState;
                        City tempCity = tmpState.currGraph.cities.get(obj.getKey());
                        for (OutgoingEdge e : tempCity.getOutgoingEdges()) {
                            if (e.destination.occupiedBy == 1) {
                                e.destination.occupiedBy = war.CONFEDERACY_PLAYER;
                            }
                        }
                        tmpState.destination = obj.getKey();
                        tmpState.action = "Force March";
                        tmpState.player = "Confederacy";
                        listOfMoves.add(tmpState);
                    }
                }

            }
            // Paratroop Drop
            for (Map.Entry<String, City> obj : currState.currGraph.cities.entrySet()) {
                if (obj.getValue().occupiedBy == 0) {
                    //do a paratroop drop
                    State1 tmpState = currState;
                    tmpState.currGraph.cities.get(obj.getKey()).occupiedBy = war.CONFEDERACY_PLAYER;
                    tmpState.action = "Paratroop Drop";
                    tmpState.destination = obj.getKey();
                    tmpState.player = "Confederacy";
                    listOfMoves.add(tmpState);
                }

            }

        }
        //get all union moves.
        else {
            //try force march
            for (Map.Entry<String, City> obj : currState.currGraph.cities.entrySet()) {
                //if the position is empty and the neighbour is confederacy
                if (obj.getValue().occupiedBy == 0) {
                    //check if you can do a force march
                    if (obj.getValue().isOccupiedBy(this, 1)) {
                        State1 tmpState = currState;
                        City tempCity = tmpState.currGraph.cities.get(obj.getKey());
                        for (OutgoingEdge e : tempCity.getOutgoingEdges()) {
                            if (e.destination.occupiedBy == war.CONFEDERACY_PLAYER) {
                                e.destination.occupiedBy = 1;
                            }
                        }
                        tmpState.destination = obj.getKey();
                        tmpState.action = "Force March";
                        tmpState.player = "Union";
                        listOfMoves.add(tmpState);
                    }
                }

            }
            // Paratroop Drop
            for (Map.Entry<String, City> obj : currState.currGraph.cities.entrySet()) {
                if (obj.getValue().occupiedBy == 0) {
                    //do a paratroop drop
                    State1 tmpState = currState;
                    tmpState.currGraph.cities.get(obj.getKey()).occupiedBy = war.CONFEDERACY_PLAYER;
                    tmpState.action = "Paratroop Drop";
                    tmpState.destination = obj.getKey();
                    tmpState.player = "Union";
                    listOfMoves.add(tmpState);
                }

            }

        }

        return listOfMoves;
    }

    public int eval(State1 currState) {
        return currState.union_cost - currState.confideracy_cost;
    }

}           */