// ========================
// GOMOKU AI ENGINE (v1.0.0)
// ========================

const GomokuAI = (() => {
    // Game Constants
    const BOARD_SIZE = 15;
    const WIN_LENGTH = 5;

    // AI Cache
    let transpositionTable = new Map();
    let killerMoves = [];

    // Optimized evaluation constants
    const SCORES = {
        FIVE: 100000000,
        OPEN_FOUR: 10000000,
        CLOSED_FOUR: 1000000,
        OPEN_THREE: 50000,
        CLOSED_THREE: 1000,
        OPEN_TWO: 500,
        CLOSED_TWO: 100
    };

    // ========================
    // PUBLIC API
    // ========================

    function clearCache() {
        transpositionTable.clear();
        killerMoves = [];
    }

    // ========================
    // LEVEL-SPECIFIC MOVE FUNCTIONS
    // ========================

    function getBeginnerMove(gameState) {
        if (Math.random() < 0.3) {
            const blockMove = findThreateningMove(gameState, 'black');
            if (blockMove) return blockMove;
        }
        const smartMoves = getSmartMoves(gameState);
        if (smartMoves.length > 0) return smartMoves[Math.floor(Math.random() * smartMoves.length)];
        return getRandomMove(gameState);
    }

    function getEasyMove(gameState) {
        const immediateThreat = findImmediateWin(gameState, 'black');
        if (immediateThreat) return immediateThreat;

        const winMove = findImmediateWin(gameState, 'white');
        if (winMove) return winMove;

        if (Math.random() < 0.5) {
            const blockThree = findThreateningMove(gameState, 'black');
            if (blockThree) return blockThree;
        }

        if (Math.random() < 0.5) {
            const createThree = findThreateningMove(gameState, 'white');
            if (createThree) return createThree;
        }

        const smartMoves = getSmartMoves(gameState);
        if (smartMoves.length > 0) return smartMoves[Math.floor(Math.random() * smartMoves.length)];
        return getRandomMove(gameState);
    }

    function getMediumMove(gameState) {
        const winMove = findImmediateWin(gameState, 'white');
        if (winMove) return winMove;

        const defenseMove = findImmediateWin(gameState, 'black');
        if (defenseMove) return defenseMove;

        if (Math.random() < 0.1) {
            const smartMoves = getSmartMoves(gameState);
            if (smartMoves.length > 0) return smartMoves[Math.floor(Math.random() * smartMoves.length)];
        }

        return minimaxRoot(gameState, 3);
    }

    function getHardMove(gameState) {
        const winMove = findImmediateWin(gameState, 'white');
        if (winMove) return winMove;

        const defenseMove = findImmediateWin(gameState, 'black');
        if (defenseMove) return defenseMove;

        if (Math.random() < 0.05) return getSuboptimalMove(gameState, 4);

        return minimaxRoot(gameState, 4);
    }

    function getExpertMove(gameState) {
        if (gameState.moveHistory.length === 0) return { row: 7, col: 7 };
        if (gameState.moveHistory.length === 1) {
            const first = gameState.moveHistory[0];
            const adjacent = [
                { row: first.row + 1, col: first.col },
                { row: first.row - 1, col: first.col },
                { row: first.row, col: first.col + 1 },
                { row: first.row, col: first.col - 1 },
                { row: first.row + 1, col: first.col + 1 },
                { row: first.row - 1, col: first.col - 1 },
            ];
            for (const move of adjacent) {
                if (isValidPos(move.row, move.col) && !gameState.board[move.row][move.col]) return move;
            }
        }

        const vcfMove = findVCF(gameState, 'white', 10);
        if (vcfMove) return vcfMove;

        const timeLimit = 3000;
        const startTime = Date.now();
        let bestMove = null;
        let depth = 4;

        while (Date.now() - startTime < timeLimit && depth <= 8) {
            const move = minimaxRoot(gameState, depth, startTime, timeLimit);
            if (move) bestMove = move;
            depth++;
            if (Date.now() - startTime > timeLimit * 0.8) break;
        }

        return bestMove || minimaxRoot(gameState, 4);
    }

    // ========================
    // HELPER FUNCTIONS
    // ========================

    function getBestMove(board, level) {
        const levelMap = {
            1: getBeginnerMove,
            2: getEasyMove,
            3: getMediumMove,
            4: getHardMove,
            5: getExpertMove
        };

        const gameState = {
            board: board.map(row => row.map(cell => cell === 0 ? null : cell)),
            moveHistory: [],
            difficulty: level
        };

        const moveFn = levelMap[level] || getExpertMove;
        return moveFn(gameState);
    }

    function getRandomMove(gameState) {
        const moves = getAvailableMoves(gameState);
        return moves[Math.floor(Math.random() * moves.length)];
    }

    function findThreateningMove(gameState, player) {
        const moves = getSmartMoves(gameState);
        let bestThreatMove = null;
        let maxThreat = 0;

        for (const move of moves) {
            gameState.board[move.row][move.col] = player;
            const directions = [[0,1], [1,0], [1,1], [1,-1]];
            for (const [dx, dy] of directions) {
                let count = 1;
                for (let i = 1; i < 5; i++) {
                    const r = move.row + i*dx, c = move.col + i*dy;
                    if (isValidPos(r,c) && gameState.board[r][c] === player) count++; else break;
                }
                for (let i = 1; i < 5; i++) {
                    const r = move.row - i*dx, c = move.col - i*dy;
                    if (isValidPos(r,c) && gameState.board[r][c] === player) count++; else break;
                }
                if (count > maxThreat) {
                    maxThreat = count;
                    bestThreatMove = move;
                }
            }
            gameState.board[move.row][move.col] = null;
        }

        return maxThreat >= 3 ? bestThreatMove : null;
    }

    function getSuboptimalMove(gameState, depth) {
        const moves = getSmartMoves(gameState);
        if (moves.length <= 1) return moves[0];

        const evaluatedMoves = moves.map(move => {
            gameState.board[move.row][move.col] = 'white';
            const score = minimax(gameState, depth - 1, -Infinity, Infinity, false);
            gameState.board[move.row][move.col] = null;
            return { move, score };
        }).sort((a,b) => b.score - a.score);

        const index = Math.random() < 0.5 ? 1 : 2;
        return evaluatedMoves[Math.min(index, evaluatedMoves.length-1)].move;
    }

    function findImmediateWin(gameState, player) {
        const moves = getSmartMoves(gameState);
        for (const move of moves) {
            gameState.board[move.row][move.col] = player;
            if (checkWin(gameState, move.row, move.col, player)) {
                gameState.board[move.row][move.col] = null;
                return move;
            }
            gameState.board[move.row][move.col] = null;
        }
        return null;
    }

    function findVCF(gameState, player, maxDepth) {
        if (maxDepth <= 0) return null;
        const opponent = player === 'white' ? 'black' : 'white';
        const threats = [];
        const moves = getSmartMoves(gameState);

        for (const move of moves) {
            gameState.board[move.row][move.col] = player;
            const score = evaluatePosition(gameState, player);
            if (score > 500000) threats.push(move);
            gameState.board[move.row][move.col] = null;
        }

        for (const threat of threats) {
            gameState.board[threat.row][threat.col] = player;
            if (checkWin(gameState, threat.row, threat.col, player)) {
                gameState.board[threat.row][threat.col] = null;
                return threat;
            }

            const defenseMoves = [];
            const opponentMoves = getSmartMoves(gameState);
            for (const defMove of opponentMoves) {
                gameState.board[defMove.row][defMove.col] = opponent;
                const defScore = evaluatePosition(gameState, player);
                if (defScore < 500000) defenseMoves.push(defMove);
                gameState.board[defMove.row][defMove.col] = null;
            }

            if (defenseMoves.length === 0) {
                gameState.board[threat.row][threat.col] = null;
                return threat;
            }

            let forcedWin = true;
            for (const defMove of defenseMoves.slice(0,3)) {
                gameState.board[defMove.row][defMove.col] = opponent;
                const continuation = findVCF(gameState, player, maxDepth - 1);
                gameState.board[defMove.row][defMove.col] = null;
                if (!continuation) { forcedWin = false; break; }
            }

            gameState.board[threat.row][threat.col] = null;
            if (forcedWin && defenseMoves.length <= 3) return threat;
        }

        return null;
    }

    function minimaxRoot(gameState, depth, startTime = 0, timeLimit = 0) {
        const moves = getSmartMoves(gameState);
        if (moves.length === 0) return null;

        const orderedMoves = moves.map(move => {
            gameState.board[move.row][move.col] = 'white';
            const score = evaluatePosition(gameState, 'white');
            gameState.board[move.row][move.col] = null;
            return { move, score };
        }).sort((a,b) => b.score - a.score);

        let bestScore = -Infinity;
        let bestMove = orderedMoves[0].move;
        let alpha = -Infinity;
        const beta = Infinity;

        for (const { move } of orderedMoves) {
            if (timeLimit > 0 && Date.now() - startTime > timeLimit) break;
            gameState.board[move.row][move.col] = 'white';
            if (checkWin(gameState, move.row, move.col, 'white')) {
                gameState.board[move.row][move.col] = null;
                return move;
            }
            const score = minimax(gameState, depth-1, alpha, beta, false);
            gameState.board[move.row][move.col] = null;
            if (score > bestScore) { bestScore = score; bestMove = move; }
            alpha = Math.max(alpha, score);
        }

        return bestMove;
    }

    function minimax(gameState, depth, alpha, beta, isMaximizing) {
        const boardKey = getBoardHash(gameState);
        const cached = transpositionTable.get(boardKey + depth + isMaximizing);
        if (cached !== undefined) return cached;

        if (depth === 0) {
            const score = evaluateBoard(gameState);
            transpositionTable.set(boardKey + depth + isMaximizing, score);
            return score;
        }

        const moves = getSmartMoves(gameState);
        if (moves.length === 0) return 0;

        if (isMaximizing) {
            let maxEval = -Infinity;
            for (const move of moves) {
                gameState.board[move.row][move.col] = 'white';
                if (checkWin(gameState, move.row, move.col, 'white')) {
                    gameState.board[move.row][move.col] = null;
                    return 100000000 + depth * 1000;
                }
                const evalScore = minimax(gameState, depth-1, alpha, beta, false);
                gameState.board[move.row][move.col] = null;
                maxEval = Math.max(maxEval, evalScore);
                alpha = Math.max(alpha, evalScore);
                if (beta <= alpha) break;
            }
            transpositionTable.set(boardKey + depth + isMaximizing, maxEval);
            return maxEval;
        } else {
            let minEval = Infinity;
            for (const move of moves) {
                gameState.board[move.row][move.col] = 'black';
                if (checkWin(gameState, move.row, move.col, 'black')) {
                    gameState.board[move.row][move.col] = null;
                    return -100000000 - depth * 1000;
                }
                const evalScore = minimax(gameState, depth-1, alpha, beta, true);
                gameState.board[move.row][move.col] = null;
                minEval = Math.min(minEval, evalScore);
                beta = Math.min(beta, evalScore);
                if (beta <= alpha) break;
            }
            transpositionTable.set(boardKey + depth + isMaximizing, minEval);
            return minEval;
        }
    }

    function getBoardHash(gameState) {
        return gameState.board.map(row => row.map(cell => cell === null ? '0' : cell === 'white' ? '1' : '2').join('')).join('');
    }

    function evaluateBoard(gameState) {
        return evaluatePosition(gameState, 'white') - evaluatePosition(gameState, 'black');
    }

    function evaluatePosition(gameState, player) {
        let score = 0;
        const opponent = player === 'white' ? 'black' : 'white';

        for (let r = 0; r < BOARD_SIZE; r++) score += evaluateLine(gameState.board[r], player, opponent);
        for (let c = 0; c < BOARD_SIZE; c++) {
            const col = [];
            for (let r = 0; r < BOARD_SIZE; r++) col.push(gameState.board[r][c]);
            score += evaluateLine(col, player, opponent);
        }

        const diags = getDiagonals(gameState);
        for (const diag of diags) score += evaluateLine(diag, player, opponent);

        score += evaluatePosition_positional(gameState, player);

        return score;
    }

    function evaluatePosition_positional(gameState, player) {
        let score = 0;
        const center = Math.floor(BOARD_SIZE/2);
        for (let r = 0; r < BOARD_SIZE; r++) {
            for (let c = 0; c < BOARD_SIZE; c++) {
                if (gameState.board[r][c] === player) {
                    const dist = Math.abs(r-center)+Math.abs(c-center);
                    score += Math.max(0, 14-dist)*2;
                }
            }
        }
        return score;
    }

    function evaluateLine(line, player, opponent) {
        let score = 0;
        let consecutive = 0;

        for (let i = 0; i < line.length; i++) {
            if (line[i] === player) consecutive++;
            else if (line[i] === opponent) {
                if (consecutive>0) {
                    let startBlocked = (i-consecutive-1<0 || line[i-consecutive-1]===opponent);
                    score += getSegmentScore(consecutive, startBlocked?0:1);
                    consecutive=0;
                }
            } else if (line[i]===null) {
                if (consecutive>0) {
                    let startBlocked = (i-consecutive-1<0 || line[i-consecutive-1]===opponent);
                    score += getSegmentScore(consecutive, startBlocked?1:2);
                    consecutive=0;
                }
            }
        }

        if (consecutive>0) {
            let startBlocked = (line.length-consecutive-1<0 || line[line.length-consecutive-1]===opponent);
            score += getSegmentScore(consecutive, startBlocked?0:1);
        }

        return score;
    }

    function getSegmentScore(length, openEnds) {
        if (length >= 5) return SCORES.FIVE;
        if (length === 4) return openEnds===2?SCORES.OPEN_FOUR:SCORES.CLOSED_FOUR;
        if (length === 3) return openEnds===2?SCORES.OPEN_THREE:SCORES.CLOSED_THREE;
        if (length === 2) return openEnds===2?SCORES.OPEN_TWO:SCORES.CLOSED_TWO;
        return 0;
    }

    function getDiagonals(gameState) {
        const diags = [];
        for (let k = 0; k < BOARD_SIZE*2-1; k++) {
            const d1 = [];
            const d2 = [];
            for (let j=0;j<=k;j++){
                const i=k-j;
                if (i<BOARD_SIZE && j<BOARD_SIZE) d1.push(gameState.board[i][j]);
                if (i<BOARD_SIZE && j<BOARD_SIZE) d2.push(gameState.board[i][BOARD_SIZE-1-j]);
            }
            if (d1.length>=5) diags.push(d1);
            if (d2.length>=5) diags.push(d2);
        }
        return diags;
    }

    function getSmartMoves(gameState) {
        const moves = [];
        const radius = 2;
        const visited = Array(BOARD_SIZE).fill(null).map(()=>Array(BOARD_SIZE).fill(false));

        let hasPieces=false;
        outer: for (let r=0;r<BOARD_SIZE;r++){
            for (let c=0;c<BOARD_SIZE;c++){
                if (gameState.board[r][c]){ hasPieces=true; break outer; }
            }
        }
        if (!hasPieces) return [{row:7,col:7}];

        for (let r=0;r<BOARD_SIZE;r++){
            for (let c=0;c<BOARD_SIZE;c++){
                if (gameState.board[r][c]){
                    for (let i=-radius;i<=radius;i++){
                        for (let j=-radius;j<=radius;j++){
                            const nr=r+i, nc=c+j;
                            if (isValidPos(nr,nc) && !gameState.board[nr][nc] && !visited[nr][nc]){
                                moves.push({row:nr,col:nc});
                                visited[nr][nc]=true;
                            }
                        }
                    }
                }
            }
        }

        return moves;
    }

    function getAvailableMoves(gameState) {
        const moves=[];
        for (let r=0;r<BOARD_SIZE;r++){
            for (let c=0;c<BOARD_SIZE;c++){
                if (!gameState.board[r][c]) moves.push({row:r,col:c});
            }
        }
        return moves;
    }

    function isValidPos(row,col) { return row>=0 && row<BOARD_SIZE && col>=0 && col<BOARD_SIZE; }

    function checkWin(gameState,row,col,player){
        const directions=[[0,1],[1,0],[1,1],[1,-1]];
        for (const [dx,dy] of directions){
            let count=1;
            for (let i=1;i<WIN_LENGTH;i++){ const r=row+i*dx, c=col+i*dy; if (isValidPos(r,c)&&gameState.board[r][c]===player) count++; else break; }
            for (let i=1;i<WIN_LENGTH;i++){ const r=row-i*dx, c=col-i*dy; if (isValidPos(r,c)&&gameState.board[r][c]===player) count++; else break; }
            if (count>=WIN_LENGTH) return true;
        }
        return false;
    }

    // ========================
    // PUBLIC API RETURN
    // ========================

    return {
        getBestMove: getBestMove,
        clearCache: clearCache
    };

})();

// Node.js export for testing
if (typeof module !== "undefined" && module.exports) {
    module.exports = GomokuAI;
}