Lesson 14 AI logic, Array Methods

Mark Harder, 11 January 2019

AI Logic

Lets apply the KISS principle from lesson 12 to building our AI code. Part of keeping our code simple is breaking down the AI move into distinct steps. We are going to use a method call heuristic technique. Heuristic is any approach to problem solving that employs a practical method, not guaranteed to be optimal, perfect, logical, or rational, but instead sufficient for reaching an immediate goal. In practical terms, we are going to breakdown our AI method into a series of choices/steps that reflect how a human might make a choice. So lets do that, how would you choose your next move? A good heuristic strategy is to do a series of checks, in order, of best and most useful to random for the last to find a move.

Tic Tac Toe AI move order heuristic.

  1. Are there locations where I can play and win? If yes, then choose one.
  2. Are there locations where my opponent can play and win? If yes, then choose a blocking location.
  3. The center location is the best spot to start, so if the center spot in available, choose it.
  4. Choose a location to setup up for two or more win paths for next turn.
  5. Choose a location to setup a win path for next turn.
  6. Choose a random location.
    • All steps are checking available locations.

How would a few of these play out?

  1. Are there locations where I can play and win? Yes the bottom right.
    Play example 1
  2. In this case it is O’s turn and it needs to block X in the bottom center.
    Play example 1

Most of these steps require us to look at each of the empty locations and test to see if a possible move will give a win.
First lets convert our existing method CheckForWinner() that checks for a win to a generic function that can be used over and over. See principle DRY from lesson 12.

Function to Breakout our Test for a Win

// Break out the test for a specific player win.
// Return 'X' or 'O' of the winner, 'Tie' for a full board, '' for no current winner.
function TestForWin(TestBoard) {
    // Setup the variable we are going to return.
    let Winner = '';

    return Winner;
}

In our existing function called CheckForWinner() we test against the global variable board by calling gameState.board[][]
In our new function we are passing in a variable named TestBoard which we will replace gameState.board.
Instead of setting gameState.Winner = to our result, we will set our new variable Winner = to our end result, so that we can return it at the end of the function instead. The idea with a re-usable function is that the only thing changed is what is returned by the function.
In computer science, a function is said to have a side effect if it modifies some state outside its local environment, that is to say has an observable interaction with the outside world besides returning a value.

// Break out the test for a specific player win.
// Return 'X' or 'O' of the winner, 'Tie' for a full board, '' for no current winner.
function TestForWin(TestBoard) {
    // Setup the variable we are going to return.
    let Winner = '';
   
    // Here is the simplest logic for checking every possibility for win.
    let row1 = TestBoard[0][0] + TestBoard[0][1] + TestBoard[0][2];
    let row2 = TestBoard[1][0] + TestBoard[1][1] + TestBoard[1][2];
    let row3 = TestBoard[2][0] + TestBoard[2][1] + TestBoard[2][2];
    
    // first check to see of the board is full
    if (row1.length + row2.length + row3.length === 9) {
        Winner = "Tie";
    }
    
    // check rows for win
    if (row1 === "XXX" || row2 === "XXX" || row3 === "XXX") {
        Winner = "X";
    }
    if (row1 === "OOO" || row2 === "OOO" || row3 === "OOO") {
        Winner = "O";
    }

    // check cols for win
    let col1 = TestBoard[0][0] + TestBoard[1][0] + TestBoard[2][0];
    let col2 = TestBoard[0][1] + TestBoard[1][1] + TestBoard[2][1];
    let col3 = TestBoard[0][2] + TestBoard[1][2] + TestBoard[2][2];    
    if (col1 === "XXX" || col2 === "XXX" || col3 === "XXX") {
        Winner = "X";
    }
    if (col1 === "OOO" || col2 === "OOO" || col3 === "OOO") {
        Winner = "O";
    }

    // check diagonal for win
    let x1 = TestBoard[0][0] + TestBoard[1][1] + TestBoard[2][2];
    let x2 = TestBoard[0][2] + TestBoard[1][1] + TestBoard[2][0];
    if (x1 === "XXX" || x2 === "XXX") {
        Winner = "X";
    }
    if (x1 === "OOO" || x2 === "OOO") {
        Winner = "O";
    }

    return Winner;
}

Now we can call the new function. Lets start by re-writing our CheckForWinner() function so that it uses our new DRY function.

function CheckForWinner() {
    let Winner = TestForWin(gameState.board);
    gameState.Winner = Winner;
    if (Winner === "X") {
        gameState.XWinCount ++;
    }
    if (Winner === "O") {
        gameState.OWinCount ++;
    }
    if (Winner === "Tie") {
        gameState.TieWins ++;
    }

    // Return true if the a winner has been found.
    return (gameState.Winner.length > 0);
}

Next we need to use our new DRY function to test all open spots for a win. Before we do that we need to learn how to test all possibilities.

Array.map(), .reduce(), .filter() and .concat()

.map()

How does it work? lets start with a simple example. Say you have an array of objects representing persons in a school. The thing we need is an array of peoples names.

// What we start with
let people = [{ id: 1, name: 'Mark Harder', position: 'Teacher', age: 40 },
    { id: 2, name: 'John Shy', position: 'Student', age: 14 },
    { id: 3, name: 'Berry Ray', position: 'Student', age: 15 },
    { id: 4, name: 'Temple Kin', position: 'Student', age: 16 }
];
// What we need
let peopleNames = ['John Shy', 'Berry Ray', 'Temple Kin'];

There are multiple ways to achieve this conversion of one array to another. You could use a for() loop or a .forEach() to meet our goal.

let peopleNames = [];
people.forEach(function (person) {
    // Array.forEach() calls your function with a parameter (person) for each item in the array.
    // Next we take the property 'name' and add it (push) to our empty array 'peopleNames'.
    peopleNames.push(person.name);
});

Notice that we needed to create an empty array first. Now lets see what this looks like using .map().

let peopleNames = people.map( (person) => {
    return person.name;
});

In this example we used an arrow function to build our array output using the map method off the array. The return result from our function used to build our new array. We are returning a string in our function, but we could also just as easily return another object.

Our array function can also be written in this even more simplified way: If there is only one command to the function we can even forego the return word

let peopleNames = people.map(person => person.name);

Or as a traditional function call:

let peopleNames = people.map(function(person) {
    return person.name;
});

.reduce()

Just like .map(), .reduce() also runs a callback for each element of an array. What’s different here is that reduce passes the result of this callback (the accumulator) from one array element to the other. The accumulator can be pretty much anything (integer, string, object, etc.) and must be instantiated or passed in when calling .reduce().

Time for an example. If we start with the same people array, we could use reduce() to sum up the ages of all the people.

let totalAge = people.reduce( (accumulator, person) => {
    return accumulator + person.age;
});

Lets break down our example code.

let totalAge = people.reduce();

  • Take each item in the people array, take something from the item add it to the accumulator, then pass it to the next iteration as the parameter accumulator. Take the total after the last item is added and assign it to the variable totalAge.

Syntax

array.reduce(callback[, initialValue])
Return value is the result from the reduction.

  • callback function has two required parameters: accumulator, currentValue
  • optionally the function can have 2 more parameters: currentIndex, array
  • optionally you c an add a parameters after the callback function initialValue initialValue: An initial value that the accumulator starts as when the first value {first array item} is called.

There are two optional parameters for the function, for a total of 4 potential parameters.

  • accumulator
    • The accumulator accumulates the callback’s return values; it is the accumulated value previously returned in the last invocation of the callback, or initialValue, if supplied (see below).
  • currentValue
    • The current element being processed in the array.
  • currentIndex
    • The index of the current element being processed in the array. Starts at index 0, if an initialValue is provided, and at index 1 otherwise.
  • array
    • The array reduce() was called upon.

.filter()

What if you have an array, but only want some of the elements in it? That’s where .filter() comes in!

Lets say we want an array of the students.

let peopleNames = people.filter( (person) => { return person.position === 'Student' } );

Lets break this code down

let peopleNames = people.filter()

  • Take the resulting array from applying filter method to the people array and assign that result to the new peopleName variable created with the let command.
    (person) => { return {Comparison} }
  • This is a arrow function where the passed in parameter is named person. For each item in your people array, it will come into the function on each iteration as the person parameter/variable.
  • {Comparison} is where you place your conditional test. If it returns true, the array element will be included in the output array and excluded if false.
  • person.position === ‘Student’ This tests to see if the property named position on the array item is equal to the string ‘Student’
  • This call will return an array like the input array, except that only objects/people that are Student will be included.
  • In our example the person named ‘Mark Harder’ will be excluded because it is position: ‘Teacher’

.concat()

This method is used two merge two arrays. The original arrays are not changed, but rather a new array that is a combination of both is returned.

Here is a simple example:

let array1 = ['Mark Harder', 'John Shy'];  
let array2 = ['Berry Ray', 'Temple Kin'];   
let array3 = array1.concat(array2);  

Results are:

[‘Mark Harder’, ‘John Shy’, ‘Berry Ray’, ‘Temple Kin’]

This method is very useful when combined with .reduce().

let nameList = ['Fred Flintstone'];
let names = people.reduce( (accumulator, person) => {
    return accumulator.concat(person.name);
}, nameList);

Results are:

[“Fred Flintstone”, “Mark Harder”, “John Shy”, “Berry Ray”, “Temple Kin”]

Normally .reduce() adds together value with an accumulator and returns the result, but using the .concat() we can take an initial array and then add to it inside the reduce method.

The line:

return accumulator.concat(person.name);

This return statement comes back in the next iteration as the parameter ‘accumulator’
So if we take the accumulator and call .concat() the new array will be returned.

Lets combine .filter(), and .reduce()

If we want to filter our people array to just students, then add their ages together and assign that total to a new variables named totalStudentAge

let totalStudentAge = people.filter( (person) => { retutrn person.position === 'Student' } ).reduce( (accumulator, person) => {
    retun accumulator + person.age;
});

Lets break down our example code.

let totalStudentAge = people.filter

  • First we filter the people array to be just students.
  • Then we reduce (add the age property together.)

Next Lesson We Will Start Building our AI Player Code.


Assignment due for discussion next class and checked into GitHub by the Monday after that.

  • Create a new repo called lesson14
  • Lets practice using map, reduce and filter. There is an index,html and main.js file that contain 4 code questions that you need to complete.
    • Download repo https://github.com/mhintegrity/lesson14
      1. Return an array of the full names of people making over $100,000.
      2. Return a total cost of the team by adding up salaries
      3. Return an array of the full names of people with SQL skills
      4. Return an array of people with “Software Engineer” in their job title. Each object in the array your return should have 2 properties, fullName, and job.