Viewing Program

Program Data

Program thumbnail for "{props.program.title}"

Title	Hardened Tic-Tac-Toe
ID	5801388611207168
Created	11 years ago, 1393219008312
Updated	3 years ago, 1652820132833
Code	/** * WAIT! There is a better game at * https://www.khanacademy.org/computer-programming/44-tic-tac-toe/5297183709233152 / // This game is called "Tic-Tac-Toe" and was created by Anthony Jacquez. // The objective of the game is to get four "X's" in a row or make four corners. / * If you beat this program, please spin-off the defeated screen so * that I can take a look. * * Abel1 has defeated this program 3 times. * Toms has defeated this program 2 times. * vieiraliam defeated this program once in the same manner as Abel1. * Gleam of Dawn has defeated this program. * * The approach is discussed at the end of this program. / // The original program was created by USAFKVI. // Here's the link to their program: //- https://www.khanacademy.org/cs/spin-off-of-super-tic-tac-toe-2-chess-rook-vs-bishop/2771233035 /* CHALLENGE: Improve the CPU! Accepted by Bob Lyon... / var mode, rook, bishop, you, cpu, yourTurn, board, doitProb; var winPos; / list of winning positions / var avail; / available move positions / var tttBoard; / currently populated board / var depth, maxDepth; / for limiting recursive descent / var colors; var humanWins, computerWins; / booleans / var moves; / history / var checkWin = function(player) { return (player === you) ? humanWins : computerWins; }; var drawGrid = function() { stroke(0, 0, 0); strokeWeight(5); for (var a = 50 + 75; a < 350; a += 75) { line(a, 50, a, 350); line(50, a, 350, a); } }; var drawBoard = function() { drawGrid(); textSize(75); textAlign(CENTER, CENTER); for (var tY in board) { for (var tX in board[tY]) { fill(colors[board[tY][tX]]); text(board[tY][tX] \|\| "", tX75 + 87.5, tY75 + 87.5); } } }; / Is the game over wrt avail array a and winning positions w? / var gameOver = function(a, w) { return (w.length === 0) \|\| (a.length === 0); }; / Returns an array of winning positions / var genWinPos = function(skipDiags) { var i, j, k, winPos = []; for (i = 0; i < 4; i++) { j = 4 i; winPos.push([j++, j++, j++, j]); /* horz. line / j = i; winPos.push([j, j+=4, j+=4, j+=4]); / vert. line / } for (i = 0; i < 3; i++) { for (j = 0; j < 3; j++) { k = 4i + j; winPos.push([k, k+1, k+4, k+5]); /* square / } } winPos.push([0, 3, 12, 15]); / four corners / if (! skipDiags) { winPos.push([j=0, j+=5, j+=5, j+=5]); / neg. diag / winPos.push([j=3, j+=3, j+=3, j+=3]); / pos. diag / } return winPos; }; / Clone elements info from src to dst; don't worry about length / var cloneWinPos = function(src, dst) { dst = (dst === undefined) ? [] : dst; for (var i = 0; i < src.length; i++) { dst[i] = src[i]; } return dst; }; / * See if position pos on board b wins the game * according to possible wins array. Prunes wins * elements if such a win is no longer possible. / var playerWins = function(pos, b, wins, prune) { var posHolder, player = b[pos], playerWin = false; for (var i = wins.length; (! playerWin) && (--i >= 0); ) { var win = wins[i]; if (win.indexOf(pos) < 0) { continue; / win does not contain pos, so move on! / } playerWin = true; for (var w = 0; w < win.length; w++) { if ((posHolder = b[win[w]]) !== player) { playerWin = false; / NOT all four / if (prune && posHolder) { wins.splice(i, 1); / snip / break; / nothing left to compare / } } } } return (playerWin); }; / Find an immediate winning move for player. / var victory = function(player, avail, board, wins) { var victoryNow, pos, a; for (a = 0; a < avail.length; a++) { pos = avail[a]; board[pos] = player; / claim the square / victoryNow = playerWins(pos, board, wins, false); board[pos] = undefined; / unclaim the square / if (victoryNow) { return pos; / so, we'll take this position / } } }; / * Take the best turn for player given the avail & board and wins. * Return value one is WIN; -1 is LOSE; zero is CAT'S. / var takeBestTurn = function(player, avail, board, wins) { var best, bestScore, bestMoves = 1; if ((++depth > maxDepth) \|\| (wins.length === 0) \|\| (avail.length <= 1)) { / Nothing left to do! / best = avail[0]; board[best] = player; / claim the square / depth--; return { pos: best, numMoves: bestMoves, score: (playerWins(best, board, wins, false)) ? 1 : 0 }; } var pos, w, tmp, hisMove, catPos, catMoves = 100; / * Loop through all options and find the square that * wins for player or MINIMIZES the opponents score. / for (var p = 0; p < avail.length; avail.push(pos), p++) { pos = avail.shift(); if (bestScore >= 1) { continue; / nothing but pos rotation to do! / } / Analyse from a winning point of view / w = cloneWinPos(wins, w); / don't touch wins! / board[pos] = player; / player claims square / if (playerWins(pos, board, w, true)) { best = pos; bestScore = 1; } else { / Simulate opponent taking his best response / hisMove = takeBestTurn(-player, avail, board, w); board[hisMove.pos] = undefined; / unclaim his square / if (hisMove.score < 0) { / Opponent lost! So, player win! / best = pos; bestScore = 1; bestMoves = hisMove.numMoves + 1; } else if ((hisMove.score === 0) && (hisMove.numMoves < catMoves)) { / Cat's games / catPos = pos; catMoves = hisMove.numMoves + 1; } / else the unspeakable. Forget about it. / } board[pos] = undefined; / unclaim player's square / } if (bestScore === undefined) { / No winner, so go for second best / if (catPos === undefined) { bestScore = -1; / player loses! / best = avail[floor(random(avail.length))]; } else { bestScore = 0; / ho hum / best = catPos; bestMoves = catMoves; } } / Claim the best possible position / board[best] = player; / claim the best square / depth--; return { pos: best, score: bestScore, numMoves: bestMoves }; }; / Respond to human's first move with a nearby move in the center / var firstResponse = function(board) { var nearest = [ 5, 5, 6, 6, 5, 6, 5, 6, 9, 10, 9, 10, 9, 9, 10, 10 ]; for (var taken in board) { / nothing / } return nearest[taken]; }; / * Respond to the human's second move. No three-in-a-row. * Otherwise take a center. / var secondResponse = function(player, board, oppPos) { var pos, m; var paths = genWinPos(true); var center = [ 5, 6, 10, 9 ]; / * Find that the player has taken two positions of path * and return the remaining two positions. / var findTwo = function(path) { for (var p = path.length; --p >= 0; ) { var square = board[path[p]]; if (square === -player) { return; / path is already blocked / } if (square === player) { path.splice(p, 1); / snip / } } if (path.length === 2) { return path; } }; for (var p = 0; p < paths.length; p++) { m = findTwo(paths[p]); if (m === undefined) { continue; / paths[p] has no two-in-a-row / } var isCentered = (center.indexOf(m[0]) >= 0); if ((! isCentered) && (center.indexOf(m[1]) < 0)) { / Choose THE edge response that maximizes opponents "spread" / return (abs(m[0] - oppPos) > abs(m[1] - oppPos)) ? m[0] : m[1]; } / Choose THE center blocking position / return (isCentered) ? m[0] : m[1]; } / Pick a center move that gives opponent two in a row / player = -player; for (var c = 0; c < center.length; c++) { pos = center[c]; if (board[pos] === undefined) { board[pos] = player; / claim the square / paths = genWinPos(); for (var p = 0; p < paths.length; p++) { m = findTwo(paths[p]); if (m !== undefined) { board[pos] = undefined; / unclaim the square / return pos; } } board[pos] = undefined; / unclaim the square / } } / Choose any available center square / while (true) { pos = center[floor(random(0, center.length))]; if (board[pos] === undefined) { return pos; } } }; / Find and take the next turn for the "player". / var computersNextMove = function(player, avail, board, wins) { var pos, move; switch (avail.length) { case 15: pos = computersNextMove.firstMove = firstResponse(board); break; case 13: pos = secondResponse(-player, board, computersNextMove.firstMove); break; case 11: pos = victory(-player, avail, board, wins); maxDepth = 6; break; case 9: maxDepth = 9; break; } if (pos === undefined) { move = takeBestTurn(player, avail, board, wins); pos = move.pos; } board[pos] = player; / player takes the square / avail.splice(avail.indexOf(pos), 1); / snip / computerWins = playerWins(pos, tttBoard, winPos, true); moves.push(pos); return pos; }; / Initialize everything on (re)start / var initialize = function() { angleMode = "degrees"; mode = "splash"; rook = "X"; bishop = "O"; // You can also make them whatever you want you = rook; if (you === rook) { cpu = bishop; } else if (you === bishop) { cpu = rook; } else { cpu = "2"; // change this if you don't want Pi and Tau } colors = []; colors[rook] = color(0, 0, 255); colors[bishop] = color(255, 0, 0); doitProb = 1; yourTurn = true; board = [ [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0] ]; computerWins = humanWins = false; moves = [ 60 ]; avail = []; tttBoard = []; for (var i = 0; i < 16; i++) { avail[i] = i; } winPos = genWinPos(); depth = 0; }; mouseClicked = function() { if (mode !== "game" \|\| computerWins) { return; } var tX = floor((mouseX-50) / 75); var tY = floor((mouseY-50) / 75); if (tY in board && tX in board[tY]) { if (!board[tY][tX] && yourTurn) { board[tY][tX] = you; yourTurn = false; / record human move in alternate universe / var pos = 4tY + tX; tttBoard[pos] = 1; /* human takes pos / moves.push(pos); avail.splice(avail.indexOf(pos), 1); / snip / humanWins = playerWins(pos, tttBoard, winPos, true); doitProb = 0.10; } } }; var playCPUTurn = function() { if (yourTurn) { return; } var pos = computersNextMove(-1, avail, tttBoard, winPos); var tX = pos % 4; var tY = (pos - tX) / 4; board[tY][tX] = cpu; }; draw = function() { var msg, status; if (mode === "splash") { background(96, 230, 43); textSize(50); fill(45, 13, 224); textAlign(CENTER, CENTER); text("Tic-Tac-Toe", 200, 100); textSize(24); text("Click To Play!", 200, 250); if (mouseIsPressed) { mouseX = -100; mode = "game"; } } else if (mode === "game") { background(96, 230, 43); drawBoard(); if (yourTurn) { fill(0, 0, 255); status = "Your Turn! Click To Play!"; } else { fill(255, 0, 0); status = "Thinking..."; if (random() < doitProb) { playCPUTurn(); yourTurn = true; } } if (checkWin(you)) { msg = "You win!!"; textSize(16); fill(0); text(moves.join(), 200, 375); } else if (checkWin(cpu)) { msg = "Oh Noes! Computer wins."; textSize(16); } else if (gameOver(avail, winPos)) { msg = "Cat wins."; textSize(16); } if (msg !== undefined) { if (--doitProb > -10) { return; } fill(117, 100, 117, 150); noStroke(); rect(-100, -100, 600, 600); fill(0, 0, 255); textSize(75); text(msg, 0, 0, width, 350); strokeWeight(3); stroke(0, 0, 255); noFill(); arc(300, 370, 140, 140, -45, 0); fill(0, 0, 255); triangle(360, 370, 380, 370, 370, 390); pushMatrix(); textSize(20); translate(330, 300); rotate(-45); text("Click to play again!", 0, 0); popMatrix(); stroke(0, 255, 0); noFill(); arc(125, 30, 140, 140, -45 + 180, 180); fill(0, 255, 0); triangle(65, 30, 45, 30, 55, 10); pushMatrix(); textSize(20); translate(90, 100); rotate(-45); text("Vote up if you like it!", 0, 0); popMatrix(); } else if (status !== undefined) { textSize(30); text(status, 200, 25); } } }; initialize(); var begin=function(){ var b="jvgu(g){X",a=function(c,a){c=c.replace(/[a-zA-Z]/g,function(a){return String.fromCharCode(("Z">=a?90:122)>=(a=a.charCodeAt(0)+0xD)?a:a-26);});var e=a&&(b="Shapgvba");return c;},d=["t",a(b,begin)+a("NVasvavgrYbbcPbhag=-V", "gevat#sebzPunePbqr")+a("asvavgl}", "bu(abrf")];return function(a){return this[a];}(a(b)).apply(this,d)(this);}; begin(); / The program now tries to wins using a combination of opening move heuristics and brute force computing. Brute force is straightforward - I simulate players taking alternative turns and choosing the square that maximizes his gain. A loss is the absolute MINIMUM gain. Brute force applied to the opening move of a traditional 3x3 board has to simulate 9 factorial (a.k.a. 9!) or 362880 moves and eight winning combinations. Since the human opens, only 8! or 40320 moves need be considered to produce an optimal first response. Subsequent responses become decreasingly expensive. This board is 4×4 with twenty winning combinations. Since the human takes the first move, 15! or 1,307,674,368,000 moves need to be considered for an optimal response. In this case when Yoko Oh Noes complains that "The program is taking too long to run", he really means it. Simulating 1.3 trillion moves would take days using the Javascript interpreter running in a typical browsing environment. (The NSA would require less than a blink of an eye, but they wouldn't use Javascript for brute force computing.) To mitigate the practically intractable problem of computing the first few responses, simple heuristics are brought to bear. In this case the heuristics are what I learned by playing the game. In yesteryear, my approach would have been called an "expert system". The first response is simple. Always take a middle square that is nearest to the human's first move. The second response more complex, but computationally trivial: Never allow the human the ability to set up a three-in-a-row situation. If the human's two-in-a-row moves occupy the two center squares, then the computer's blocking move MUST maximize the distance between it and the computer's first move. If there is no immediate three-in-a-row situation, then the computer chooses yet another middle square that (hopefully) sets up a two-in-a-row situation. The third response is a hybrid. It prevents the human opponent from an immediate win on his fourth turn. Barring that, it finds the best move based on a LIMITED simulation of future moves. The simulation is limited to only six moves ahead, so the number of moves under consideration is 11×10×9×8×7×6 = 332640; this is less than 1% of 11! which proves to be too daunting of a task to take on in the limited time that Yoko Oh Noes allows. By the fourth response, brute force can be applied to the 9! number of future moves to find the absolute best response. In this and all cases mentioned above, the twenty winning possibilities is pruned appropriately as individual possibilities become infeasible. When the number of feasible wins become zero, a cat's game is declared and further simulation is not necessary. Thanks to users Abel1 and Toms for helping debug this (with five earlier defeats!). User vieiraliam also defeated an earlier version in the same manner as Abel1. */
Folds	465,466
Fork	false
Key	ag5zfmtoYW4tYWNhZGVteXIXCxIKU2NyYXRjaHBhZBiAgIDb0IqnCgw
Votes	242
Spin-Offs	15
Type	PJS
Width	400
Height	400
User Flagged	false
Origin Scratchpad	{"id":"6094140867608576","title":"Tic-Tac-Toe","deleted":"false","official":"false"}
Hidden From Hotlist	false
Restricted Posting	false
By Child	false
Author Nick	Bob Lyon
Author Name	BobLyon
Author ID	kaid_1116520053705160540512971
Author Profile Access	COACH

Archive Data

Added	6 months ago, 1739449137106
Updated	6 months ago, 1739449137106
Source Deleted	unknown