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