... please wait
Based on a lesson on the basics of machine learning on Brilliant.org. The article suggested that for each square on the board there is a bucket of potential moves. The program randomly picks a move. These moves are based on past winning moves and in theory the more winning moves there are the more likely it will pick a winning move for a given situation. Essentially the player picks a square and the program rolls a single dice who's number of sides are determined by the number of successful moves in the past for that square. The die is allowed to have the same move on multiple sides so, good moves will statistically come up more often. Winning moves a re recorded so, in theory, the more the game is played the better the chances of landing on a good move.
The article didn't provide any source code. It was entirely conceptual and I built my code based on my interpretation of the lesson. For all I know I could be completely off.
The program does appear to follow some of the milestones suggested in the article. The program does eventually appear to work towards a tie or "cat". The article suggests that eventually the program will win every time...I'm not holding my breath. The problem is that the program is only looking one move into the past. It's not forming any kind of a strategy. Like if I start at the corner and move across the board it doesn't appear to block my move. Which based on the single move logic makes sense. I added a bias in my code to the first move. I didn't weight it differently but, the program does look at a different table for first move historical data. Over time it does tend to pick the center square, which is what I tend to pick the most. Also, when the program picks the center square it appears to run a sound game however, it's a very small board and what appears to be logical moves could just be chance and my own bias. I would need to graph out the moves to be sure.
The concept is nothing new. This code is based on the "matchbox" method from 1960.The math often dates back 50+ years. Realistically the mathematics involved with modern machine learning is nothing new. The caveat is that we now have the computing power to do more calculations quickly.
I am no stranger to weighted algorithms. Several years ago I wrote a weighted algorithm to optimize brokering loan applications. The loan application had some 20 fields and if a loan was rejected the program attempted to find a company that would accept the loan. The company would pay a finders fee. The companies that bought the loan would pay different fees that appeared to correlate with the application fees so, I built a database and gave weights to rejected fields based on the pay-out and gave first look to those companies who paid more for the given field historically.
The code is really ugly and inefficient ... I just wanted to get it working. I was bored at home during the pandemic and registered for a Brillant.org trial. The article was REALLY geared to the lay person.
var currentmoves = [];
var win = [
[0,1,2],
[3,4,5],
[6,7,8],
[0,3,6],
[1,4,7],
[2,5,8],
[0,4,8],
[6,4,2]
];
var brain = {
"no_of_x_wins":0,
"no_of_o_wins":0,
"no_of_draw":0,
"games_played":1,
"guess_seed":1000000,
"history":[
[
[1,2,3,4,5,6,7,8],
[0,2,3,4,5,6,7,8],
[0,1,3,4,5,6,7,8]
],
[
[0,1,2,4,5,6,7,8],
[0,1,2,3,5,6,7,8],
[0,1,2,3,4,6,7,8]
],
[
[0,1,2,3,4,5,7,8],
[0,1,2,3,4,5,6,8],
[0,1,2,3,4,5,6,7]
]
],
"first_moves":[0,1,2,3,4,5,6,7,8],
// 0 = none
// 1 = player
// 2 = computer
"current":[
[
0,0,0
],
[
0,0,0
],
[
0,0,0
]
]
};
var c_move = [0,0];
var Xmoves = {
"first":null,
"moves":[
[
null,null,null
],
[
null,null,null
],
[
null,null,null
]
]
};
var Omoves = {
"first":null,
"moves":[
[
null,null,null
],
[
null,null,null
],
[
null,null,null
]
]
};
var is_first = true;
var no_of_games_played = 0;
var no_of_x_wins = 0;
var no_of_o_wins = 0;
var no_of_draw = 0;
var game_running = false;
// player is always X
var first = Math.random() * 10000;
var state = true;
if (first > 5000)
state = false;
var no_of_moves = null;
var player_move = null;
window.onload = function() {
document.getElementById("restart").addEventListener("click",restart,false);
let squares = document.getElementsByTagName("td");
for(let i=0;i<squares.length;i++) {
squares[i].addEventListener("click",function(e){sqClicked(e)});
}
restart();
}
/**
*
*GAME
*
**/
function upStats() {
console.log("upStats()");
document.getElementById("nogames").innerHTML = brain.games_played;
document.getElementById("no_of_x_wins").innerHTML = brain.no_of_x_wins;
document.getElementById("no_of_o_wins").innerHTML = brain.no_of_o_wins;
document.getElementById("no_of_draw").innerHTML = brain.no_of_draw;
}
/**
* restart the game
* @returns {Void}
**/
function restart() {
console.log("restart()");
getBrain(function(){
upStats();
brain.games_played++;
game_running = true;
no_of_moves = null;
currentmoves = [];
first = Math.random() * 10000;
state = true;
is_first = true;
Xmoves.first = null;
Omoves.first = null;
if (first > 5000)
state = false;
var squares = document.getElementsByTagName("td");
for(var i=0;i<squares.length;i++) {
squares[i].removeClass("mark_square");
squares[i].innerHTML = "";
}
for(let y=0;y<brain.current.length;y++) {
for(let x=0;x<brain.current.length;x++) {
brain.current[y][x] = 0;
}
}
if (!state) {
// !state = O ( computer move )
console.log("Computer Moves First");
computerMove();
}
});
}
/**
* check the current status of the game
* @returns {Void}
**/
function checkGameoutcome() {
console.log("checkGameoutcome()");
if (game_running) {
if (checkWin(1)) {
alert("Player Wins");
recordWin(Xmoves.moves);
recordWin(Xmoves.moves);
game_running = false;
brain.no_of_x_wins++;
console.log("recorded first_move",Xmoves.first);
recordFirstMove(2,Xmoves.first);
setBrain();
}else if (checkWin(2)) {
alert("Computer Wins");
recordWin(Omoves.moves);
recordWin(Omoves.moves);
recordWin(Omoves.moves);
game_running = false;
brain.no_of_o_wins++;
console.log("######## recorded first_move",Omoves.first);
recordFirstMove(3,Omoves.first);
setBrain();
}else if (currentmoves.length == 9) {
alert("CAT!!!");
recordWin(Xmoves.moves);
recordWin(Omoves.moves);
game_running = false;
brain.no_of_draw++;
recordFirstMove(1,Xmoves.first,Omoves.first);
setBrain();
}
}
}
/**
* loop the current results to see if a win has occured
* @param {Number}
* @returns {Boolean}
**/
function checkWin(t) {
console.log("checkWin()");
var test = brain.current.flat(2);
for(let i=0;i<win.length;i++) {
if(test[win[i][0]] == t && test[win[i][1]] == t && test[win[i][2]] == t) {
document.getElementById(win[i][0]).addClass("mark_square");
document.getElementById(win[i][1]).addClass("mark_square");
document.getElementById(win[i][2]).addClass("mark_square");
return true;
}
}
return false;
}
/**
*
*
* END GAME
*
*
* */
/**
*
*
*START PLAYER
*
*
**/
/**
* player click
* @param {Objwect} mouse event
* @returns {Void}
**/
function sqClicked(e) {
console.log("sqClicked()");
if (state) {
if (game_running) {
console.log("Players Turn");
e.target.innerHTML = "X";
state = false;
no_of_moves++;
currentmoves.push(parseInt(e.target.id));
var move = FlatTo2D(parseInt(e.target.id),3);
brain.current[move[0]][move[1]] = 1;
Xmoves.moves[c_move[0]][c_move[1]] = parseInt(e.target.id);
console.log("&&&&&&&&&&&&&&& is_first",is_first);
if (is_first) {
Xmoves.first = parseInt(e.target.id);
console.log("players first move",Xmoves.first);
}
c_move[0] = move[0];
c_move[1] = move[1];
is_first = false;
console.log("currentmoves",currentmoves);
computerMove(e.target.id);
}
checkGameoutcome();
}
}
/**
*
*
*END PLAYER
*
*
**/
/**
*
*
*START COMPUTER
*
*
**/
/**
* computer move
* @param {Number}
* @returns {Void}
**/
function computerMove(id) {
console.log("computerMove()");
if (game_running) {
console.log("Computers Turn");
var move = [0,0];
if (no_of_moves == null) {
// pick the most optimal first move
move = getFirstMove();
}else{
// pick move to counter player move
move = pickCounterMove(id);
}
if (!move) {
//
}else{
no_of_moves++;
brain.current[move[0]][move[1]] = 2;
Omoves.moves[c_move[0]][c_move[1]] = a2DtoFlat(move[1],move[0],3);
c_move[0] = move[0];
c_move[1] = move[1];
document.getElementsByTagName("td")[a2DtoFlat(move[1],move[0],3)].innerHTML = "O";
state = true;
}
}
checkGameoutcome();
}
/**
* The computers first move (if the computer has the first move)
* @returns {Array}
* */
function getFirstMove() {
console.log("getFirstMove()");
var move = [0,0];
var max = 0;
var guess = 0;
// loop all historic moves
console.log("first_moves",brain.first_moves);
guess = brain.first_moves[Math.floor((Math.random() * (brain.first_moves.length)))];
Omoves.first = guess;
is_first = false;
currentmoves.push(guess);
console.log("currentmoves",currentmoves);
return FlatTo2D(guess,3);
}
/**
* The computers counter move
* @param {Number}
* @returns {Array}
* */
function pickCounterMove(id) {
console.log("pickCounterMove()");
var nomoves = false;
var guess = null;
// get the x,y of the index
var xy = FlatTo2D(id,3);
var max = 100;
var i = 0;
do {
i++;
if (i >= max) {
nomoves = true;
break;
}
// make a random guess based on the length of the choices
guess = brain.history[xy[0]][xy[1]][Math.floor((Math.random() * (brain.history[xy[0]][xy[1]].length)))];
console.log("computer guess",guess);
} while((currentmoves.indexOf(guess) != -1) || (guess == null));
if (nomoves) {
return false;
}else{
currentmoves.push(guess);
return FlatTo2D(guess,3);
}
}
/**
*
* @param {Number}
* @returns {Void}
* */
function recordWin(a) {
console.log("recordWin()");
for(let y=0;y<a.length;y++) {
for(let x=0;x<a.length;x++) {
if (a[y][x] != null)
brain.history[y][x].push(a[y][x]);
}
}
console.log("Brain History",brain.history);
}
/**
*
* @param {Number}
* @returns {Void}
* */
function recordFirstMove(n,a,b) {
for(let i=0;i<n;i++) {
if (a != null)
brain.first_moves.push(a);
if (b != null)
brain.first_moves.push(b);
}
}
/**
*
*
*END COMPUTER
*
*
**/
/**
*
* @param {Number}
* @param {Number}
* @returns {Array}
* */
function FlatTo2D(i,w) {
var xx = i % w;
var yy = Math.floor(i / w);
return [yy,xx];
}
/**
*
* @param {Number}
* @param {Number}
* @param {Number}
* @returns {Number}
* */
function a2DtoFlat(x,y,w) {
return Math.floor(x + w * y);
}
/**
*
*
* GET / SET BRAIN DATA
*
*
* */
/**
*
* @param {Object}
* @returns {Void}
* */
function setBrain() {
console.log("setBrain()");
var xhttp = new XMLHttpRequest();
xhttp.open("POST", "brain.php", true);
xhttp.setRequestHeader("Content-type", "application/x-www-form-urlencoded");
xhttp.send("task=set&brain="+JSON.stringify(brain));
}
/**
*
* @returns {Void}
* */
function getBrain(callback) {
console.log("getBrain()");
var xhttp = new XMLHttpRequest();
xhttp.open("POST", "brain.php", true);
xhttp.send("task=get");
xhttp.onreadystatechange = function() {
if (this.readyState == 4 && this.status == 200) {
if (this.responseText)
brain = JSON.parse(this.responseText);
}
callback();
};
}
/**
*
*
* PROTOTYPES
*
*
* */
HTMLElement.prototype.hasClass = function(c) {
if (this.classList) {
return this.classList.contains(c);
}
return !!this.className.match(new RegExp('(\\s|^)' + c + '(\\s|$)'));
}
HTMLElement.prototype.addClass = function(c) {
if (this.classList) {
this.classList.add(c);
}else{
if (!this.hasClass(c)) {
this.className += c;
}
}
}
HTMLElement.prototype.removeClass = function(c) {
if (this.classList) {
this.classList.remove(c);
}else{
if (this.hasClass(c)) {
var reg = new RegExp('(\\s|^)' + c + '(\\s|$)');
this.className=this.className.replace(reg, ' ');
}
}
}
