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

public class TicTacToe {

	private class Move {
		final int x, y, score;

		Move(int x, int y, int score) {
			this.x = x;
			this.y = y;
			this.score = score;
		}

		Move(int score) {
			this(-1, -1, score);
		}

		@Override
		public String toString() {
			return String.format("%d %d %d", y, x, score);
		}
	}

	private static final char HUMAN = 'X';
	private static final char COMPUTER = 'O';
	private static final char EMPTY = ' ';

	private static final char CONTINUE = '+';
	private static final char DRAW = '-';

	private static final int MAX_DEPTH = 9;

	private final char[][] board = new char[3][3];

	public TicTacToe() {
		for (int i = 0; i < 3; i++) {
			Arrays.fill(board[i], EMPTY);
		}
	}

	public int humanMove(final int row, final int column)
	{
		board[row][column] = HUMAN;
		return eval(HUMAN);
	}

	public int computerMove()
	{
		Move move = maximum(Math.min(MAX_DEPTH, getMoves().size()));
		board[move.y][move.x] = COMPUTER;
		return eval(COMPUTER);
	}

	private Move maximum(int depth) {
		if (depth == 0) {
			return new Move(0);
		}

		Move best = new Move(Integer.MIN_VALUE);

		for (Move move : getMoves()) {
			board[move.y][move.x] = COMPUTER;

			char result = eval(COMPUTER);
			int value = result == COMPUTER ? depth : minimum(depth-1).score;

			if (value > best.score) {
				best = new Move(move.x, move.y, value);
			}

			board[move.y][move.x] = EMPTY;
		}

		return best;
	}

	private Move minimum(int depth) {
		if (depth == 0) {
			return new Move(0);
		}

		Move worst = new Move(Integer.MAX_VALUE);

		for (Move move : getMoves()) {
			board[move.y][move.x] = HUMAN;

			char result = eval(HUMAN);
			int value = result == HUMAN ? -depth : maximum(depth-1).score;

			if (value < worst.score) {
				worst = new Move(move.x, move.y, value);
			}

			board[move.y][move.x] = EMPTY;
		}

		return worst;

	}

	private List<Move> getMoves() {
		List<Move> moves = new ArrayList<>();

		for (int y = 0; y < 3; y++) {
			for (int x = 0; x < 3; x++) {
				if (board[y][x] == EMPTY) {
					moves.add(new Move(x, y, 0));
				}
			}
		}
		return moves;
	}

	private char eval(char player) {
		// Rows
		for (int y = 0; y < 3; y++) {
			if (board[y][0] == player &&
				board[y][1] == player &&
				board[y][2] == player) {

				return player;
			}
		}

		// Columns
		for (int x = 0; x < 3; x++) {
			if (board[0][x] == player &&
				board[1][x] == player &&
				board[2][x] == player) {

				return player;
			}
		}

		// Diagonals
		if (board[0][0] == player &&
			board[1][1] == player &&
			board[2][2] == player) {

			return player;
		}

		if (board[0][2] == player &&
			board[1][1] == player &&
			board[2][0] == player) {

			return player;
		}

		for (int y = 0; y < 3; y++) {
			for (int x = 0; x < 3; x++) {
				if (board[y][x] == EMPTY) return CONTINUE;
			}
		}

		return DRAW;
	}

	@Override
	public String toString() {
		String s = "";
		s += " " + board[0][0] + " | " + board[0][1] + " | " + board[0][2] + '\n';
		s += "---+---+---\n";
		s += " " + board[1][0] + " | " + board[1][1] + " | " + board[1][2] + '\n';
		s += "---+---+---\n";
		s += " " + board[2][0] + " | " + board[2][1] + " | " + board[2][2] + '\n';
		return s;
	}

	public static void main(String[] args) {

		Scanner s = new Scanner(System.in);
		TicTacToe game = new TicTacToe();

		int result = CONTINUE;

		while (result == CONTINUE) {

			result = game.computerMove();
			System.out.println(game);

			if (result != CONTINUE) break;

			System.out.print("Human move: ");
			String input = s.nextLine();
			if (input.equals("q")) System.exit(1);

			int y = Integer.parseInt(input) / 10;
			int x = Integer.parseInt(input) % 10;

			result = game.humanMove(y-1, x-1);
		}

		System.out.println(game);

		if (result == HUMAN) System.out.println("human won");
		if (result == COMPUTER) System.out.println("computer won");
		if (result == DRAW) System.out.println("draw");

		s.close();
	}

}