DouKaku?

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Random;
import java.util.Set;

public class TicTacToe {
    public static final int SIZE = 3;

    private static final Pair[][] lines_ = new Pair[][] {
            { Pair.get(0, 0), Pair.get(0, 1), Pair.get(0, 2) },
            { Pair.get(1, 0), Pair.get(1, 1), Pair.get(1, 2) },
            { Pair.get(2, 0), Pair.get(2, 1), Pair.get(2, 2) },
            { Pair.get(0, 0), Pair.get(1, 0), Pair.get(2, 0) },
            { Pair.get(0, 1), Pair.get(1, 1), Pair.get(2, 1) },
            { Pair.get(0, 2), Pair.get(1, 2), Pair.get(2, 2) },
            { Pair.get(0, 0), Pair.get(1, 1), Pair.get(2, 2) },
            { Pair.get(2, 0), Pair.get(1, 1), Pair.get(0, 2) }, };
    public static final List<List<Pair>> LineList = new ArrayList<List<Pair>>();
    static {
        for (Pair[] line: lines_) {
            List<Pair> list = new ArrayList<Pair>();
            for (Pair pair: line) {
                list.add(pair);
            }
            LineList.add(Collections.unmodifiableList(list));
        }
    }

    private final Mark[][] fields_ = new Mark[SIZE][SIZE];

    public TicTacToe() {
        for (int x = 0; x < SIZE; x++) {
            for (int y = 0; y < SIZE; y++) {
                fields_[x][y] = Mark.E;
            }
        }
    }

    public Mark getMark(Pair pair) {
        return fields_[pair.x][pair.y];
    }

    public void setMark(Pair pair, Mark mark) {
        fields_[pair.x][pair.y] = mark;
    }

    public boolean nextStep(Pair pair, Mark mark) {
        if (getMark(pair) != Mark.E)
            return false;
        setMark(pair, mark);
        return true;
    }

    public Mark isEndGame() {
        for (Pair[] row : lines_) {
            Mark m = null;
            boolean isSame = true;
            for (Pair cell : row) {
                Mark mark = fields_[cell.x][cell.y];
                if (m == null) {
                    m = mark;
                    continue;
                }
                if (m != mark) {
                    isSame = false;
                    break;
                }
            }
            if (isSame)
                return m;
        }
        return Mark.E;
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        builder.append(String.format("%s|%s|%s%n",
                toString(getMark(Pair.get(0, 0))),
                toString(getMark(Pair.get(1, 0))),
                toString(getMark(Pair.get(2, 0)))));
        builder.append(String.format("-+-+-%n"));
        builder.append(String.format("%s|%s|%s%n",
                toString(getMark(Pair.get(0, 1))),
                toString(getMark(Pair.get(1, 1))),
                toString(getMark(Pair.get(2, 1)))));
        builder.append(String.format("-+-+-%n"));
        builder.append(String.format("%s|%s|%s%n",
                toString(getMark(Pair.get(0, 2))),
                toString(getMark(Pair.get(1, 2))),
                toString(getMark(Pair.get(2, 2)))));
        return builder.toString();
    }
    private String toString(Mark mark) {
        switch (mark) {
            case O:
            case X:
                return mark.toString();
            case E:
            default:
                return " ";
        }
    }

    public static void main(String[] args) {
        Player random1 = new RandomPlayer(Mark.O, "random1");
        Player random2 = new RandomPlayer(Mark.X, "random2");
        Player think1 = new ThinkingPlayer(Mark.O, "think1");
        Player think2 = new ThinkingPlayer(Mark.X, "think2");

        playGame(random1, random2);
        playGame(think1, random2);
        playGame(random1, think2);
        playGame(think1, think2);
    }

    private static void playGame(Player player1, Player player2) {
        int maxTurn = TicTacToe.SIZE * TicTacToe.SIZE;
        int[] result = new int[3];
        for (int round = 0; round < 10000; round++) {
            TicTacToe game = new TicTacToe();
            for (int turn = 0; turn <= maxTurn; turn++) {
                if (turn == maxTurn) {
                    result[2]++;
                    break;
                } else if (turn % 2 == 0) {
                    player1.put(game);
                } else {
                    player2.put(game);
                }
                Mark mark = game.isEndGame();
                if (mark == Mark.O) {
                    result[0]++;
                    break;
                } else if (mark == Mark.X) {
                    result[1]++;
                    break;
                }
            }
        }

        System.out.println("Result:");
        System.out.printf("%s won: %d%n", player1.name, result[0]);
        System.out.printf("%s won: %d%n", player2.name, result[1]);
        System.out.printf("draw game  : %d%n", result[2]);
    }
}

enum Mark {
    E {
        @Override public Mark getOpponent() { return E; }
    },
    O {
        @Override public Mark getOpponent() { return X; }
    },
    X {
        @Override public Mark getOpponent() { return O; }
    };

    public abstract Mark getOpponent();
}

class Pair {
    public final int x;
    public final int y;

    private Pair(int x, int y) {
        this.x = x;
        this.y = y;
    }

    private static final List<Pair> cache = new ArrayList<Pair>();
    static {
        for (int x = 0; x < TicTacToe.SIZE; x++) {
            for (int y = 0; y < TicTacToe.SIZE; y++) {
                cache.add(new Pair(x, y));
            }
        }
    }
    public static Pair get(int x, int y) {
        return cache.get(x * TicTacToe.SIZE + y);
    }

    @Override
    public int hashCode() {
        return x * 3 + y;
    }
    @Override
    public boolean equals(Object obj) {
        if (obj == this) return true;
        if (!(obj instanceof Pair)) return false;
        Pair other = (Pair) obj;
        return this.x == other.x && this.y == other.y;
    }
}

abstract class Player {
    public final Mark mark;
    public final String name;

    public Player(Mark mark, String name) {
        this.mark = mark;
        this.name = name;
    }
    public abstract void put(TicTacToe game);
}

class RandomPlayer extends Player {
    private final Random random_ = new Random();

    public RandomPlayer(Mark mark, String name) {
        super(mark, name);
    }

    @Override
    public void put(TicTacToe game) {
        if (game.isEndGame() != Mark.E) return;
        for (;;) {
            Pair pair = getNextPair();
            boolean res = game.nextStep(pair, mark);
            if (res)
                break;
        }
    }
    private Pair getNextPair() {
        return Pair.get(random_.nextInt(TicTacToe.SIZE), random_.nextInt(TicTacToe.SIZE));
    }
}

class ThinkingPlayer extends Player {
    private static final Pair CENTER = Pair.get(1, 1);
    private static final List<Pair> CORNER = new ArrayList<Pair>();
    private static final List<Pair> SIDES = new ArrayList<Pair>();

    public ThinkingPlayer(Mark mark, String name) {
        super(mark, name);
        CORNER.add(Pair.get(0, 0));
        CORNER.add(Pair.get(2, 2));
        CORNER.add(Pair.get(2, 0));
        CORNER.add(Pair.get(0, 2));
        SIDES.add(Pair.get(1, 0));
        SIDES.add(Pair.get(1, 2));
        SIDES.add(Pair.get(0, 1));
        SIDES.add(Pair.get(2, 1));
    }

    @Override
    public void put(TicTacToe game) {
        if (game.isEndGame() != Mark.E) return;
        
        int turn = 0;
        Map<Pair, Boolean> map = new HashMap<Pair, Boolean>();
        for (int x = 0; x < TicTacToe.SIZE; x++) {
            for (int y = 0; y < TicTacToe.SIZE; y++) {
                Pair pair = Pair.get(x, y);
                Mark mark = game.getMark(pair);
                if (mark == Mark.E) continue;
                turn++;
                map.put(pair, mark == this.mark);
            }
        }

        switch (turn) {
            case 0:
            case 1:
                priorityStep(game);
                break;
            case 2:
                {
                    if (map.get(CENTER) == null) {
                        game.nextStep(CENTER, this.mark);
                    } else {
                        for (int index = 0, size = CORNER.size(); index < size; index++) {
                            if (map.get(CORNER.get(index)) == Boolean.FALSE) {
                                int i = (index & 2) + (~index & 1);
                                boolean step = game.nextStep(CORNER.get(i), this.mark);
                                if (step) return;
                            }
                        }
                        priorityStep(game);
                    }
                }
                break;
            case 3:
                {
                    Set<Pair> winPair = searchWinPair(game, this.mark.getOpponent());
                    if (!winPair.isEmpty()) {
                        boolean step = game.nextStep(winPair.toArray(new Pair[0])[0], this.mark);
                        if (!step) throw new IllegalStateException(game.toString());
                        return;
                    }
                    if (game.getMark(CENTER) == this.mark) {
                        if ((game.getMark(CORNER.get(0)) == this.mark.getOpponent() && game.getMark(CORNER.get(1)) == this.mark.getOpponent())
                                || (game.getMark(CORNER.get(2)) == this.mark.getOpponent() && game.getMark(CORNER.get(3)) == this.mark.getOpponent())) {
                            for (Pair pair: SIDES) {
                                boolean step = game.nextStep(pair, this.mark);
                                if (step) return;
                            }
                        }
                    }
                    Set<Pair> goodPair = searchGoodPair(game, this.mark.getOpponent());
                    if (!goodPair.isEmpty()) {
                        boolean step = game.nextStep(goodPair.toArray(new Pair[0])[0], this.mark);
                        if (!step) throw new IllegalStateException(game.toString());
                        return;
                    }
                    priorityStep(game);
                }
                break;
            default:
                {
                    Set<Pair> winPair = searchWinPair(game, this.mark);
                    if (!winPair.isEmpty()) {
                        boolean step = game.nextStep(winPair.toArray(new Pair[0])[0], this.mark);
                        if (!step) throw new IllegalStateException(game.toString());
                        return;
                    }
                    Set<Pair> losePair = searchWinPair(game, this.mark.getOpponent());
                    if (!losePair.isEmpty()) {
                        boolean step = game.nextStep(losePair.toArray(new Pair[0])[0], this.mark);
                        if (!step) throw new IllegalStateException(game.toString());
                        return;
                    }
                    Set<Pair> noGoodPair = searchGoodPair(game, this.mark.getOpponent());
                    if (!noGoodPair.isEmpty()) {
                        boolean step = game.nextStep(noGoodPair.toArray(new Pair[0])[0], this.mark);
                        if (!step) throw new IllegalStateException(game.toString());
                        return;
                    }
                    Set<Pair> goodPair = searchGoodPair(game, this.mark);
                    if (!goodPair.isEmpty()) {
                        boolean step = game.nextStep(goodPair.toArray(new Pair[0])[0], this.mark);
                        if (!step) throw new IllegalStateException(game.toString());
                        return;
                    }
                    priorityStep(game);
                }
                break;
        }
    }

    private void priorityStep(TicTacToe game) {
        boolean step = false;
        {
            step = game.nextStep(CENTER, this.mark);
            if (step) return;
        }
        for (Pair pair: CORNER) {
            step = game.nextStep(pair, this.mark);
            if (step) return;
        }
        for (Pair pair: SIDES) {
            step = game.nextStep(pair, this.mark);
            if (step) return;
        }
    }

    private Set<Pair> searchWinPair(TicTacToe game, Mark mark) {
        Set<Pair> list = new HashSet<Pair>();
        for (List<Pair> line: TicTacToe.LineList) {
            int count = 0;
            Pair empty = null;
            for (Pair pair: line) {
                if (game.getMark(pair) == mark) {
                    count++;
                } else if (game.getMark(pair) == mark.getOpponent()) {
                    count = -1;
                    break;
                } else {
                    empty = pair;
                }
            }
            if (count == 2 && empty != null) list.add(empty);
        }
        return list;
    }

    private Set<Pair> searchGoodPair(TicTacToe game, Mark mark) {
        Set<Pair> list = new HashSet<Pair>();
        for (int x = 0; x < TicTacToe.SIZE; x++) {
            for (int y = 0; y < TicTacToe.SIZE; y++) {
                Pair pair = Pair.get(x, y);
                if (game.getMark(pair) == Mark.E) {
                    game.setMark(pair, mark);
                    Set<Pair> winPair = searchWinPair(game, mark);
                    if (winPair.size() > 1) list.add(pair);
                    game.setMark(pair, Mark.E);
                }
            }
        }
        return list;
    }
}