Utility Village 틱택토는 쉬움(랜덤 AI)과 어려움(Minimax AI) 두 가지 난이도를 제공합니다. 어려움 난이도에서 AI는 절대 지지 않습니다 — 최선의 결과는 무승부입니다.
게임 상태
type Cell = 'X' | 'O' | null;
type Board = Cell[]; // 9칸 배열, 인덱스 0~8
interface GameState {
board: Board;
currentPlayer: 'X' | 'O';
winner: 'X' | 'O' | 'draw' | null;
scores: { X: number; O: number; draws: number };
}
플레이어는 X, AI는 O입니다.
승리 판정
8개의 승리 라인을 미리 정의하고 순회합니다.
const WINNING_LINES = [
[0, 1, 2], [3, 4, 5], [6, 7, 8], // 행
[0, 3, 6], [1, 4, 7], [2, 5, 8], // 열
[0, 4, 8], [2, 4, 6], // 대각선
];
function checkWinner(board: Board): 'X' | 'O' | 'draw' | null {
for (const [a, b, c] of WINNING_LINES) {
if (board[a] && board[a] === board[b] && board[a] === board[c]) {
return board[a] as 'X' | 'O';
}
}
if (board.every(cell => cell !== null)) return 'draw';
return null;
}
Minimax 알고리즘
Minimax는 게임 트리를 완전 탐색하여 AI(O)에게 최선인 수를 찾는 알고리즘입니다.
- AI(O): 점수 최대화 (maximizing)
- 플레이어(X): 점수 최소화 (minimizing)
function minimax(board: Board, isMaximizing: boolean, depth: number): number {
const winner = checkWinner(board);
// 종료 조건
if (winner === 'O') return 10 - depth; // AI 승리: 빨리 이길수록 높은 점수
if (winner === 'X') return depth - 10; // 플레이어 승리: 빨리 질수록 낮은 점수
if (winner === 'draw') return 0;
const emptyCells = board.reduce<number[]>(
(acc, cell, i) => (cell === null ? [...acc, i] : acc), []
);
if (isMaximizing) {
let best = -Infinity;
for (const cell of emptyCells) {
board[cell] = 'O';
best = Math.max(best, minimax(board, false, depth + 1));
board[cell] = null;
}
return best;
} else {
let best = Infinity;
for (const cell of emptyCells) {
board[cell] = 'X';
best = Math.min(best, minimax(board, true, depth + 1));
board[cell] = null;
}
return best;
}
}
depth 페널티의 역할
10 - depth를 점수로 사용하면 AI가 가능한 한 빨리 이기는 경로를 선택합니다. depth 페널티 없이 단순히 +10 / -10 / 0을 사용하면 어떤 이기는 수든 동등하게 취급하여 AI가 이미 승리가 확정된 상황에서도 임의의 수를 두는 것처럼 보일 수 있습니다.
반대로 플레이어(X)의 승리는 depth - 10이므로 AI는 최대한 늦게 지는 경로를 선택합니다. 이는 플레이어가 실수를 유도하는 방어적 전략입니다.
AI 수 선택
function getAIMove(board: Board, difficulty: 'easy' | 'hard'): number {
const emptyCells = board.reduce<number[]>(
(acc, cell, i) => (cell === null ? [...acc, i] : acc), []
);
if (difficulty === 'easy') {
// 쉬움: 빈 칸 중 랜덤 선택
return emptyCells[Math.floor(Math.random() * emptyCells.length)];
}
// 어려움: Minimax로 최선의 수 선택
let bestScore = -Infinity;
let bestMove = emptyCells[0];
for (const cell of emptyCells) {
board[cell] = 'O';
const score = minimax(board, false, 0);
board[cell] = null;
if (score > bestScore) {
bestScore = score;
bestMove = cell;
}
}
return bestMove;
}
React 통합
AI 차례가 되면 useEffect로 감지하고 400ms 딜레이 후 수를 둡니다. 딜레이 없이 즉시 응답하면 AI가 너무 기계적으로 느껴지기 때문입니다.
useEffect(() => {
if (gameState.currentPlayer === 'O' && !gameState.winner) {
const timer = setTimeout(() => {
const move = getAIMove([...gameState.board], difficulty);
dispatch({ type: 'MAKE_MOVE', payload: move });
}, 400);
return () => clearTimeout(timer);
}
}, [gameState.currentPlayer, gameState.winner]);
틱택토는 해결된 게임
틱택토는 solved game입니다. 양쪽 모두 최선을 다하면 항상 무승부가 됩니다. 따라서 어려움 난이도에서 플레이어가 할 수 있는 최선의 결과도 무승부입니다. AI를 이기는 것은 불가능합니다.
난이도 변경 시 점수판이 초기화됩니다. 쉬움에서 쌓은 점수와 어려움에서의 점수를 분리하기 위해서입니다.