/**
* @fileoverview TTT-Trainingsdaten-Generator für den NN-Playground.
*
* Generiert Supervised-Learning-Daten: Board-Zustand → Minimax-optimaler Zug (One-Hot).
* Die Daten werden on-demand im Browser berechnet (kein externer Datensatz nötig).
*
* Encoding:
* Input: 9 Werte — 1 = currentPlayer, -1 = Gegner, 0 = leer
* Target: 9 Werte — One-Hot-Vektor des optimalen Zugs (Minimax)
*
* Symmetrie-Augmentierung: Diehedralgruppe D₄ (4 Rotationen × 2 Spiegelungen = 8).
*
* Convention: Keine DOM-Bezüge! Läuft auch im Web Worker.
*
* @author Alexander Wolf
* @see ToDos/NN_PLAYGROUND_PLAN_v2.md
*/
/* global GAME_CONSTANTS */
/**
* @typedef {Object} TTTSample
* @property {Float64Array} input — 9 Eingangswerte (Board-Zustand)
* @property {Float64Array} target — 9 Zielwerte (One-Hot: optimaler Zug)
*/
/**
* Symmetrie-Transformationen des 3×3 TTT-Bretts (Diehedralgruppe D₄).
* Jede Transformation ist eine Permutation der 9 Feld-Indizes.
*
* Original: Rotation 90° CW: Rotation 180°: Rotation 270° CW:
* 0 1 2 6 3 0 8 7 6 2 5 8
* 3 4 5 → 7 4 1 → 5 4 3 → 1 4 7
* 6 7 8 8 5 2 2 1 0 0 3 6
*
* Horizontale Spiegelung: Vertikale Spiegelung: Diag ↘: Diag ↗:
* 2 1 0 6 7 8 0 3 6 8 5 2
* 5 4 3 3 4 5 1 4 7 7 4 1
* 8 7 6 0 1 2 2 5 8 6 3 0
*
* @type {number[][]}
*/
const TTT_SYMMETRIES = [
[0, 1, 2, 3, 4, 5, 6, 7, 8], // Identity
[6, 3, 0, 7, 4, 1, 8, 5, 2], // 90° CW
[8, 7, 6, 5, 4, 3, 2, 1, 0], // 180°
[2, 5, 8, 1, 4, 7, 0, 3, 6], // 270° CW
[2, 1, 0, 5, 4, 3, 8, 7, 6], // Horizontal flip
[6, 7, 8, 3, 4, 5, 0, 1, 2], // Vertical flip
[0, 3, 6, 1, 4, 7, 2, 5, 8], // Diagonal ↘
[8, 5, 2, 7, 4, 1, 6, 3, 0], // Diagonal ↗
];
/**
* Wendet eine Symmetrie-Transformation auf einen 9er-Vektor an.
*
* @param {Float64Array|number[]} vec — Eingabe (9 Elemente)
* @param {number[]} perm — Permutation (9 Indizes aus TTT_SYMMETRIES)
* @returns {Float64Array} Transformierter Vektor
*/
function applySymmetry(vec, perm) {
const result = new Float64Array(9);
for (let i = 0; i < 9; i++) {
result[i] = vec[perm[i]];
}
return result;
}
/**
* Einfacher Minimax für TTT (ohne Alpha-Beta — TTT ist klein genug).
* Gibt den optimalen Zug für den aktuellen Spieler zurück.
*
* @param {number[]} grid — 9er Board-Array (0=leer, 1=P1, 2=P2)
* @param {number} currentPlayer — 1 oder 2
* @returns {number} Index des optimalen Zugs (0-8)
*/
function minimaxBestMove(grid, currentPlayer) {
const P1 = 1, P2 = 2, EMPTY = 0, DRAW_VAL = 3;
const 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(g) {
for (const [a, b, c] of LINES) {
if (g[a] !== EMPTY && g[a] === g[b] && g[b] === g[c]) return g[a];
}
if (!g.includes(EMPTY)) return DRAW_VAL;
return 0; // game continues
}
function minimax(g, player, isMaximizing) {
const w = checkWinner(g);
if (w === currentPlayer) return 10;
if (w === (currentPlayer === P1 ? P2 : P1)) return -10;
if (w === DRAW_VAL) return 0;
let bestScore = isMaximizing ? -Infinity : Infinity;
for (let i = 0; i < 9; i++) {
if (g[i] !== EMPTY) continue;
g[i] = player;
const nextPlayer = player === P1 ? P2 : P1;
const score = minimax(g, nextPlayer, !isMaximizing);
g[i] = EMPTY;
if (isMaximizing) {
bestScore = Math.max(bestScore, score);
} else {
bestScore = Math.min(bestScore, score);
}
}
return bestScore;
}
let bestMove = -1;
let bestScore = -Infinity;
for (let i = 0; i < 9; i++) {
if (grid[i] !== EMPTY) continue;
grid[i] = currentPlayer;
const nextPlayer = currentPlayer === P1 ? P2 : P1;
const score = minimax(grid, nextPlayer, false);
grid[i] = EMPTY;
if (score > bestScore) {
bestScore = score;
bestMove = i;
}
}
return bestMove;
}
/**
* Generiert TTT-Trainingsdaten mit Minimax-Labels.
*
* Erkundet alle erreichbaren Spielzustände per BFS und berechnet für jeden
* nicht-terminalen Zustand den optimalen Zug via Minimax.
*
* @param {Object} [options={}]
* @param {boolean} [options.useSymmetries=false] — Symmetrie-Augmentierung (D₄)
* @param {boolean} [options.bothPlayers=true] — Trainingsbeispiele für beide Spieler
* @returns {TTTSample[]} Array von {input, target}
*/
function generateTTTTrainingData(options = {}) {
const { useSymmetries = false, bothPlayers = true } = options;
const P1 = 1, P2 = 2, EMPTY = 0;
const visited = new Set();
const samples = [];
/**
* Enkodiert ein Board als Eingabevektor.
* currentPlayer → +1, Gegner → -1, leer → 0.
*
* @param {number[]} grid
* @param {number} player
* @returns {Float64Array}
*/
function encodeBoard(grid, player) {
const input = new Float64Array(9);
const opponent = player === P1 ? P2 : P1;
for (let i = 0; i < 9; i++) {
if (grid[i] === player) input[i] = 1;
else if (grid[i] === opponent) input[i] = -1;
// else 0 (leer)
}
return input;
}
/**
* Prüft ob ein Zustand terminal ist.
* @param {number[]} grid
* @returns {boolean}
*/
function isTerminal(grid) {
const 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]
];
for (const [a, b, c] of LINES) {
if (grid[a] !== EMPTY && grid[a] === grid[b] && grid[b] === grid[c]) return true;
}
return !grid.includes(EMPTY);
}
/**
* Rekursives BFS über alle erreichbaren Zustände.
* @param {number[]} grid
* @param {number} player
*/
function explore(grid, player) {
const key = grid.join('') + player;
if (visited.has(key)) return;
visited.add(key);
if (isTerminal(grid)) return;
// Nur Zustände für currentPlayer trainieren (oder beide)
if (bothPlayers || player === P1) {
const bestMove = minimaxBestMove([...grid], player);
if (bestMove < 0) return;
const input = encodeBoard(grid, player);
const target = new Float64Array(9);
target[bestMove] = 1.0;
samples.push({ input, target });
// Symmetrie-Augmentierung
if (useSymmetries) {
for (let s = 1; s < TTT_SYMMETRIES.length; s++) { // skip identity (s=0)
const symInput = applySymmetry(input, TTT_SYMMETRIES[s]);
const symTarget = applySymmetry(target, TTT_SYMMETRIES[s]);
// Deduplizierung: Nur wenn nicht bereits vorhanden
const symKey = Array.from(symInput).join(',');
if (!visited.has('sym_' + symKey)) {
visited.add('sym_' + symKey);
samples.push({ input: symInput, target: symTarget });
}
}
}
}
// Alle möglichen Folgezüge erkunden
const opponent = player === P1 ? P2 : P1;
for (let i = 0; i < 9; i++) {
if (grid[i] !== EMPTY) continue;
const nextGrid = [...grid];
nextGrid[i] = player;
explore(nextGrid, opponent);
}
}
explore(Array(9).fill(EMPTY), P1);
return samples;
}
/**
* Shuffled ein Array in-place (Fisher-Yates).
* @param {Array} arr
* @returns {Array} Das gleiche Array (mutiert)
*/
function shuffleArray(arr) {
for (let i = arr.length - 1; i > 0; i--) {
const j = Math.floor(Math.random() * (i + 1));
[arr[i], arr[j]] = [arr[j], arr[i]];
}
return arr;
}
// Export für Web Worker und Main Thread
if (typeof self !== 'undefined' && typeof self.importScripts === 'function') {
// Web Worker context
self.generateTTTTrainingData = generateTTTTrainingData;
self.shuffleArray = shuffleArray;
self.TTT_SYMMETRIES = TTT_SYMMETRIES;
} else if (typeof window !== 'undefined') {
// Browser context
window.generateTTTTrainingData = generateTTTTrainingData;
window.shuffleArray = shuffleArray;
window.TTT_SYMMETRIES = TTT_SYMMETRIES;
}