Friday, August 29, 2014

Dijkstra's Algorithm Implementation in Java

This program implements Dijkstra's algorithm for finding the shortest path to all vertices from the given source in a graph. The code is simple enough. I've added comments wherever necessary.

Graph used in this example:



Code:

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

class Node {

    boolean showMoreInfo = true;
    int distanceFromSource = 0;
    String name;
    public Map<Node, Integer> neighbors = new HashMap<>();

    Node(String name) {
        this.name = name;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("Node: ").append(name).append("\n");

        sb.append("Distance from source: ").append(distanceFromSource).append("\n");

        if (showMoreInfo) {
            sb.append("Neighbor nodes: \n");
            for (Node node : neighbors.keySet()) {
                sb.append(node.name).append("  Distance: ").append(this.neighbors.get(node)).append("\n");
            }

            sb.append("\n");
        }
        return sb.toString();
    }
}

public class DijkstrasAlgorithm {
    List<Node> nodes = new ArrayList<>(); 
    
    public void drawGraph() {
        Node s = new Node("s");

        //Two immediate (reachable) neighbors of Node s
        Node t = new Node("t");
        Node y = new Node("y");
        s.neighbors.put(t, 10);
        s.neighbors.put(y, 5);

        //One of the two immediate (reachable) neighbors of Node t
        Node x = new Node("x");
        t.neighbors.put(x, 1);
        t.neighbors.put(y, 2);

        y.neighbors.put(t, 3);
        y.neighbors.put(x, 9);

        //Last Node z (immediately reachable from x and y nodes)
        Node z = new Node("z");
        x.neighbors.put(z, 4);
        y.neighbors.put(z, 2);
        z.neighbors.put(x, 6);
        z.neighbors.put(s, 7);

        //Now add these to List<Node> nodes
        nodes.add(s);
        nodes.add(t);
        nodes.add(y);
        nodes.add(x);
        nodes.add(z);
    }

    private void initializeNodes(){
        for(Node node:nodes)
            node.distanceFromSource = Integer.MAX_VALUE;
        nodes.get(0).distanceFromSource = 0;
    }
    
    private void relax(Node previous, Node next){
        if(next.distanceFromSource>previous.distanceFromSource+previous.neighbors.get(next)){
            next.distanceFromSource = previous.distanceFromSource+previous.neighbors.get(next);
        }
    }
    
    private Node getMin(List<Node> nodes){
        int min = Integer.MAX_VALUE; 
        int minIndex = -1;
        for(int i=0;i<nodes.size();++i){
            if(nodes.get(i).distanceFromSource<min){
                min = nodes.get(i).distanceFromSource; 
                minIndex = i;
            }
        }
        return nodes.get(minIndex);
    }
    
    public void dijkstra(){
        List<Node> nodesCopy = new ArrayList<>();
        nodesCopy.addAll(nodes);
        
        while(!nodesCopy.isEmpty()){
            Node min = getMin(nodesCopy);
            
            Map<Node, Integer> neighbors = min.neighbors;
            for(Map.Entry<Node, Integer> me:neighbors.entrySet()){
                relax(min, me.getKey());
            }
            nodesCopy.remove(min);
        }
    }
    
    public static void main(String[] args){
        DijkstrasAlgorithm da = new DijkstrasAlgorithm();
        da.drawGraph();
        da.initializeNodes(); 
        da.dijkstra();
        
        System.out.println(da.nodes.size());
        for(Node node:da.nodes)
            System.out.println(node);
    }
}

Output:

Node: s
Distance from source: 0
Neighbor nodes:
t  Distance: 10
y  Distance: 5


Node: t
Distance from source: 8
Neighbor nodes:
x  Distance: 1
y  Distance: 2


Node: y
Distance from source: 5
Neighbor nodes:
x  Distance: 9
t  Distance: 3
z  Distance: 2


Node: x
Distance from source: 9
Neighbor nodes:
z  Distance: 4


Node: z
Distance from source: 7
Neighbor nodes:
x  Distance: 6
s  Distance: 7

Monday, August 25, 2014

Tic Tac Toe AI [ Minimax Algorithm ] with GUI using JavaFX [Tic Tac Toe][Artificial Intelligence][Minimax][Java][JavaFX]

I made this GUI for the TicTacToe AI: http://coderbots.blogspot.in/2014/08/minimax-algorithm-tic-tac-toe-ai-in.html. The GUI is written in JavaFX. You might wanna give it a shot and see if you can defeat the AI (not possible though).

Lamba Expressions (Java 8): http://coderbots.blogspot.in/2014/08/using-lambdas-java-8-java-8lambda.html

[Make sure you have JDK 8.0 Installed] If not, here's a link: http://www.oracle.com/technetwork/java/javase/downloads/jre8-downloads-2133155.html

Here's a link to a click and run JAR : http://www.mediafire.com/download/yktyrg2w8754yah/TicTacToe_v2.jar
[CSS and Image files included in the JAR. Just open it up with WinRAR, if you feel like seeing the CSS]

Screenshots:


Source [GUI]:

import java.util.Random;
import javafx.application.Application;
import javafx.geometry.Insets;
import javafx.geometry.Pos;
import javafx.scene.Scene;
import javafx.scene.control.Button;
import javafx.scene.control.Label;
import javafx.scene.image.Image;
import javafx.scene.image.ImageView;
import javafx.scene.layout.GridPane;
import javafx.stage.Stage;

/**
 *
 * @author Jatin Thakur
 */
class Turn {

    enum NextMove {

        O, X, E
    }
    NextMove next;
}

public class TicTacToeAIGUI extends Application {

    Board board = new Board();
    Turn boardTurn = new Turn();
    GridPane grid;
    Label cell1, cell2, cell3,
            cell4, cell5, cell6,
            cell7, cell8, cell9;
    Label[] cells;

    @Override
    public void start(Stage primaryStage) {

        Stage stage = new Stage();
        GridPane g = new GridPane();
        g.setId("firstDialog");
        g.setPadding(new Insets(20, 20, 20, 20));
        g.setVgap(20);
        g.setHgap(20);

        //First Dialog Labels and Buttons
        Label label = new Label("Who will play first?");
        Button IWillPlay = new Button("Lemme play first!");
        Button YouPlay = new Button("You're a legend! you play first!");
        g.add(label, 0, 0, 2, 1);
        g.add(IWillPlay, 0, 1, 1, 1);
        g.add(YouPlay, 1, 1, 1, 1);

        //Scene for the firstDialog
        Scene sc = new Scene(g, 450, 200);
        g.setAlignment(Pos.CENTER);
        sc.getStylesheets().addAll(this.getClass().getResource("firstDialog.css").toExternalForm());
        stage.setTitle("Choose turn");
        stage.setScene(sc);
        stage.setOnCloseRequest(e -> {
            System.exit(0);
        });

        //Board scene
        GridPane grid = new GridPane();
        cell1 = new Label();
        cell2 = new Label();
        cell3 = new Label();
        cell4 = new Label();
        cell5 = new Label();
        cell6 = new Label();
        cell7 = new Label();
        cell8 = new Label();
        cell9 = new Label();

        cells = new Label[]{cell1, cell2, cell3,
            cell4, cell5, cell6,
            cell7, cell8, cell9};

        for (Label cell : cells) {
            cell.setMinSize(128, 128);
            boolean isUsed = false;
            cell.setUserData(isUsed);
        }

        grid.addRow(0, cell1, cell2, cell3);
        grid.addRow(1, cell4, cell5, cell6);
        grid.addRow(2, cell7, cell8, cell9);

        grid.setAlignment(Pos.CENTER);
        grid.setMaxSize(800, 800);
        grid.setGridLinesVisible(true);
        grid.setId("board");

        boardTurn.next = Turn.NextMove.O;
        Image OPic = new Image(getClass().getResourceAsStream("O.png"));
        Image XPic = new Image(getClass().getResourceAsStream("X.png"));

        for (Label cell : cells) {

            cell.setOnMouseClicked(event -> {
                if (((boolean) cell.getUserData()) == false) {
                    cell.setGraphic(new ImageView(XPic));

                    int index = -1;
                    for (int i = 0; i < cells.length; ++i) {
                        if (cell == cells[i]) {
                            index = i;
                        }
                    }

                    board.placeAMove(new Point(index / 3, index % 3), 2);
                    board.displayBoard();
                    System.out.println("Placed a move at: (" + index / 3 + ", " + index % 3 + ")");
                    boolean mark = true;
                    int next = board.returnNextMove();

                    if (next != -1) {   //If the game isn't finished yet!   
                        int indexCell = next;

                        cells[indexCell].setGraphic(new ImageView(OPic));
                        cells[indexCell].setUserData(mark); //Used!
                        System.out.println("Computer has evaluated the next move! " + indexCell);
                        board.placeAMove(new Point(indexCell / 3, indexCell % 3), 1);
                        cell.setUserData(mark);
                    }

                    if (board.isGameOver()) {
                        Stage stage2 = new Stage();
                        GridPane g2 = new GridPane();
                        g2.setPadding(new Insets(20, 20, 20, 20));
                        g2.setVgap(20);
                        g2.setHgap(20);
                        Label label2 = new Label();
                        if (board.hasXWon()) {
                            label2.setText("You better learn to play first, kid!");
                            stage2.setTitle("You lost!");
                        } else {
                            label2.setText("You can't beat me, Stop trying!");
                            stage2.setTitle("It's a draw!");
                        }
                        g2.add(label2, 0, 0, 2, 1);
                        Button onceMore = new Button("Lemme play again!");
                        Button quit = new Button("I'm tired. I quit!");
                        g2.add(onceMore, 1, 1, 1, 1);
                        g2.add(quit, 2, 1, 1, 1);
                        onceMore.setOnMouseClicked(q -> {
                            primaryStage.close();
                            stage2.close();
                            board.resetBoard();
                            start(new Stage());
                        });

                        quit.setOnMouseClicked(q -> {
                            System.exit(0);
                        });
                        Scene scene = new Scene(g2);
                        scene.getStylesheets().addAll(this.getClass().getResource("result.css").toExternalForm());
                        stage2.setScene(scene);
                        stage2.setOnCloseRequest(q -> {
                            primaryStage.close();
                        });
                        stage2.show();
                    }
                }
            });
        };

        Scene scene = new Scene(grid);
        primaryStage.setTitle("Tic Tac Toe");
        primaryStage.setScene(scene);

        scene.getStylesheets().addAll(this.getClass().getResource("board.css").toExternalForm());

        //FirstWindow Action Listeners
        IWillPlay.setOnMouseClicked((event) -> {
            boardTurn.next = Turn.NextMove.X;
            stage.close();
        });

        YouPlay.setOnMouseClicked((event) -> {
            int index = new Random().nextInt(9);
            cells[index].setGraphic(new ImageView(OPic));
            cells[index].setUserData(new Boolean(true));
            board.placeAMove(new Point(index / 3, index % 3), 1);
            boardTurn.next = Turn.NextMove.X;
            stage.close();
        });
        stage.showAndWait();  //Tag1 
        /*
         The placement position of this line (tag1) is important.
         If you place this line above the listeners, the listeners 
         aren't gonna work
         */
        primaryStage.show();
    }

    public static void main(String[] args) {
        launch(args);
    }

}


Source [Logic][Board class]:

import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.Scanner;

class Point {

    int x, y;

    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public String toString() {
        return "[" + x + ", " + y + "]";
    }
}

class PointAndScore {

    int score;
    Point point;

    PointAndScore(int score, Point point) {
        this.score = score;
        this.point = point;
    }
}

class Board {
 
    List<Point> availablePoints;
    Scanner scan = new Scanner(System.in);
    int[][] board = new int[3][3];

    public Board() {
    }

    public boolean isGameOver() {
        //Game is over is someone has won, or board is full (draw)
        return (hasXWon() || hasOWon() || getAvailableStates().isEmpty());
    }

    public boolean hasXWon() {
        if ((board[0][0] == board[1][1] && board[0][0] == board[2][2] && board[0][0] == 1) || (board[0][2] == board[1][1] && board[0][2] == board[2][0] && board[0][2] == 1)) {
            //System.out.println("X Diagonal Win");
            return true;
        }
        for (int i = 0; i < 3; ++i) {
            if (((board[i][0] == board[i][1] && board[i][0] == board[i][2] && board[i][0] == 1)
                    || (board[0][i] == board[1][i] && board[0][i] == board[2][i] && board[0][i] == 1))) {
                // System.out.println("X Row or Column win");
                return true;
            }
        }
        return false;
    }

    public boolean hasOWon() {
        if ((board[0][0] == board[1][1] && board[0][0] == board[2][2] && board[0][0] == 2) || (board[0][2] == board[1][1] && board[0][2] == board[2][0] && board[0][2] == 2)) {
            // System.out.println("O Diagonal Win");
            return true;
        }
        for (int i = 0; i < 3; ++i) {
            if ((board[i][0] == board[i][1] && board[i][0] == board[i][2] && board[i][0] == 2)
                    || (board[0][i] == board[1][i] && board[0][i] == board[2][i] && board[0][i] == 2)) {
                //  System.out.println("O Row or Column win");
                return true;
            }
        }

        return false;
    }

    public List<Point> getAvailableStates() {
        availablePoints = new ArrayList<>();
        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 3; ++j) {
                if (board[i][j] == 0) {
                    availablePoints.add(new Point(i, j));
                }
            }
        }
        return availablePoints;
    }

    public void placeAMove(Point point, int player) {
        board[point.x][point.y] = player;   //player = 1 for X, 2 for O
    } 
    
    void takeHumanInput() {
        System.out.println("Your move: ");
        int x = scan.nextInt();
        int y = scan.nextInt();
        Point point = new Point(x, y);
        placeAMove(point, 2); 
    }

    public void displayBoard() {
        System.out.println();

        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 3; ++j) {
                System.out.print(board[i][j] + " ");
            }
            System.out.println();

        }
    } 
    
    Point computersMove; 
    
    public int minimax(int depth, int turn) {  
        if (hasXWon()) return +1; 
        if (hasOWon()) return -1;

        List<Point> pointsAvailable = getAvailableStates();
        if (pointsAvailable.isEmpty()) return 0; 
 
        int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
         
        for (int i = 0; i < pointsAvailable.size(); ++i) {  
            Point point = pointsAvailable.get(i);   
            if (turn == 1) { 
                placeAMove(point, 1); 
                int currentScore = minimax(depth + 1, 2);
                max = Math.max(currentScore, max);
                
                if(depth == 0)System.out.println("Score for position "+(i+1)+" = "+currentScore);
                if(currentScore >= 0){ if(depth == 0) computersMove = point;} 
                if(currentScore == 1){board[point.x][point.y] = 0; break;} 
                if(i == pointsAvailable.size()-1 && max < 0){if(depth == 0)computersMove = point;}
            } else if (turn == 2) {
                placeAMove(point, 2); 
                int currentScore = minimax(depth + 1, 1);
                min = Math.min(currentScore, min); 
                if(min == -1){board[point.x][point.y] = 0; break;}
            }
            board[point.x][point.y] = 0; //Reset this point
        } 
        return turn == 1?max:min;
    }  
    
    //Functions for GUI
    public int returnNextMove() {
        if (isGameOver()) return -1;
        minimax(0, 1); 
        return computersMove.x * 3 + computersMove.y;
    }

    public void resetBoard(){
        for(int i = 0;i<3;++i)
            for(int j=0;j<3;++j)
                board[i][j] = 0;
    }
}

Minimax Algorithm Tic Tac Toe AI In Java [Minimax][Full tree Search][Artificial Intelligence][Java]

The minimax tree has leaf values like -1 0 or 1. Min selects the minimum i.e. -1. Max selects the maximum among the available after Min would have taken its move. i.e. 0 or 1. So it has available moves like -1, -1, 0, 0, +1, +1 at the top most node (root, which is the present game state) and selects the first +1 value as it has a chance of victory no matter what other opponent does (it has already been calculated like if the opponent does this, I can do this (it always assumes the opponent takes the smartest move to destroy you) and I can win). There is no summation of values taking place like +3, +4, +1 so that max selects +3 and like that. This kind of approach is used in other implementation where you don't have the time to evaluate the whole tree and just want to evaluate the tree at the (say 4th) level and then rank the states accordingly like I have 3 rows in which I can get 3 Xs so that gives a score +1000, 2 rows = +100 and 1 row = +10. -ve values for the opponents position. So you get values like +1200 or -2300 at the leaves from where you select the move which is favorable (this player is not perfect, it can lose. It has not evaluated all the possibilites. It has just gone to some extent of computation to get some available move in some limited time).

This AI is a perfect player i.e. it can never lose. It wins or it draws the match.

Source: The code isn't really hard. Function names are self explanatory. Comments are added wherever necessary. I've supposed that 2 is the human player playing the game and 1 is the computer. If you want to see the actual calculations, just uncomment the commented lines.

[Make sure you have JDK 8.0 Installed] If not, here's a link: http://www.oracle.com/technetwork/java/javase/downloads/jre8-downloads-2133155.html

import java.util.*;

class Point {

    int x, y;

    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public String toString() {
        return "[" + x + ", " + y + "]";
    }
}

class PointsAndScores {

    int score;
    Point point;

    PointsAndScores(int score, Point point) {
        this.score = score;
        this.point = point;
    }
}

class Board {
 
    List<Point> availablePoints;
    Scanner scan = new Scanner(System.in);
    int[][] board = new int[3][3];

    public Board() {
    }

    public boolean isGameOver() {
        //Game is over is someone has won, or board is full (draw)
        return (hasXWon() || hasOWon() || getAvailableStates().isEmpty());
    }

    public boolean hasXWon() {
        if ((board[0][0] == board[1][1] && board[0][0] == board[2][2] && board[0][0] == 1) || (board[0][2] == board[1][1] && board[0][2] == board[2][0] && board[0][2] == 1)) {
            //System.out.println("X Diagonal Win");
            return true;
        }
        for (int i = 0; i < 3; ++i) {
            if (((board[i][0] == board[i][1] && board[i][0] == board[i][2] && board[i][0] == 1)
                    || (board[0][i] == board[1][i] && board[0][i] == board[2][i] && board[0][i] == 1))) {
                // System.out.println("X Row or Column win");
                return true;
            }
        }
        return false;
    }

    public boolean hasOWon() {
        if ((board[0][0] == board[1][1] && board[0][0] == board[2][2] && board[0][0] == 2) || (board[0][2] == board[1][1] && board[0][2] == board[2][0] && board[0][2] == 2)) {
            // System.out.println("O Diagonal Win");
            return true;
        }
        for (int i = 0; i < 3; ++i) {
            if ((board[i][0] == board[i][1] && board[i][0] == board[i][2] && board[i][0] == 2)
                    || (board[0][i] == board[1][i] && board[0][i] == board[2][i] && board[0][i] == 2)) {
                //  System.out.println("O Row or Column win");
                return true;
            }
        }

        return false;
    }

    public List<Point> getAvailableStates() {
        availablePoints = new ArrayList<>();
        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 3; ++j) {
                if (board[i][j] == 0) {
                    availablePoints.add(new Point(i, j));
                }
            }
        }
        return availablePoints;
    }

    public void placeAMove(Point point, int player) {
        board[point.x][point.y] = player;   //player = 1 for X, 2 for O
    }

    public Point returnBestMove() {
        int MAX = -100000;
        int best = -1;

        for (int i = 0; i < rootsChildrenScores.size(); ++i) { 
            if (MAX < rootsChildrenScores.get(i).score) {
                MAX = rootsChildrenScores.get(i).score;
                best = i;
            }
        }

        return rootsChildrenScores.get(best).point;
    }

    void takeHumanInput() {
        System.out.println("Your move: ");
        int x = scan.nextInt();
        int y = scan.nextInt();
        Point point = new Point(x, y);
        placeAMove(point, 2); 
    }

    public void displayBoard() {
        System.out.println();

        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 3; ++j) {
                System.out.print(board[i][j] + " ");
            }
            System.out.println();

        }
    }

    public int returnMin(List<Integer> list) {
        int min = Integer.MAX_VALUE;
        int index = -1;
        for (int i = 0; i < list.size(); ++i) {
            if (list.get(i) < min) {
                min = list.get(i);
                index = i;
            }
        }
        return list.get(index);
    }

    public int returnMax(List<Integer> list) {
        int max = Integer.MIN_VALUE;
        int index = -1;
        for (int i = 0; i < list.size(); ++i) {
            if (list.get(i) > max) {
                max = list.get(i);
                index = i;
            }
        }
        return list.get(index);
    }

    List<PointsAndScores> rootsChildrenScores;
 
    public void callMinimax(int depth, int turn){
        rootsChildrenScores = new ArrayList<>();
        minimax(depth, turn);
    }
    
    public int minimax(int depth, int turn) {

        if (hasXWon()) return +1;
        if (hasOWon()) return -1;

        List<Point> pointsAvailable = getAvailableStates();
        if (pointsAvailable.isEmpty()) return 0; 

        List<Integer> scores = new ArrayList<>(); 

        for (int i = 0; i < pointsAvailable.size(); ++i) {
            Point point = pointsAvailable.get(i);  

            if (turn == 1) { //X's turn select the highest from below minimax() call
                placeAMove(point, 1); 
                int currentScore = minimax(depth + 1, 2);
                scores.add(currentScore);

                if (depth == 0) 
                    rootsChildrenScores.add(new PointsAndScores(currentScore, point));
                
            } else if (turn == 2) {//O's turn select the lowest from below minimax() call
                placeAMove(point, 2); 
                scores.add(minimax(depth + 1, 1));
            }
            board[point.x][point.y] = 0; //Reset this point
        }
        return turn == 1 ? returnMax(scores) : returnMin(scores);
    }
}

public class TicTacToe {

    public static void main(String[] args) {
        Board b = new Board();
        Random rand = new Random();
        
        b.displayBoard();

        System.out.println("Who's gonna move first? (1)Computer (2)User: ");
        int choice = b.scan.nextInt();
        if(choice == 1){
            Point p = new Point(rand.nextInt(3), rand.nextInt(3));
            b.placeAMove(p, 1);
            b.displayBoard();
        }
        
        while (!b.isGameOver()) {
            System.out.println("Your move: ");
            Point userMove = new Point(b.scan.nextInt(), b.scan.nextInt());

            b.placeAMove(userMove, 2); //2 for O and O is the user
            b.displayBoard();
            if (b.isGameOver()) {
                break;
            } 
            b.callMinimax(0, 1);
            for (PointsAndScores pas : b.rootsChildrenScores) {
                System.out.println("Point: " + pas.point + " Score: " + pas.score);
            }
            b.placeAMove(b.returnBestMove(), 1);
            b.displayBoard();
        }
        if (b.hasXWon()) {
            System.out.println("Unfortunately, you lost!");
        } else if (b.hasOWon()) {
            System.out.println("You win! This is not going to get printed.");
        } else {
            System.out.println("It's a draw!");
        }
    }
}

Sample run:

0 0 0
0 0 0
0 0 0
Who's gonna move first? (1)Computer (2)User:
2
Your move:
2 2

0 0 0
0 0 0
0 0 2
Point: [0, 0] Score: -1
Point: [0, 1] Score: -1
Point: [0, 2] Score: -1
Point: [1, 0] Score: -1
Point: [1, 1] Score: 0
Point: [1, 2] Score: -1
Point: [2, 0] Score: -1
Point: [2, 1] Score: -1

0 0 0
0 1 0
0 0 2
Your move:
0 0

2 0 0
0 1 0
0 0 2
Point: [0, 1] Score: 0
Point: [0, 2] Score: -1
Point: [1, 0] Score: 0
Point: [1, 2] Score: 0
Point: [2, 0] Score: -1
Point: [2, 1] Score: 0

2 1 0
0 1 0
0 0 2
Your move:
2 1

2 1 0
0 1 0
0 2 2
Point: [0, 2] Score: -1
Point: [1, 0] Score: -1
Point: [1, 2] Score: -1
Point: [2, 0] Score: 0

2 1 0
0 1 0
1 2 2
Your move:
0 2

2 1 2
0 1 0
1 2 2
Point: [1, 0] Score: -1
Point: [1, 2] Score: 0

2 1 2
0 1 1
1 2 2
Your move:
1 0

2 1 2
2 1 1
1 2 2
It's a draw!

Update:
Here is an improved version. We don't need to evaluate more when we already have found a winning move, so we just skip rest of the evaluations as soon as we get +1 (for max) or -1 (for min) for some state for the next move.

Source:


import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.Scanner;

class Point {

    int x, y;

    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public String toString() {
        return "[" + x + ", " + y + "]";
    }
}

class PointAndScore {

    int score;
    Point point;

    PointAndScore(int score, Point point) {
        this.score = score;
        this.point = point;
    }
}

class Board {
 
    List<Point> availablePoints;
    Scanner scan = new Scanner(System.in);
    int[][] board = new int[3][3];

    public Board() {
    }

    public boolean isGameOver() {
        //Game is over is someone has won, or board is full (draw)
        return (hasXWon() || hasOWon() || getAvailableStates().isEmpty());
    }

    public boolean hasXWon() {
        if ((board[0][0] == board[1][1] && board[0][0] == board[2][2] && board[0][0] == 1) || (board[0][2] == board[1][1] && board[0][2] == board[2][0] && board[0][2] == 1)) {
            //System.out.println("X Diagonal Win");
            return true;
        }
        for (int i = 0; i < 3; ++i) {
            if (((board[i][0] == board[i][1] && board[i][0] == board[i][2] && board[i][0] == 1)
                    || (board[0][i] == board[1][i] && board[0][i] == board[2][i] && board[0][i] == 1))) {
                // System.out.println("X Row or Column win");
                return true;
            }
        }
        return false;
    }

    public boolean hasOWon() {
        if ((board[0][0] == board[1][1] && board[0][0] == board[2][2] && board[0][0] == 2) || (board[0][2] == board[1][1] && board[0][2] == board[2][0] && board[0][2] == 2)) {
            // System.out.println("O Diagonal Win");
            return true;
        }
        for (int i = 0; i < 3; ++i) {
            if ((board[i][0] == board[i][1] && board[i][0] == board[i][2] && board[i][0] == 2)
                    || (board[0][i] == board[1][i] && board[0][i] == board[2][i] && board[0][i] == 2)) {
                //  System.out.println("O Row or Column win");
                return true;
            }
        }

        return false;
    }

    public List<Point> getAvailableStates() {
        availablePoints = new ArrayList<>();
        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 3; ++j) {
                if (board[i][j] == 0) {
                    availablePoints.add(new Point(i, j));
                }
            }
        }
        return availablePoints;
    }

    public void placeAMove(Point point, int player) {
        board[point.x][point.y] = player;   //player = 1 for X, 2 for O
    } 
    
    void takeHumanInput() {
        System.out.println("Your move: ");
        int x = scan.nextInt();
        int y = scan.nextInt();
        Point point = new Point(x, y);
        placeAMove(point, 2); 
    }

    public void displayBoard() {
        System.out.println();

        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 3; ++j) {
                System.out.print(board[i][j] + " ");
            }
            System.out.println();

        }
    } 
    
    Point computersMove; 
    
    public int minimax(int depth, int turn) {  
        if (hasXWon()) return +1; 
        if (hasOWon()) return -1;

        List<Point> pointsAvailable = getAvailableStates();
        if (pointsAvailable.isEmpty()) return 0; 
 
        int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
         
        for (int i = 0; i < pointsAvailable.size(); ++i) {  
            Point point = pointsAvailable.get(i);   
            if (turn == 1) { 
                placeAMove(point, 1); 
                int currentScore = minimax(depth + 1, 2);
                max = Math.max(currentScore, max);
                
                if(depth == 0)System.out.println("Score for position "+(i+1)+" = "+currentScore);
                if(currentScore >= 0){ if(depth == 0) computersMove = point;} 
                if(currentScore == 1){board[point.x][point.y] = 0; break;} 
                if(i == pointsAvailable.size()-1 && max < 0){if(depth == 0)computersMove = point;}
            } else if (turn == 2) {
                placeAMove(point, 2); 
                int currentScore = minimax(depth + 1, 1);
                min = Math.min(currentScore, min); 
                if(min == -1){board[point.x][point.y] = 0; break;}
            }
            board[point.x][point.y] = 0; //Reset this point
        } 
        return turn == 1?max:min;
    }  
}

public class TicTacToe {

    public static void main(String[] args) {
        Board b = new Board();
        Random rand = new Random();
        
        b.displayBoard();

        System.out.println("Select turn:\n\n1. Computer 2. User: ");
        int choice = b.scan.nextInt();
        if(choice == 1){
            Point p = new Point(rand.nextInt(3), rand.nextInt(3));
            b.placeAMove(p, 1);
            b.displayBoard();
        }
        
        while (!b.isGameOver()) {
            System.out.println("Your move: ");
            Point userMove = new Point(b.scan.nextInt(), b.scan.nextInt());

            b.placeAMove(userMove, 2); //2 for O and O is the user
            b.displayBoard();
            if (b.isGameOver()) break;
            
            b.minimax(0, 1);  
            
            b.placeAMove(b.computersMove, 1);
            b.displayBoard();
        }
        if (b.hasXWon()) 
            System.out.println("Unfortunately, you lost!");
        else if (b.hasOWon()) 
            System.out.println("You win!"); //Can't happen
        else 
            System.out.println("It's a draw!");
    }
}


Output: 

0 0 0
0 0 0
0 0 0
Select turn:

1. Computer 2. User:
2
Your move:
2 2

0 0 0
0 0 0
0 0 2
Score for position 1 = -1
Score for position 2 = -1
Score for position 3 = -1
Score for position 4 = -1
Score for position 5 = 0
Score for position 6 = -1
Score for position 7 = -1
Score for position 8 = -1

0 0 0
0 1 0
0 0 2
Your move:
0 0

2 0 0
0 1 0
0 0 2
Score for position 1 = 0
Score for position 2 = -1
Score for position 3 = 0
Score for position 4 = 0
Score for position 5 = -1
Score for position 6 = 0

2 0 0
0 1 0
0 1 2
Your move:
0 1

2 2 0
0 1 0
0 1 2
Score for position 1 = 0
Score for position 2 = -1
Score for position 3 = -1
Score for position 4 = -1

2 2 1
0 1 0
0 1 2
Your move:
2 0

2 2 1
0 1 0
2 1 2
Score for position 1 = 0
Score for position 2 = -1

2 2 1
1 1 0
2 1 2
Your move:
1 2

2 2 1
1 1 2
2 1 2
It's a draw!

More: 

Tic-Tac-Toe (JavaFX UI)
Minimax With Alpha-Beta Pruning (Tic-Tac-Toe)

Connect 4 AI (Minimax)
Conncet 4 AI (Minimax + Alpha-Beta Pruning)

   

Tuesday, August 19, 2014

Using Lambdas Java 8 [Java 8][Lambda]

This program shows the usage of Lambdas in Java 8. Make sure that you're using JDK 1.8.0_11 or higher. If you're using Netbeans, configure it to use JDK 8 if not already done.

Lambdas are useful if you are going to learn the JavaFX APIs (they use them a lot). These also make writing much cleaner code possible.

Here's an example. Comments are included wherever necessary.

import java.util.*;
import java.util.function.*;

class Student{
    
    enum Sex { MALE, FEMALE }
    
    Student(String name, int id, Sex gender){
        this.name = name;
        this.id = id;
        this.gender = gender;
    }
    
    String name;
    int id;
    Sex gender;
    
    public void printStudent(){
        System.out.println(name+" "+id+" "+gender); 
    }
}

public class LambdaTest {
    
    static List<Student> students = new ArrayList<>();
    
    public static <A , B> void filter(Iterable<A> source, Predicate<A> lamPred, Function<A, B> mapper, Consumer<B> output){
        for(A item:source){
            if(lamPred.test(item)){
                B data = mapper.apply(item);
                output.accept(data);
            }
        }
    }
    
    public static void main(String[] args) {
        students.add(new Student("SchoolStud", 12, Student.Sex.MALE)); 
      
        filter(students, student->student.id!=0, p->{return p.name;}, stringg->System.out.println(stringg));
        filter(students, student->student.id==12, p->p.name, stringg->System.out.println(stringg));
        filter(students, s->s.id==12, s->s.name, s->System.out.println(s));
          
        AnotherTest.main();
    }    
}

interface MyLambdaType<A, B, C, D>{
    D perform(A a, B b, C c);
//    A anotherFunction(A a, B b); //Uncomment this and you get an error.
//    This interface must only have one abstract method for using it as a Lambda
}

class AnotherTest{
    public static void main(){
        Predicate<Integer> pred = p->p==11; //Tests if a value is 11
        Function<Integer, String> withReturn = p->p.toString();//Returns the 
        //string representation of Integer
        
        Consumer<String> printer = p->System.out.println(p);
        
        //In case of return values
        Function<Integer, String> withReturn1 = p->{return "Use braces if "
                + "explicitly writing return. Don't forget semicolons "
                + "inside braces";};
        BiFunction<Integer, Integer, String> adder = (a, b)->((Integer)(a+b)).toString();
        
        //If you wanna make your own lamba function using a custom interface, 
        //that interface must have only one abstract method
        MyLambdaType<Integer, Integer, Integer, String> mlt = (a, b, c)->((Integer)(a+b+c)).toString();
        
        //Now use the lambdas just defined:
        System.out.println(pred.test(11));
        System.out.println(pred.test(121));
        
        System.out.println(withReturn.apply(1772)); //Get me a string
        //representation of this Integer
        
        printer.accept("This lambda prints this line");//Print a line for me
        
        System.out.println(withReturn1.apply(1773));
        
        System.out.println(adder.apply(1772, 1772));
        
        //Now test your own lambda type
        System.out.println(mlt.perform(1, 1, 1));//Perform the addition
        //of these three numbers
        
        /*
        Lambdas are just passable functions
        */
    }
}

Output:

SchoolStud
SchoolStud
SchoolStud
true
false
1772
This lambda prints this line
Use braces if explicitly writing return. Don't forget semicolons inside braces
3544
3

Documentation http://docs.oracle.com/javase/tutorial/java/javaOO/lambdaexpressions.html

Sunday, August 17, 2014

Using JavaFX to create a Sign in form [JavaFX]

This program shows how to create a simple sign-in form using JavaFX.

Source:

import javafx.application.Application;
import javafx.event.ActionEvent;
import javafx.event.EventHandler;
import javafx.geometry.Insets;
import javafx.geometry.Pos;
import javafx.scene.Scene;
import javafx.scene.control.Button;
import javafx.scene.control.Label;
import javafx.scene.control.PasswordField;
import javafx.scene.control.TextField;
import javafx.scene.layout.GridPane;
import javafx.scene.layout.HBox;
import javafx.scene.paint.Color;
import javafx.scene.text.Font;
import javafx.scene.text.FontWeight;
import javafx.scene.text.Text;
import javafx.stage.Stage;

public class LoginPractice extends Application {

    @Override
    public void start(Stage stage) throws Exception {
        Text welcomeText = new Text();
        welcomeText.setText("Welcome");
        welcomeText.setFont(Font.font("Tahoma", FontWeight.MEDIUM, 20));

        GridPane grid = new GridPane();
        grid.setAlignment(Pos.CENTER);
        grid.setHgap(10);
        grid.setVgap(10);
        grid.setPadding(new Insets(25, 25, 25, 25));

        grid.add(welcomeText, 0, 0, 2, 1);

        Label username = new Label();
        username.setText("Username");
        grid.add(username, 0, 1);

        TextField usernamefield = new TextField();
        grid.add(usernamefield, 1, 1);

        Label password = new Label();
        password.setText("Password");
        grid.add(password, 0, 2);

        PasswordField passwordfield = new PasswordField();
        grid.add(passwordfield, 1, 2);

        Button button = new Button("Sign In"); 
        HBox hbox = new HBox(8); // spacing = 8
        hbox.getChildren().add(button);
        hbox.setAlignment(Pos.BOTTOM_RIGHT);
        grid.add(hbox, 1, 3);
        //grid.setGridLinesVisible(true); //Uncomment to see the actual layout
        final Text pressedText = new Text();
        pressedText.setFill(Color.FIREBRICK);
        grid.add(pressedText, 1, 5);

        button.setOnAction(new EventHandler<ActionEvent>() {
            @Override
            public void handle(ActionEvent event) {
                pressedText.setText("Signing you in...");
            }
        });

        Scene scene = new Scene(grid, 300, 250);
        stage.setScene(scene);
        stage.setTitle("Login");
        stage.show();
    }

    public static void main(String[] args) {
        launch(args);
    }

}