/**
* @fileoverview Bibliothek von KI-Regeln für Tic-Tac-Toe.
* Enthält komplexe Logik für 3D und Ultimate sowie Strategie-Templates.
* @author Alexander Wolf
*/
const TTTRulesLibrary = {
// --- UTILS (Hilfsfunktionen für die Regeln) ---
utils: {
/** Simuliert einen Zug und prüft auf Sieg */
canWin: (game, move, player) => {
// Simuliere den Zug für den aktuellen Spieler im sim-Board
const sim = game.clone();
// Setze nur, wenn der Spieler auch dran ist, sonst überspringe
if (sim.currentPlayer !== player) {
// Wir müssen den Spieler auf den gewünschten setzen
sim.currentPlayer = player;
}
sim.makeMove(move);
// ACHTUNG: Nach makeMove ist currentPlayer gewechselt, winner ist aber korrekt
return sim.winner === player;
},
/** Zählt Steine in einer 3D-Linie (Heuristik) */
countLine: (game, lineIndices, player) => {
let count = 0;
let empty = 0;
for(let idx of lineIndices) {
if (game.grid[idx] === player) count++;
else if (game.grid[idx] === NONE) empty++;
else return -1; // Blockiert durch Gegner
}
return { count, empty };
},
/** Generiert alle Linien-Indizes für 3D (Teuer, sollte gecacht werden) */
getLines3D: (size) => {
// (Vereinfacht: Wir berechnen das on-the-fly in den Regeln oder hardcoden für 3x3)
// Für echte Performance müsste das im Board gecacht sein.
return []; // Placeholder, Logik wird in AtomicRule implementiert
}
},
// --- BASIS REGELN ---
basics: {
win: new AtomicRule("Siegzug", "Gewinne sofort", (game) => {
for(let m of game.getAllValidMoves()) {
if(TTTRulesLibrary.utils.canWin(game, m, game.currentPlayer)) return m;
}
return null;
}),
block: new AtomicRule("Blocken", "Verhindere Niederlage", (game) => {
const opponent = (game.currentPlayer === PLAYER1) ? PLAYER2 : PLAYER1;
for(let m of game.getAllValidMoves()) {
if(TTTRulesLibrary.utils.canWin(game, m, opponent)) return m;
}
return null;
}),
random: new AtomicRule("Zufall", "Fallback", (game) => {
const moves = game.getAllValidMoves();
return moves.length > 0 ? moves[Math.floor(Math.random()*moves.length)] : null;
})
},
regular: {
// 1. Zwickmühle (Fork) suchen
fork: new AtomicRule("Gabelung", "Erzeuge zwei Gewinnwege.", (game) => {
// Suche Zug, der zwei Gewinnlinien öffnet
const moves = game.getAllValidMoves();
for (let m of moves) {
const sim = game.clone();
sim.makeMove(m); // Wir haben gesetzt
// Zähle Gewinnmöglichkeiten im NÄCHSTEN Zug
let wins = 0;
const nextMoves = sim.getAllValidMoves(); // Jetzt ist Gegner dran, aber wir prüfen UNSERE Wins
// Achtung: Nach makeMove ist currentPlayer gewechselt!
// Wir wollen wissen: Wenn ICH (der ursprüngliche Spieler) wieder dran wäre...
// Trick: Wir prüfen, ob wir im übernächsten Zug gewinnen können an >= 2 Stellen
// Das ist komplex. Einfachere Heuristik:
// "Fork" bedeutet, ich habe 2 Linien mit je 2 Steinen und leerem 3. Feld.
// ... (Hier implementieren wir eine vereinfachte Zählung)
// Um Code kurz zu halten: Wir nutzen TTTRulesLibrary.utils.findFork (Dummy oben)
// Hier eine echte Implementierung für 3x3:
// Simuliere Board NACH meinem Zug
const myPlayer = game.currentPlayer;
// Wir müssen manuell zählen, da makeMove Player switcht
const grid = [...game.grid];
grid[m] = myPlayer;
// Zähle Linien mit 2 eigenen und 1 leerem
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]];
let threats = 0;
for(let l of lines) {
const cells = [grid[l[0]], grid[l[1]], grid[l[2]]];
const myCount = cells.filter(c => c === myPlayer).length;
const emptyCount = cells.filter(c => c === 0).length;
if(myCount === 2 && emptyCount === 1) threats++;
}
if(threats >= 2) return m;
}
return null;
}),
blockFork: new AtomicRule("Gabelung Blocken", "Verhindere Fork des Gegners.", (game) => {
const opp = game.currentPlayer === PLAYER1 ? PLAYER2 : PLAYER1;
const me = game.currentPlayer;
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]];
// Hilfsfunktion: Zählt Drohungen (Linien mit 2 Steinen + 1 leer)
const countThreats = (grid, player) => {
let threats = 0;
for (const l of lines) {
const cells = [grid[l[0]], grid[l[1]], grid[l[2]]];
if (cells.filter(c => c === player).length === 2 &&
cells.filter(c => c === NONE).length === 1) threats++;
}
return threats;
};
// Finde alle Züge, die dem Gegner eine Gabelung ermöglichen würden
const moves = game.getAllValidMoves();
const forkMoves = []; // Züge, an denen Gegner forken könnte
for (const m of moves) {
const simGrid = [...game.grid];
simGrid[m] = opp;
if (countThreats(simGrid, opp) >= 2) forkMoves.push(m);
}
if (forkMoves.length === 0) return null;
// Strategie 1: Wenn genau 1 Fork-Feld → direkt blockieren
if (forkMoves.length === 1) return forkMoves[0];
// Strategie 2: Erzwinge eine Antwort, die NICHT zu einer Gabelung führt.
// Setze dort, wo wir eine Drohung (2er-Linie) aufbauen,
// OHNE dass die erzwungene Block-Position des Gegners ihm eine Gabelung gibt.
for (const m of moves) {
const simGrid = [...game.grid];
simGrid[m] = me;
if (countThreats(simGrid, me) >= 1) {
// Finde wo Gegner blocken muss
let safeForce = true;
for (const l of lines) {
const cells = [simGrid[l[0]], simGrid[l[1]], simGrid[l[2]]];
if (cells.filter(c => c === me).length === 2 &&
cells.filter(c => c === NONE).length === 1) {
const blockIdx = l[cells.indexOf(NONE)];
// Prüfe: Gibt dieser Block dem Gegner eine Gabelung?
const afterBlock = [...simGrid];
afterBlock[blockIdx] = opp;
if (countThreats(afterBlock, opp) >= 2) {
safeForce = false;
break;
}
}
}
if (safeForce) return m;
}
}
// Fallback: Blockiere erstes Fork-Feld direkt
return forkMoves[0];
}),
center: new AtomicRule("Zentrum", "Mitte", g => {
// ✅ Prüfe ob Zentrum frei UND in validMoves ist!
if (g.grid[4] === 0) {
const validMoves = g.getAllValidMoves();
return validMoves.includes(4) ? 4 : null;
}
return null;
}),
corner: new AtomicRule("Ecke", "Ecke", g => {
// ✅ WICHTIG: Nur aus gültigen Zügen wählen!
const corners = [0,2,6,8];
const validCorners = corners.filter(x => g.grid[x]===0 && g.getAllValidMoves().includes(x));
return validCorners.length > 0 ? validCorners[Math.floor(Math.random()*validCorners.length)] : null;
})
},
// --- 3D SPEZIFISCH ---
dimension3: {
// Funktioniert für 3x3x3 und 4x4x4
centerCore: new AtomicRule("Zentrum", "Besetze den Kern", (game) => {
const size = game.size;
const total = size * size * size;
const validMoves = game.getAllValidMoves();
// Generische Mitte-Berechnung
if (size % 2 !== 0) { // Ungerade (3, 5...) -> 1 Mitte
const center = Math.floor(total / 2);
// ✅ Prüfe ob Zentrum frei UND in validMoves!
return (game.grid[center] === 0 && validMoves.includes(center)) ? center : null;
}
else { // Gerade (4) -> 8 Mitten (Würfel im Würfel)
// Einfache Heuristik: Suche freien Platz im inneren Kern
// Wir scannen von 1 bis size-2 in allen Dimensionen
for(let z=1; z<size-1; z++) {
for(let y=1; y<size-1; y++) {
for(let x=1; x<size-1; x++) {
const idx = z*size*size + y*size + x;
// ✅ Prüfe BEIDE Bedingungen!
if (game.grid[idx] === 0 && validMoves.includes(idx)) return idx;
}
}
}
return null;
}
}),
// Versuch, Linien aufzubauen (Heuristik)
createSetup: new AtomicRule("Linie Bauen", "Setze neben eigenen Stein", (game) => {
// Suche einen Zug, der neben einem eigenen Stein liegt (Nachbarschaft)
// Das ist eine einfache Approximation für "Linie bauen"
const myStones = [];
game.grid.forEach((v, i) => { if(v === game.currentPlayer) myStones.push(i); });
if(myStones.length === 0) return null; // Noch keine Steine
const validMoves = game.getAllValidMoves();
// Suche Move, der Nachbar eines eigenen Steins ist
// (Nachbar: Index-Differenz ist 1, size, size*size etc...)
// ✅ Zufällig aus gültigen Zügen wählen!
return validMoves.length > 0 ? validMoves[Math.floor(Math.random()*validMoves.length)] : null;
}),
// NEU: Punkt n) - Bedingte 3D-Strategien
blockDiagonal: new AtomicRule(
"Raum-Diagonal Blocken",
"Gegner hat 2 in 3D-Diagonal",
(game) => {
const opp = game.currentPlayer === 1 ? 2 : 1;
const validMoves = game.getAllValidMoves();
// 3D Raumdiagonalen (durch Kern = Index 13)
const diagonals = [
[0, 13, 26], // Ecke zu Ecke
[2, 13, 24],
[6, 13, 20],
[8, 13, 18],
[18, 13, 8], // Gespiegelt
[20, 13, 6],
[24, 13, 2],
[26, 13, 0]
];
for (let line of diagonals) {
let oppCount = 0, emptyIdx = -1;
for (let idx of line) {
if (game.grid[idx] === opp) oppCount++;
if (game.grid[idx] === 0) emptyIdx = idx;
}
// ✅ Prüfe AUCH ob der Zug gültig ist!
if (oppCount === 2 && emptyIdx >= 0 && validMoves.includes(emptyIdx)) {
return emptyIdx;
}
}
return null;
}
),
coreExpand: new AtomicRule(
"Kern Expansion",
"Baue vom Kern aus",
(game) => {
const size = game.size;
const center = Math.floor(size * size * size / 2);
const me = game.currentPlayer;
// Wenn Kern besetzt ist (von mir), setze Nachbarn
if (game.grid[center] === me) {
// Alle direkten Nachbarn des Kerns (26 bei 3x3x3)
const neighbors = [];
for (let i = 0; i < game.grid.length; i++) {
if (game.grid[i] === 0) {
// Manuell: nähe zum Kern checken
const dist = Math.abs(i - center);
if (dist <= size + 1) neighbors.push(i);
}
}
const validMoves = game.getAllValidMoves();
const expansion = neighbors.filter(n => validMoves.includes(n));
// ✅ Zufällig aus allen gültigen Expansionen wählen!
return expansion.length > 0 ? expansion[Math.floor(Math.random()*expansion.length)] : null;
}
return null;
}
)
},
// --- ULTIMATE SPEZIFISCH ---
ultimate: {
// Gewinne das kleine Board
winLocal: new AtomicRule("Lokal Sieg", "Gewinne Teil-Board", (game) => {
for (let m of game.getAllValidMoves()) {
const sim = [...game.boards[m.big]];
sim[m.small] = game.currentPlayer;
if (checkSmallWin(sim)) return m;
}
return null;
}),
// Verhindere, dass Gegner kleines Board gewinnt
blockLocal: new AtomicRule("Lokal Block", "Rette Teil-Board", (game) => {
const opp = (game.currentPlayer===1)?2:1;
for (let m of game.getAllValidMoves()) {
const sim = [...game.boards[m.big]];
sim[m.small] = opp;
if (checkSmallWin(sim)) return m;
}
return null;
}),
// Schicke Gegner in ein bereits entschiedenes Board
sendToTrash: new AtomicRule("Müllabfuhr", "Schicke Gegner ins Aus", (game) => {
const moves = game.getAllValidMoves();
// Wir suchen Züge, wo das Zielboard (m.small) bereits entschieden ist (Status != 0)
// Das gibt dem Gegner zwar freie Wahl, aber er kann auf DIESEM Board nicht mehr punkten.
// Bessere Strategie wäre: Schicke ihn in ein Board, das ICH schon habe.
const candidates = moves.filter(m => game.macroBoard[m.small] !== 0);
// ✅ Zufällig aus allen Kandidaten wählen!
return candidates.length > 0 ? candidates[Math.floor(Math.random()*candidates.length)] : null;
}),
// Punkt o) NEU - Ultimate Strategiephase Bedingungen
winGlobal: new AtomicRule(
"Global Sieg",
"Gewinne ein Board für Sieg-Pfad",
(game) => {
// Wenn ich in den letzten 3 Boards führe, versuche den Sieg abzusichern
const me = game.currentPlayer;
let myBoardWins = 0;
for (let b = 0; b < 9; b++) {
if (game.macroBoard[b] === me) myBoardWins++;
}
// Wenn ich 2+ Boards habe, versuche 3. zu gewinnen
if (myBoardWins >= 2) {
for (let m of game.getAllValidMoves()) {
const sim = [...game.boards[m.big]];
sim[m.small] = me;
if (checkSmallWin(sim)) return m;
}
}
return null;
}
),
blockGlobal: new AtomicRule(
"Global Block",
"Blockiere Gegner vor Sieg",
(game) => {
const opp = game.currentPlayer === 1 ? 2 : 1;
let oppBoardWins = 0;
for (let b = 0; b < 9; b++) {
if (game.macroBoard[b] === opp) oppBoardWins++;
}
// Wenn Gegner 2+ Boards hat, blockiere seinen 3.
if (oppBoardWins >= 2) {
for (let m of game.getAllValidMoves()) {
const sim = [...game.boards[m.big]];
sim[m.small] = opp;
if (checkSmallWin(sim)) return m;
}
}
return null;
}
)
}
};
/** Hilfsfunktion für lokalen Sieg */
function checkSmallWin(grid) {
const wins = [[0,1,2],[3,4,5],[6,7,8], [0,3,6],[1,4,7],[2,5,8], [0,4,8],[2,4,6]];
return wins.some(w => grid[w[0]]!==0 && grid[w[0]]===grid[w[1]] && grid[w[1]]===grid[w[2]]);
}
/**
* Factory: Erstellt Entscheidungsbaum nach Spieltyp und Schwierigkeitsstufe.
*
* @param {string} type - 'regular' | '3d' | 'ultimate'
* @param {string} [level='advanced'] - 'elementary' | 'advanced'
* - elementary: Einfache Prioritätsliste (Win → Block → Positional → Random)
* - advanced: Echte Verzweigungen mit ConditionNodes
* @returns {DecisionTree}
*/
function createStrategyTree(type = 'regular', level = 'advanced') {
if (level === 'elementary') return _createElementaryTree(type);
return _createAdvancedTree(type);
}
/**
* Elementary-Baum: Flache Prioritätsliste ohne Verzweigungen.
* @private
*/
function _createElementaryTree(type) {
const root = new RuleGroup("KI Elementary");
// 1. Existenz: Win/Block
root.add(TTTRulesLibrary.basics.win.clone());
root.add(TTTRulesLibrary.basics.block.clone());
// 2. Positionelle Basis
if (type === 'regular') {
root.add(TTTRulesLibrary.regular.center.clone());
root.add(TTTRulesLibrary.regular.corner.clone());
} else if (type === '3d') {
root.add(TTTRulesLibrary.dimension3.centerCore.clone());
root.add(TTTRulesLibrary.dimension3.createSetup.clone());
} else if (type === 'ultimate') {
root.add(TTTRulesLibrary.ultimate.winLocal.clone());
root.add(TTTRulesLibrary.ultimate.blockLocal.clone());
}
// 3. Fallback
root.add(TTTRulesLibrary.basics.random.clone());
return new DecisionTree(`KI ${type} (elementary)`, root);
}
/**
* Advanced-Baum: Echte ConditionNode-Verzweigungen.
* @private
*/
function _createAdvancedTree(type) {
const root = new RuleGroup("KI Advanced");
// ═══ 1. EXISTENZ: Immer zuerst ═══
const survival = new RuleGroup("Existenz", "Gewinnen oder Blocken");
survival.add(TTTRulesLibrary.basics.win.clone());
survival.add(TTTRulesLibrary.basics.block.clone());
root.add(survival);
// ═══ 2. TAKTIK: Typ-abhängig mit echten Verzweigungen ═══
if (type === 'regular') {
// Bedingung: Stehen wir unter Druck? (Gegner hat mehr Drohungen)
const pressureCheck = new ConditionNode(
"Unter Druck?",
"Hat der Gegner potenzielle Gabelungen?",
(game) => {
const opp = game.currentPlayer === PLAYER1 ? PLAYER2 : PLAYER1;
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]];
let oppThreats = 0;
for (const l of lines) {
const cells = [game.grid[l[0]], game.grid[l[1]], game.grid[l[2]]];
if (cells.filter(c => c === opp).length === 2 &&
cells.filter(c => c === NONE).length === 1) oppThreats++;
}
// "Unter Druck" wenn Gegner mindestens 1 offene Drohung hat
return oppThreats >= 1;
},
// THEN: Defensiv — Gabelung blocken, dann Position
new RuleGroup("🛡️ Defensiv", "", [
TTTRulesLibrary.regular.blockFork.clone(),
TTTRulesLibrary.regular.center.clone(),
TTTRulesLibrary.regular.corner.clone()
]),
// ELSE: Offensiv — Gabelung suchen, dann Position
new RuleGroup("⚔️ Offensiv", "", [
TTTRulesLibrary.regular.fork.clone(),
TTTRulesLibrary.regular.center.clone(),
TTTRulesLibrary.regular.corner.clone()
])
);
root.add(pressureCheck);
} else if (type === 'ultimate') {
// Lokale Taktik zuerst
const localTactics = new RuleGroup("Lokale Taktik");
localTactics.add(TTTRulesLibrary.ultimate.winLocal.clone());
localTactics.add(TTTRulesLibrary.ultimate.blockLocal.clone());
// Bedingung: Hat der Gegner Chance auf Global-Sieg?
const strategyPhase = new ConditionNode(
"Gegner Vorsprung?",
"Hat Gegner 2+ Boards gewonnen?",
(game) => {
const opp = game.currentPlayer === PLAYER1 ? PLAYER2 : PLAYER1;
let oppWins = 0;
for (let b = 0; b < 9; b++) {
if (game.macroBoard[b] === opp) oppWins++;
}
return oppWins >= 2;
},
// THEN: Defensive — Gegner nah am Sieg
new RuleGroup("🛡️ Defensive Strategie", "", [
TTTRulesLibrary.ultimate.blockGlobal.clone(),
TTTRulesLibrary.ultimate.sendToTrash.clone(),
TTTRulesLibrary.basics.random.clone()
]),
// ELSE: Offensive — wir im Vorteil oder gleich
new RuleGroup("⚔️ Offensive Strategie", "", [
TTTRulesLibrary.ultimate.winGlobal.clone(),
TTTRulesLibrary.ultimate.sendToTrash.clone(),
TTTRulesLibrary.basics.random.clone()
])
);
root.add(localTactics);
root.add(strategyPhase);
} else if (type === '3d') {
// Bedingung: Ist Kern frei?
const coreControl = new ConditionNode(
"Kern frei?",
"Ist die Raummitte noch nicht besetzt?",
(game) => game.grid[Math.floor(game.size * game.size * game.size / 2)] === 0,
// THEN: Kern nehmen
TTTRulesLibrary.dimension3.centerCore.clone(),
// ELSE: Expansion oder Verteidigung
new ConditionNode(
"Raumdiagonale bedroht?",
"Gegner hat 2 in einer 3D-Diagonale?",
(game) => {
const opp = game.currentPlayer === PLAYER1 ? PLAYER2 : PLAYER1;
const diagonals = [
[0, 13, 26], [2, 13, 24], [6, 13, 20], [8, 13, 18]
];
for (const line of diagonals) {
let oppCount = 0;
for (const idx of line) {
if (game.grid[idx] === opp) oppCount++;
}
if (oppCount >= 2) return true;
}
return false;
},
// THEN: Diagonale blockieren
new RuleGroup("🛡️ 3D Defensiv", "", [
TTTRulesLibrary.dimension3.blockDiagonal.clone(),
TTTRulesLibrary.dimension3.coreExpand.clone()
]),
// ELSE: Offensiv ausbauen
new RuleGroup("⚔️ 3D Offensiv", "", [
TTTRulesLibrary.dimension3.coreExpand.clone(),
TTTRulesLibrary.dimension3.createSetup.clone()
])
)
);
root.add(coreControl);
}
// ═══ 3. FALLBACK ═══
root.add(TTTRulesLibrary.basics.random.clone());
return new DecisionTree(`KI ${type} (advanced)`, root);
}