var INFINITY = 20000;
function game() {
    var logo = document.getElementById('logo');
    var table = getElementsByClassName(logo, 'ttt')[0];

    var board = [[1, 0, 0], [0, -1, 0], [0, 0, 0]];
    var boardSize = board.length;
    var maxDepth = 10;
    while (table.childNodes.length > 0) {
        table.removeChild(table.childNodes[0]);
    }
    table.gameDone = false;
    for (var i = 0; i < boardSize; ++i) {
        var tr = document.createElement('tr');
        for (var j = 0; j < boardSize; ++j) {
            var td = document.createElement('td');
            if (i == 0 && j == 0) {
                td.className += ' red';
                td.innerHTML = 'O';
            }
            else if (i == 1 && j == 1) {
                td.className += ' blue';
                td.innerHTML = 'X';
            }
            else {
                td.innerHTML = '&nbsp;';
                var playerMove = createClickListener(td, table, board, i, j,
		  maxDepth);
                addEventListener(td, 'click', playerMove);
            }
            tr.appendChild(td);
        }

        table.appendChild(tr);
    }

    document.getElementById('logo').appendChild(table);
}

function createClickListener(td, table, board, x, y, maxDepth) {
    var clickListener = function () {
        if (table.gameDone || board[x][y] != 0) {
            removeEventListener(td, 'click', clickListener);
            return;
        }
        board[x][y] = 1;
        td.innerHTML = 'O';
        td.className += ' red';
        removeEventListener(td, 'click', clickListener);

        var winner = determineWinner(board);
        if (winner != 0 && winner != null) {
            finishAndPrepareForRestart(table);
        }
        else if (!cpuMove(board, table, clickListener, maxDepth)) {
            finishAndPrepareForRestart(table);
        }
    };

    return clickListener;
}

function finishAndPrepareForRestart(table) {
    table.gameDone = true;
    for (var i = 0; i < table.childNodes.length; ++i) {
        for (var j = 0; j < table.childNodes.length; ++j) {
            var td = table.childNodes[i].childNodes[j];
            addEventListener(td, 'click', game);
        }
    }
}

function cpuMove(board, table, playerMove, maxDepth) {
    var nextMove = decide(board, -1, maxDepth);
    if (nextMove == null) {
        return false;
    }
    var x = nextMove[0], y = nextMove[1];
    board[x][y] = -1;

    for (var i = 0; i < table.childNodes.length; ++i) {
        if (i == x) {
            for (var j = 0; j < table.childNodes[i].childNodes.length; ++j) {
                if (j == y) {
                    var td = table.childNodes[i].childNodes[j];
                    td.innerHTML = 'X';
                    td.className += ' blue';
                    removeEventListener('click', playerMove);
                    break;
                }
            }
        }
    }

    var winner = determineWinner(board);
    return winner == 0;
}

function decide(board, player, maxDepth) {
    var nextMove = minimax(board, player, maxDepth);
    if (nextMove == null) {
        return null;
    }

    return nextMove.move;
}

function minimax(board, player, depth) {
    var best = null;

    var nextMoves = getNextMoves(board, player);
    for (var i = 0; i < nextMoves.length; ++i) {
        var nextMove = nextMoves[i];
        var newBoard = copyBoard(board);
        newBoard[nextMove[0]][nextMove[1]] = player;

        var value = minimaxScore(newBoard, nextPlayer(player), depth);

        if (best == null || value != null && value > best.score) {
            best = { score: value, move: nextMove };
        }
    }

    return best;
}

function minimaxScore(board, player, depth) {
    var winner = determineWinner(board);

    if (depth == 0 || winner != 0) {
        return determineScore(board, player, winner, depth);
    }

    var alpha = player * INFINITY;

    var nextMoves = getNextMoves(board, player);
    for (var i = 0; i < nextMoves.length; ++i) {
        var nextMove = nextMoves[i];
        var newBoard = copyBoard(board);
        newBoard[nextMove[0]][nextMove[1]] = player;

        var value = minimaxScore(newBoard, nextPlayer(player), depth - 1);
        alpha = player > 0 ? Math.max(alpha, value) : Math.min(alpha, value);
    }

    return alpha * player;
}

function determineScore(board, player, winner, level) {
    if (winner == player) {
        score = (100 + level);
    }
    else if (winner == 0) {
        score = 0;
    }
    else {
        score = (-100 - level);
    }

    return score;
}

function determineWinner(board) {
    var boardSize = board.length;
    var columnWinners = [];
    var downTowardsRightWinner = board[0][0];
    var downTowardsRightWon = downTowardsRightWinner != 0;
    var downTowardsLeftWinner = board[0][boardSize - 1];
    var downTowardsLeftWon = downTowardsRightWinner != 0;

    for (var i = 0; i < boardSize; ++i) {
        columnWinners.push({ player: board[0][i], won: board[0][i] != 0 });
    }
    for (var i = 0; i < boardSize; ++i) {
        var rowWinner = board[i][0];
        var rowWon = rowWinner != 0;
        for (var j = 0; j < boardSize; ++j) {
            if (board[i][j] != rowWinner) {
                rowWon = false;
            }

            var columnWinner = columnWinners[j];
            if (board[i][j] != columnWinner.player) {
                columnWinner.won = false;
            }

            if (i == j && downTowardsRightWinner != board[i][j]) {
                downTowardsRightWon = false;
            }

            if (i + j + 1 == boardSize && downTowardsLeftWinner != board[i][j]) {
                downTowardsLeftWon = false;
            }
        }

        if (rowWon) {
            return rowWinner;
        }
    }

    if (downTowardsRightWon) {
        return downTowardsRightWinner;
    }

    if (downTowardsLeftWon) {
        return downTowardsLeftWinner;
    }

    for (var i = 0; i < boardSize; ++i) {
        if (columnWinners[i].won) {
            return columnWinners[i].player;
        }
    }

    return 0;
}


function getNextMoves(board, player) {
    var moves = [];
    var boardSize = board.length;
    for (var i = 0; i < boardSize; ++i) {
        for (var j = 0; j < boardSize; ++j) {
            if (board[i][j] == 0) {
                moves.push([i, j]);
            }
        }
    }

    return moves;
}

function nextPlayer(player) {
    return -player;
}

function copyBoard(board) {
    var newBoard = [];
    var boardSize = board.length;
    for (var i = 0; i < boardSize; ++i) {
        newBoard.push([]);
        for (var j = 0; j < boardSize; ++j) {
            newBoard[i].push(board[i][j]);
        }
    }

    return newBoard;
}