aima.js

Artificial Intelligence - A Modern Approach (AIMA) by Stuart Russell and Peter Norvig is the reference textbook on artificial intelligence.

This package implements some of the algorithms and data structures from the AIMA book in function-oriented CoffeeScript, which is compatible with JavaScript. The focus is on code understandability.

Installation and Usage

For using this package as a module in your own Node JavaScript project, install it with the node package manager:

npm install aima

import { Problem, makeEightPuzzle, aStarSearch } from 'aima'

const simpleEightPuzzle = makeEightPuzzle([
  [1, 2, 7],
  [6, 0, 4],
  [8, 3, 5]
])

console.log(Problem.solutionPath(aStarSearch(simpleEightPuzzle)))

Put the above example code in example.mjs and run it:

node example.mjs

Extensions

• aima-checkers: Checkers rulebase.

Applications

• aima-checkers-gui: Graphical checkers browsergame for desktop and mobile.
• while-quine: Finding a Quine program for the WHILE language.

Related Work

To my knowledge, there are exactly two other JavaScript projects related to AIMA:

• aimacode/aima-javascript is an implementation maintained by AIMA co-author Peter Norvig. Its aim is to power some beautiful interactive visualizations. It is written in browser JavaScript rather than Node Java- / CoffeeScript. The aimacode organization also features repositories with AIMA implementations in other programming languages, notably Java and Python.

• ajlopez/NodeAima is an abandoned implementation of only the vacuum world in Node JavaScript.

The existing code from these projects still has to be harnessed for this project!

Contributing

Every contribution is very welcome: Modifications of existing code to make it more understandable and beautiful; additional algorithms and data structures from the book; additional problems and games; additional usage examples; additional documentation; anything else you have in mind. Please create an issue or a pull request!

Thank you very much in advance for your contribution :)

Development

• npm test verifies all the assertions in the code.

• npm run build removes all assertion statements from the code, as well as all lines which are ended by # testing only. This way, the testing can be kept right next to the code it refers to, but it is excluded from the distributed package. The code is then transpiled to JavaScript into the index.mjs file. The index.mjs file is the content for the NPM package, and also the basis for coverage reporting.

• npm run coverage creates a coverage report. It is automatically run via Github actions on each push, and the resulting report is pushed to CodeCov.

• npm run dev is a convenience shortcut for development. You can put CoffeeScript code into a new file dev.coffee, import * from './index.mjs' and then run it with npm run dev. The temporary file dev.mjs is needed for source map support, a technique which enables the JavaScript debugger to refer to the correct CoffeeScript lines, rather than to the lines in the transpiled JavaScript code. Using a separate file instead of developing inside README.litcoffee spares you to re-run all the tests there when you just want to run your new tests.

Code

Dependencies

import deepEqual            from 'deep-equal'
import { strict as assert } from 'assert'

For testing subroutines which depend on random numbers, we use a seeded random number generator which can be called by rand.random():

import gen                  from 'random-seed'   # testing only
seed = 'seedshrdlu4523'                          # testing only
rand = gen.create seed                           # testing only

Utilities

Sum

Array::sum = (f = (x) -> x) ->
  this.reduce (accumulator, element, index, array) ->
    accumulator + f element, index, array
  , 0

array = [ [100, 1000], [200, 2000], [300, 3000] ]
assert.equal (array.sum (x)           -> x[1]),                        6000
assert.equal (array.sum (x, i)        -> x[1] + 10 * i),               6030
assert.equal (array.sum (x, i, array) -> x[1] + 10 * i + array[0][0]), 6330

Argmax, Argmin

Array::argmin = (f) ->
  this.reduce (accumulator, element) ->
    if (f element) < f accumulator
      element
    else
      accumulator

Array::argmax = (f) ->
  this.reduce (accumulator, element) ->
    if (f element) > f accumulator
      element
    else
      accumulator

array = [ [100, 3000], [200, 1000], [300, 2000] ]
assert.deepEqual (array.argmax (x) -> x[0]), [300, 2000]
assert.deepEqual (array.argmax (x) -> x[1]), [100, 3000]
assert.deepEqual (array.argmin (x) -> x[0]), [100, 3000]
assert.deepEqual (array.argmin (x) -> x[1]), [200, 1000]

Max, Min

Array::min = ->
  this.argmin (x) -> x

Array::max = ->
  this.argmax (x) -> x

array = [3, 5, 4, 1, 2]
assert.equal array.max(), 5
assert.equal array.min(), 1

Factorial

factorial = (n) -> 
  [1..n]
    .reduce (accumulator, current) ->
      accumulator * current

assert.equal factorial(5), 1 * 2 * 3 * 4 * 5
assert.equal factorial(10), factorial(5) * 6 * 7 * 8 * 9 * 10

Intelligent Agents

Table-Driven Agent

Confer section 2.4, p. 47.

export class TableDrivenAgent
  constructor: (@table = {}) ->
    @percepts = []

  action: (percept) ->
    @percepts.push percept
    @table[this.percepts]

Example: Table Vacuum Agent

tableVacuumAgent = new TableDrivenAgent
  [ [ ['A', 'clean'] ] ]: 'right'
  [ [ ['A', 'dirty'] ] ]: 'suck'
  [ [ ['B', 'clean'] ] ]: 'left'
  [ [ ['B', 'dirty'] ] ]: 'suck'
  [ [ ['A', 'clean'], ['A', 'clean'] ] ]: 'right'
  [ [ ['A', 'clean'], ['A', 'dirty'] ] ]: 'suck'
  [ [ ['A', 'clean'], ['B', 'clean'] ] ]: 'left'
  [ [ ['A', 'clean'], ['B', 'dirty'] ] ]: 'suck'
  [ [ ['A', 'dirty'], ['A', 'clean'] ] ]: 'right'
  [ [ ['A', 'dirty'], ['A', 'dirty'] ] ]: 'suck'
  [ [ ['A', 'dirty'], ['B', 'clean'] ] ]: 'left'
  [ [ ['A', 'dirty'], ['B', 'dirty'] ] ]: 'suck'
  [ [ ['B', 'clean'], ['A', 'clean'] ] ]: 'right'
  [ [ ['B', 'clean'], ['A', 'dirty'] ] ]: 'suck'
  [ [ ['B', 'clean'], ['B', 'clean'] ] ]: 'left'
  [ [ ['B', 'clean'], ['B', 'dirty'] ] ]: 'suck'
  [ [ ['B', 'clean'], ['A', 'clean'] ] ]: 'right'
  [ [ ['B', 'clean'], ['A', 'dirty'] ] ]: 'suck'
  [ [ ['B', 'clean'], ['B', 'clean'] ] ]: 'left'
  [ [ ['B', 'clean'], ['B', 'dirty'] ] ]: 'suck'
  [ [ ['A', 'clean'], ['A', 'clean'], ['A', 'clean'] ] ]: 'right'
  [ [ ['A', 'clean'], ['A', 'clean'], ['A', 'dirty'] ] ]: 'suck'  #...

assert.equal tableVacuumAgent.action([ ['A', 'dirty'] ]), 'suck'
assert.equal tableVacuumAgent.action([ ['A', 'clean'] ]), 'right'
assert.equal tableVacuumAgent.action([ ['B', 'dirty'] ]), undefined

Simple Reflex Agent

Confer section 2.4, p. 49.

export class SimpleReflexAgent
  constructor: (@rules) ->

  action: (percept) ->
    state = @interpretInput percept
    rule  = @rules.find (rule) ->
      rule.condition ...state
    rule?.action

  interpretInput: (percept) ->
    percept

Example: Reflex Vacuum Agent

reflexVacuumAgent = new SimpleReflexAgent [
  condition: ([..., status  ]) -> status   == 'dirty'
  action: 'suck'
,
  condition: ([location, ...]) -> location == 'A'
  action: 'right'
,	
  condition: ([location, ...]) -> location == 'B'
  action: 'left'
]

assert.equal (reflexVacuumAgent.action [ ['A', 'dirty'] ]), 'suck'
assert.equal (reflexVacuumAgent.action [ ['A', 'clean'] ]), 'right'
assert.equal (reflexVacuumAgent.action [ ['B', 'dirty'] ]), 'suck'
assert.equal (reflexVacuumAgent.action [ ['C', 'dirty'] ]), 'suck'
assert.equal (reflexVacuumAgent.action [ ['C', 'clean'] ]), undefined

Problem Solving

For the node structure, confer section 3.3.1, p. 79.

export class Problem
  constructor: ({ @initialState, @actions, result }) ->
    @_result = result

  result: (state, action) ->
    if @actions(state).some (a) -> deepEqual action, a
      @_result state, action

  rootNode: ->
    state: @initialState

  childNode: (node, action) -> {
    state:  @result node.state, action
    parent: node
    action: action
  }

  expand: (node) ->
    @childNode(node, action) for action in @actions(node.state)

  @solutionPath: (node) ->
    if 'parent' of node
      [...Problem.solutionPath(node.parent), node.state]
    else
      [node.state]

Search

Confer section 3.1.1, p. 67.

export class SearchProblem extends Problem
  constructor: ({ initialState, actions, result, stepCost, @heuristic = (-> 0), @goalTest }) ->
    super
      initialState: initialState,
      actions:      actions,
      result:       result
    @_stepCost = stepCost

  stepCost: (state, action) ->
    this._stepCost state, action if (@actions state).some (a) -> deepEqual action, a

  rootNode: -> {
    ...super()
    pathCost:  0
    heuristic: @heuristic @initialState
  }

  childNode: (node, action) -> {
    ...super node, action
    pathCost:  node.pathCost + @stepCost node.state, action
    heuristic: @heuristic @result node.state, action
  }

Toy Problems

Vacuum World

Confer section 3.2.1, p. 70.

export vacuumWorld = new SearchProblem
  initialState: 
    location: 'A'
    A:        'dirty'
    B:        'dirty'
  actions: (state) -> [
    'left'
    'right'
    'suck'
  ]
  result: (state, action) ->
    location:
      if action == 'left'
        'A'
      else if action == 'right'
        'B'
      else
        state.location
    A: 
      if state.location == 'A' and action == 'suck'
        'clean'
      else
        state.A
    B: 
      if state.location == 'B' and action == 'suck'
        'clean'
      else
        state.B
  stepCost: (state, action) -> 1
  goalTest: (state) ->
    state.A == 'clean' and
    state.B == 'clean'

state = vacuumWorld.initialState
assert.deepEqual state, { location: 'A', A: 'dirty', B: 'dirty' }

state = vacuumWorld.result state, 'suck'
assert.deepEqual state, { location: 'A', A: 'clean', B: 'dirty' }

state = vacuumWorld.result state, 'suck'
assert.deepEqual state, { location: 'A', A: 'clean', B: 'dirty' }

state = vacuumWorld.result state, 'left'
assert.deepEqual state, { location: 'A', A: 'clean', B: 'dirty' }

state = vacuumWorld.result state, 'right'
assert.deepEqual state, { location: 'B', A: 'clean', B: 'dirty' }
assert not vacuumWorld.goalTest state

state = vacuumWorld.result state, 'suck'
assert.deepEqual state, { location: 'B', A: 'clean', B: 'clean' }
assert vacuumWorld.goalTest state

8-Puzzle

Confer section 3.2.1, p. 71.

export makeEightPuzzle = (initialState) ->
  moveIsValid = (zero) ->
    zero.y in [0, 1, 2] and
    zero.x in [0, 1, 2]

  zero = (state) -> # position of zero
    y: state.indexOf(state.filter((row) -> row.includes 0)[0])
    x: state.filter(              (row) -> row.includes 0)[0].indexOf 0

  goalPosition = (nr) -> [
    goalState.findIndex (row) -> row.includes(nr)
    goalState.find(     (row) -> row.includes(nr)).indexOf nr
  ]

  manhattanDist = ([y1, x1], [y2, x2]) ->
    Math.abs(y1 - y2) +
    Math.abs(x1 - x2)

  moves =
    up:    { y: -1, x:  0 }
    down:  { y:  1, x:  0 }
    left:  { y:  0, x: -1 }
    right: { y:  0, x:  1 }

  goalState = [
    [0, 1, 2]
    [3, 4, 5]
    [6, 7, 8]
  ]

  new SearchProblem
    initialState: initialState
    actions: (state) ->
      Object.keys(moves)
        .filter (key) -> moveIsValid
          y: (zero state).y + moves[key].y
          x: (zero state).x + moves[key].x
    result: (state, action) ->
      state.map (row, y) ->
        row.map (nr, x) ->
          # Shift zero to new position.
          if y == (zero state).y + moves[action].y and
          x    == (zero state).x + moves[action].x
            0
          # Shift number to old position of zero.
          else if nr == 0
            state[(zero state).y + moves[action].y][(zero state).x + moves[action].x]
          # Keep all other numbers.
          else
            nr
    stepCost: (state, action) -> 1
    heuristic: (state) ->
      state.sum (numbers, y) ->
        numbers.sum (number, x) ->
          manhattanDist [y, x], goalPosition number
    goalTest: (state) ->
      deepEqual state, goalState

simpleEightPuzzle = makeEightPuzzle [
  [1, 4, 2]
  [3, 0, 5]
  [6, 7, 8]
]

state = simpleEightPuzzle.initialState
assert.deepEqual state, [
  [1, 4, 2]
  [3, 0, 5]
  [6, 7, 8]
]
assert.equal (simpleEightPuzzle.heuristic state), 4

state = simpleEightPuzzle.result state, 'up'
assert.deepEqual state, [
  [1, 0, 2]
  [3, 4, 5]
  [6, 7, 8]
]
assert.equal (simpleEightPuzzle.heuristic state), 2
assert not simpleEightPuzzle.goalTest state

state = simpleEightPuzzle.result state, 'left'
assert.deepEqual state, [
  [0, 1, 2]
  [3, 4, 5]
  [6, 7, 8]
]
assert.equal (simpleEightPuzzle.heuristic state), 0
assert simpleEightPuzzle.goalTest state

complexEightPuzzle = makeEightPuzzle [
  [7, 2, 4]
  [5, 0, 6]
  [8, 3, 1]
]
state = complexEightPuzzle.initialState
assert.equal (simpleEightPuzzle.heuristic state), 20

Incremental 8-Queens Problem

Incremental formulation of the 8-queens problem. Confer section 3.2.1, p. 72.

export incrementalEightQueensProblem = new SearchProblem
  initialState: []
  actions: (state) ->
    y = state.length
    if y < 8
      [0, 1, 2, 3, 4, 5, 6, 7]
        .filter (x) ->
          not isAttacked [y, x], state
    else []
  result: (state, action) -> [...state, action]
  stepCost: (state, action) -> 0
  goalTest: (state) -> state.length == 8

isAttacked = ([y0, x0], state) ->
  state.some (x, y) ->
    x == x0 or
    y == y0 or
    Math.abs(y - y0) == Math.abs(x - x0)

state = incrementalEightQueensProblem.initialState

state = incrementalEightQueensProblem.result state, 3
assert.deepEqual state, [3]
assert.deepEqual (incrementalEightQueensProblem.result state, 3), undefined

state = incrementalEightQueensProblem.result state, 5
assert.deepEqual state, [3, 5]
assert.deepEqual (incrementalEightQueensProblem.result state, 1), undefined

Knuth Conjecture

Confer section 3.2.1, p. 73.

export makeKnuthConjecture = (goal) ->
  calc = (state) ->
    state.reduce (total, operation) ->
      if operation.isNumber
        operation
      else if operation == 'factorial'
        factorial total
      else if operation == 'square_root'
        Math.sqrt total
      else if operation == 'floor'
        Math.floor total
  new SearchProblem
    initialState: [4]
    actions: (state) ->
      if Number.isInteger calc(state)
        ['square_root', 'factorial']
      else
        ['square_root', 'floor']
    result: (state, action) -> [...state, action],
    stepCost: (state, action) -> 1,
    goalTest: (state) -> (calc state) == goal

simpleKnuthConjecture  = makeKnuthConjecture 1
complexKnuthConjecture = makeKnuthConjecture 5

state = complexKnuthConjecture.initialState
assert.deepEqual state, [4]

state = complexKnuthConjecture.result state, 'factorial'
state = complexKnuthConjecture.result state, 'factorial'
state = complexKnuthConjecture.result state, 'square_root'
state = complexKnuthConjecture.result state, 'square_root'
state = complexKnuthConjecture.result state, 'square_root'
state = complexKnuthConjecture.result state, 'square_root'

state = complexKnuthConjecture.result state, 'square_root'
assert not complexKnuthConjecture.goalTest state

state = complexKnuthConjecture.result state, 'floor'
assert complexKnuthConjecture.goalTest state

Real World Problems

Confer section 3.1, p. 68.

cities =
  dist:
    Arad:
      Zerind: 75
      Sibiu: 140
      Timisoara: 118
    Zerind:
      Arad: 75
      Oradea: 71
    Oradea:
      Zerind: 71
      Sibiu: 151
    Sibiu:
      Arad: 140
      Oradea: 151
      Fagaras: 99
      RimnicuVilcea: 80
    Fagaras:
      Sibiu: 99
      Bucharest: 211
    Bucharest:
      Fagaras: 211
      Urziceni: 85
      Giurgiu: 90
      Pitesti: 101
    Urziceni:
      Bucharest: 85
      Vaslui: 142
      Hirsova: 98
    Vaslui:
      Urziceni: 142
      Iasi: 92
    Iasi:
      Vaslui: 92
      Neamt: 87
    Neamt:
      Iasi: 87
    Hirsova:
      Urziceni: 98
      Eforie: 86
    Eforie:
      Hirsova: 86
    Giurgiu:
      Bucharest: 90
    Pitesti:
      Bucharest: 101
      Craiova: 138
      RimnicuVilcea: 97
    Craiova:
      Pitesti: 138
      Drobeta: 120
      RimnicuVilcea: 146
    Drobeta:
      Craiova: 120
      Mehadia: 75
    Mehadia:
      Drobeta: 120
      Lugoj: 70
    Lugoj:
      Mehadia: 70
      Timisoara: 111
    Timisoara:
      Lugoj: 111
      Arad: 118
    RimnicuVilcea:
      Sibiu: 80
      Pitesti: 97
      Craiova: 146
  straightLineDist:
    Bucharest:
      Arad: 366
      Mehadia: 241
      Bucharest: 0
      Neamt: 234
      Craiova: 160
      Oradea: 380
      Drobeta: 242
      Pitesti: 100
      Eforie: 161
      RimnicuVilcea: 193
      Fagaras: 176
      Sibiu: 253
      Giurgiu: 77
      Timisoara: 329
      Hirsova: 151
      Urziceni: 80
      Iasi: 226
      Vaslui: 199
      Lugoj: 244
      Zerind: 374
    Arad:
      Bucharest: 366
    Mehadia:
      Bucharest: 241
    Neamt:
      Bucharest: 234
    Craiova:
      Bucharest: 160
    Oradea:
      Bucharest: 380
    Drobeta:
      Bucharest: 242
    Pitesti:
      Bucharest: 100
    Eforie:
      Bucharest: 161
    RimnicuVilcea:
      Bucharest: 193
    Fagaras:
      Bucharest: 176
    Sibiu:
      Bucharest: 253
    Giurgiu:
      Bucharest: 77
    Timisoara:
      Bucharest: 329
    Hirsova:
      Bucharest: 151
    Urziceni:
      Bucharest: 80
    Iasi:
      Bucharest: 226
    Vaslui:
      Bucharest: 199
    Lugoj:
      Bucharest: 244
    Zerind:
      Bucharest: 374

Route Finding Problem

Confer section 3.2.2, p. 73.

export makeRouteFindingProblem = (graph, start, end) ->
  new SearchProblem
    initialState: start
    actions: (state) ->
      Object.keys graph.dist[state]
    result: (state, action) ->
      action if action of graph.dist[state]
    stepCost: (state, action) ->
      graph.dist[state][action]
    heuristic: (state) ->
      graph.straightLineDist[state][end]
    goalTest: (state) ->
      deepEqual state, end

routeFindingProblem = makeRouteFindingProblem cities, 'Arad', 'Bucharest'

state = routeFindingProblem.initialState
assert.equal state, 'Arad'
assert.equal (routeFindingProblem.stepCost state, 'Sibiu'), 140

state = routeFindingProblem.result state, 'Sibiu'
assert.equal state, 'Sibiu'
assert.equal (routeFindingProblem.stepCost state, 'RimnicuVilcea'), 80

state = routeFindingProblem.result state, 'RimnicuVilcea'
assert.equal state, 'RimnicuVilcea'
assert.equal (routeFindingProblem.stepCost state, 'Arad'), undefined

state = routeFindingProblem.result state, 'Arad'
assert.equal state, undefined

Touring Problem

Confer section 3.2.2, p. 74.

export makeTouringProblem = (graph, start, end) ->
  new SearchProblem
    initialState: [start]
    actions: (state) ->
      Object.keys graph.dist[state[state.length - 1]]
        .filter (city) -> not state.includes city
    result: (state, action) ->
      if action of graph.dist[state[state.length - 1]]
        [...state, action]
    stepCost: (state, action) ->
      graph.dist[state[state.length - 1]][action]
    heuristic: (state) ->
      graph.straightLineDist[state[state.length - 1]][end]
    goalTest: (state) ->
      deepEqual state[state.length - 1], end

touringProblem = makeTouringProblem cities, 'Arad', 'Bucharest'

state = touringProblem.initialState
assert.deepEqual state, ['Arad']
assert.equal (touringProblem.stepCost state, 'Sibiu'), 140

state = touringProblem.result state, 'Sibiu'
assert.deepEqual state, ['Arad', 'Sibiu']
assert.equal (touringProblem.stepCost state, 'RimnicuVilcea'), 80

state = touringProblem.result state, 'RimnicuVilcea'
assert.deepEqual state, ['Arad', 'Sibiu', 'RimnicuVilcea']
assert.equal (touringProblem.stepCost state, 'Sibiu'), undefined

state = touringProblem.result state, 'Sibiu'
assert.deepEqual state, undefined

Traveling Salesperson Problem

Confer section 3.2.2, p. 74.

export makeTravelingSalespersonProblem = (graph, start, end) ->
  new SearchProblem
    initialState: [start]
    actions: (state) ->
      Object.keys graph.dist[state[state.length - 1]]
        .filter (city) -> not state.includes city
    result: (state, action) -> [...state, action]
    stepCost: (state, action) ->
      graph.dist[state[state.length - 1]][action]
    goalTest: (state) ->
      state.length == (Object.keys graph.dist).length and
      state[state.length - 1] == end

travelingSalespersonProblem = makeTravelingSalespersonProblem cities, 'Arad', 'Bucharest'

state = travelingSalespersonProblem.initialState
assert.deepEqual state, ['Arad']
assert.equal (travelingSalespersonProblem.stepCost state, 'Sibiu'), 140

state = travelingSalespersonProblem.result state, 'Sibiu'
assert.deepEqual state, ['Arad', 'Sibiu']
assert.equal (travelingSalespersonProblem.stepCost state, 'Arad'), undefined

state = travelingSalespersonProblem.result state, 'Arad'
assert.deepEqual state, undefined

Tree Search

Confer section 3.3, p. 77.

export makeTreeSearch = (Queue) ->
  (problem) ->
    frontier = new Queue
    frontier.add problem.initialState.rootNode()
    while frontier.length > 0
      node = frontier.poll()
      if problem.goalTest node.state
        return node
      (frontier.add child) for child of problem.expand node
    false

Graph Search

Confer section 3.3, p. 77.

export makeGraphSearch = (Queue) ->
  (problem) ->
    frontier = new Queue
    frontier.add problem.rootNode()
    explored = new Set
    while frontier.length() > 0
      node = frontier.poll()
      if problem.goalTest node.state
        return node
      explored.add node
      for child in problem.expand node
        if (not explored.has child) and
        not frontier.some (node) -> node.state == child.state
          frontier.add child
        else if frontier.constructor.name == 'PriorityQueue'
          frontierChild = frontier
            .find (node) -> deepEqual node.state, child.state
          if typeof frontierChild != 'undefined' and
          frontierChild.pathCost > child.pathCost
            frontier.replace frontierChild, child
    false

Queues

Confer section 3.3.1, p. 80.

export class Queue
  constructor: ->
    @queue = []

  add: (item) ->
    @queue.push item

  some: (func) ->
    @queue.some func

  find: (func) ->
    @queue.find func

  replace: (a, b) ->
    @queue[@queue.indexOf a] = b

  length: ->
    @queue.length

FIFO Queue

export class FifoQueue extends Queue
  poll: ->
    @queue.shift()

LIFO Queue (Stack)

export class LifoQueue extends Queue
  poll: ->
    @queue.pop()

Priority Queue

export makePriorityQueue = (mapFunc) ->
  class PriorityQueue extends Queue
    constructor: ->
      super()
      @mapFunc = mapFunc
      @sortFunc = (a, b) -> mapFunc(a) - mapFunc(b)

    poll: ->
      @queue = @queue.sort @sortFunc
      @queue.shift()

    sort: ->
      @queue = @queue.sort @sortFunc

Uninformed Search

Breadth-First Search

Confer section 3.4.1, p. 82.

export breadthFirstSearch = makeGraphSearch FifoQueue

assert.deepEqual (Problem.solutionPath breadthFirstSearch vacuumWorld), [
  { location: 'A', A: 'dirty', B: 'dirty' }
  { location: 'A', A: 'clean', B: 'dirty' }
  { location: 'B', A: 'clean', B: 'dirty' }
  { location: 'B', A: 'clean', B: 'clean' }]
assert.deepEqual (Problem.solutionPath breadthFirstSearch simpleEightPuzzle), [
  [ [ 1, 4, 2 ]
    [ 3, 0, 5 ]
    [ 6, 7, 8 ] ]
  [ [ 1, 0, 2 ]
    [ 3, 4, 5 ]
    [ 6, 7, 8 ] ]
  [ [ 0, 1, 2 ]
    [ 3, 4, 5 ]
    [ 6, 7, 8 ] ] ]
assert.deepEqual (breadthFirstSearch incrementalEightQueensProblem).state, [
  [1, 0, 0, 0, 0, 0, 0, 0]
  [0, 0, 0, 0, 1, 0, 0, 0]
  [0, 0, 0, 0, 0, 0, 0, 1]
  [0, 0, 0, 0, 0, 1, 0, 0]
  [0, 0, 1, 0, 0, 0, 0, 0]
  [0, 0, 0, 0, 0, 0, 1, 0]
  [0, 1, 0, 0, 0, 0, 0, 0]
  [0, 0, 0, 1, 0, 0, 0, 0]
].map (row) -> row.indexOf 1
assert.deepEqual (breadthFirstSearch simpleKnuthConjecture).state, \
  [4, 'square_root', 'square_root', 'floor']
assert.deepEqual (Problem.solutionPath breadthFirstSearch routeFindingProblem), \
  [ 'Arad', 'Sibiu', 'Fagaras', 'Bucharest' ]
assert.deepEqual (breadthFirstSearch touringProblem).state, \
  [ 'Arad', 'Sibiu', 'Fagaras', 'Bucharest' ]
assert.equal (breadthFirstSearch travelingSalespersonProblem), false

Uniform Cost Search

Confer section 3.4.2, p. 84.

export uniformCostSearch = makeGraphSearch makePriorityQueue (node) -> node.pathCost

assert.deepEqual (Problem.solutionPath uniformCostSearch vacuumWorld), [
  { location: 'A', A: 'dirty', B: 'dirty' }
  { location: 'A', A: 'clean', B: 'dirty' }
  { location: 'B', A: 'clean', B: 'dirty' }
  { location: 'B', A: 'clean', B: 'clean' }]
assert.deepEqual (Problem.solutionPath uniformCostSearch simpleEightPuzzle), [
  [ [ 1, 4, 2 ]
    [ 3, 0, 5 ]
    [ 6, 7, 8 ] ]
  [ [ 1, 0, 2 ]
    [ 3, 4, 5 ]
    [ 6, 7, 8 ] ]
  [ [ 0, 1, 2 ]
    [ 3, 4, 5 ]
    [ 6, 7, 8 ] ]]
assert.deepEqual (uniformCostSearch incrementalEightQueensProblem).state, [
  [1, 0, 0, 0, 0, 0, 0, 0]
  [0, 0, 0, 0, 1, 0, 0, 0]
  [0, 0, 0, 0, 0, 0, 0, 1]
  [0, 0, 0, 0, 0, 1, 0, 0]
  [0, 0, 1, 0, 0, 0, 0, 0]
  [0, 0, 0, 0, 0, 0, 1, 0]
  [0, 1, 0, 0, 0, 0, 0, 0]
  [0, 0, 0, 1, 0, 0, 0, 0]
].map (row) -> row.indexOf 1
assert.deepEqual (uniformCostSearch simpleKnuthConjecture).state, \
  [4, 'square_root', 'square_root', 'floor']
assert.deepEqual (Problem.solutionPath uniformCostSearch routeFindingProblem), \
  [ 'Arad', 'Sibiu', 'RimnicuVilcea', 'Pitesti', 'Bucharest' ]
assert.deepEqual (uniformCostSearch touringProblem).state, \
  [ 'Arad', 'Sibiu', 'RimnicuVilcea', 'Pitesti', 'Bucharest' ]
assert.equal (uniformCostSearch travelingSalespersonProblem), false

Depth-First Search

Confer section 3.4.3, p. 87.

export depthFirstSearch = makeGraphSearch LifoQueue

assert.deepEqual (depthFirstSearch incrementalEightQueensProblem).state, [
  [0, 0, 0, 0, 0, 0, 0, 1]
  [0, 0, 0, 1, 0, 0, 0, 0]
  [1, 0, 0, 0, 0, 0, 0, 0]
  [0, 0, 1, 0, 0, 0, 0, 0]
  [0, 0, 0, 0, 0, 1, 0, 0]
  [0, 1, 0, 0, 0, 0, 0, 0]
  [0, 0, 0, 0, 0, 0, 1, 0]
  [0, 0, 0, 0, 1, 0, 0, 0]
].map (row) -> row.indexOf 1
assert.deepEqual (depthFirstSearch touringProblem).state, [
  'Arad',
  'Timisoara',
  'Lugoj',
  'Mehadia',
  'Drobeta',
  'Craiova',
  'RimnicuVilcea',
  'Pitesti',
  'Bucharest'
] # depends on the (arbitrary) order of attributes in the cities graph
assert.equal (depthFirstSearch travelingSalespersonProblem), false

Depth-Limited Search

Confer section 3.4.4, p. 88.

export depthLimitedSearch = (problem, limit) ->
  recursiveDepthLimitedSearch problem.rootNode(), problem, limit

recursiveDepthLimitedSearch = (node, problem, limit) ->
  if problem.goalTest node.state
    node
  else if limit == 0
    'cutoff'
  else
    cutoffOccurred = false
    for child in problem.expand node
      result = recursiveDepthLimitedSearch child, problem, limit - 1
      if result == 'cutoff'
        cutoffOccurred = true
      else if result
        return result
    if cutoffOccurred
      'cutoff'
    else
      false

assert.equal (depthLimitedSearch vacuumWorld, 2), 'cutoff'
assert.deepEqual (Problem.solutionPath (depthLimitedSearch vacuumWorld, 3)), [
  { location: 'A', A: 'dirty', B: 'dirty' }
  { location: 'A', A: 'clean', B: 'dirty' }
  { location: 'B', A: 'clean', B: 'dirty' }
  { location: 'B', A: 'clean', B: 'clean' }]

assert.equal (depthLimitedSearch simpleEightPuzzle, 1), 'cutoff'
assert simpleEightPuzzle.goalTest (depthLimitedSearch simpleEightPuzzle, 2).state

assert.deepEqual (depthLimitedSearch incrementalEightQueensProblem, 8).state, [
  [1, 0, 0, 0, 0, 0, 0, 0]
  [0, 0, 0, 0, 1, 0, 0, 0]
  [0, 0, 0, 0, 0, 0, 0, 1]
  [0, 0, 0, 0, 0, 1, 0, 0]
  [0, 0, 1, 0, 0, 0, 0, 0]
  [0, 0, 0, 0, 0, 0, 1, 0]
  [0, 1, 0, 0, 0, 0, 0, 0]
  [0, 0, 0, 1, 0, 0, 0, 0]
].map (row) -> row.indexOf 1

assert.equal (depthLimitedSearch simpleKnuthConjecture, 2), 'cutoff'
assert (depthLimitedSearch simpleKnuthConjecture, 3).state, 1

assert.deepEqual (Problem.solutionPath (depthLimitedSearch routeFindingProblem, 4)), \
  ['Arad', 'Sibiu', 'Fagaras', 'Bucharest']

assert.deepEqual (depthLimitedSearch touringProblem, 4).state, \
  ['Arad', 'Sibiu', 'Fagaras', 'Bucharest']

assert.equal (depthLimitedSearch travelingSalespersonProblem, 20), false

Iterative Deepening Search

Confer section 3.4.5, p. 89.

export iterativeDeepeningSearch = (problem) ->
  recursiveIterativeDeepeningSearch problem, 0

recursiveIterativeDeepeningSearch = (problem, depth) ->
  result = depthLimitedSearch problem, depth
  if result != 'cutoff'
    result
  else
    recursiveIterativeDeepeningSearch problem, (depth + 1)

assert.deepEqual (Problem.solutionPath iterativeDeepeningSearch vacuumWorld), [
  { location: 'A', A: 'dirty', B: 'dirty' }
  { location: 'A', A: 'clean', B: 'dirty' }
  { location: 'B', A: 'clean', B: 'dirty' }
  { location: 'B', A: 'clean', B: 'clean' }]
assert.deepEqual (Problem.solutionPath iterativeDeepeningSearch simpleEightPuzzle), [
  [ [ 1, 4, 2 ]
    [ 3, 0, 5 ]
    [ 6, 7, 8 ] ]
  [ [ 1, 0, 2 ]
    [ 3, 4, 5 ]
    [ 6, 7, 8 ] ]
  [ [ 0, 1, 2 ]
    [ 3, 4, 5 ]
    [ 6, 7, 8 ] ]]
assert.deepEqual (iterativeDeepeningSearch incrementalEightQueensProblem).state, [
  [1, 0, 0, 0, 0, 0, 0, 0]
  [0, 0, 0, 0, 1, 0, 0, 0]
  [0, 0, 0, 0, 0, 0, 0, 1]
  [0, 0, 0, 0, 0, 1, 0, 0]
  [0, 0, 1, 0, 0, 0, 0, 0]
  [0, 0, 0, 0, 0, 0, 1, 0]
  [0, 1, 0, 0, 0, 0, 0, 0]
  [0, 0, 0, 1, 0, 0, 0, 0]
].map (row) -> row.indexOf 1
assert.deepEqual (iterativeDeepeningSearch simpleKnuthConjecture).state, \
  [4, 'square_root', 'square_root', 'floor']
assert.deepEqual (Problem.solutionPath iterativeDeepeningSearch routeFindingProblem), \
  [ 'Arad', 'Sibiu', 'Fagaras', 'Bucharest' ]
assert.deepEqual (iterativeDeepeningSearch touringProblem).state, \
  [ 'Arad', 'Sibiu', 'Fagaras', 'Bucharest' ]
assert.equal (iterativeDeepeningSearch travelingSalespersonProblem), false

Heuristic Search

Greedy Best-First Search

Confer section 3.5.1, p. 92.

export greedySearch = makeGraphSearch \
  makePriorityQueue (node) -> node.heuristic

assert.deepEqual (Problem.solutionPath greedySearch vacuumWorld), [
  { location: 'A', A: 'dirty', B: 'dirty' }
  { location: 'A', A: 'clean', B: 'dirty' }
  { location: 'B', A: 'clean', B: 'dirty' }
  { location: 'B', A: 'clean', B: 'clean' }]
assert.deepEqual (Problem.solutionPath greedySearch simpleEightPuzzle), [
  [ [ 1, 4, 2 ]
    [ 3, 0, 5 ]
    [ 6, 7, 8 ] ]
  [ [ 1, 0, 2 ]
    [ 3, 4, 5 ]
    [ 6, 7, 8 ] ]
  [ [ 0, 1, 2 ]
    [ 3, 4, 5 ]
    [ 6, 7, 8 ] ]]
assert.deepEqual (greedySearch incrementalEightQueensProblem).state, [
  [1, 0, 0, 0, 0, 0, 0, 0]
  [0, 0, 0, 0, 1, 0, 0, 0]
  [0, 0, 0, 0, 0, 0, 0, 1]
  [0, 0, 0, 0, 0, 1, 0, 0]
  [0, 0, 1, 0, 0, 0, 0, 0]
  [0, 0, 0, 0, 0, 0, 1, 0]
  [0, 1, 0, 0, 0, 0, 0, 0]
  [0, 0, 0, 1, 0, 0, 0, 0]
].map (row) -> row.indexOf 1
assert.deepEqual (greedySearch simpleKnuthConjecture).state, \
  [4, 'square_root', 'square_root', 'floor']
assert.deepEqual (Problem.solutionPath greedySearch routeFindingProblem), \
  [ 'Arad', 'Sibiu', 'Fagaras', 'Bucharest' ]
assert.deepEqual (greedySearch touringProblem).state, \
  [ 'Arad', 'Sibiu', 'Fagaras', 'Bucharest' ]
assert.equal (greedySearch travelingSalespersonProblem), false

A* Search

Confer section 3.5.2, p. 93.

export aStarSearch  = makeGraphSearch \
  makePriorityQueue (node) -> node.pathCost + node.heuristic

assert.deepEqual (Problem.solutionPath aStarSearch vacuumWorld), [
  { location: 'A', A: 'dirty', B: 'dirty' }
  { location: 'A', A: 'clean', B: 'dirty' }
  { location: 'B', A: 'clean', B: 'dirty' }
  { location: 'B', A: 'clean', B: 'clean' }]
assert.deepEqual (Problem.solutionPath aStarSearch simpleEightPuzzle), [
  [ [ 1, 4, 2 ]
    [ 3, 0, 5 ]
    [ 6, 7, 8 ] ]
  [ [ 1, 0, 2 ]
    [ 3, 4, 5 ]
    [ 6, 7, 8 ] ]
  [ [ 0, 1, 2 ]
    [ 3, 4, 5 ]
    [ 6, 7, 8 ] ]]
assert.deepEqual (aStarSearch incrementalEightQueensProblem).state, [
  [1, 0, 0, 0, 0, 0, 0, 0]
  [0, 0, 0, 0, 1, 0, 0, 0]
  [0, 0, 0, 0, 0, 0, 0, 1]
  [0, 0, 0, 0, 0, 1, 0, 0]
  [0, 0, 1, 0, 0, 0, 0, 0]
  [0, 0, 0, 0, 0, 0, 1, 0]
  [0, 1, 0, 0, 0, 0, 0, 0]
  [0, 0, 0, 1, 0, 0, 0, 0]
].map (row) -> row.indexOf 1
assert.deepEqual (aStarSearch simpleKnuthConjecture).state, \
  [4, 'square_root', 'square_root', 'floor']
assert.deepEqual (Problem.solutionPath aStarSearch routeFindingProblem), \
  [ 'Arad', 'Sibiu', 'RimnicuVilcea', 'Pitesti', 'Bucharest' ]
assert.deepEqual (aStarSearch touringProblem).state, \
  [ 'Arad', 'Sibiu', 'RimnicuVilcea', 'Pitesti', 'Bucharest' ]
assert.equal (aStarSearch travelingSalespersonProblem), false

Optimisation

Confer section 4.1, p. 121.

export class OptimizationProblem extends Problem
  constructor: ({ initialState, actions, result, @value }) ->
    super
      initialState: initialState,
      actions: actions,
      result: result

  rootNode: -> {
    ...super()
    value: @value @initialState
  }

  childNode: (node, action) -> {
    ...super node, action
    value: @value @result node.state, action
  }

Complete-State 8-Queens Problem

Complete-state formulation of the 8-queens problem. From section 4.1.1, p. 122.

export completeStateEightQueensProblem = new OptimizationProblem
  initialState: [
    [1, 0, 0, 0, 0, 0, 0, 0]
    [1, 0, 0, 0, 0, 0, 0, 0]
    [1, 0, 0, 0, 0, 0, 0, 0]
    [1, 0, 0, 0, 0, 0, 0, 0]
    [1, 0, 0, 0, 0, 0, 0, 0]
    [1, 0, 0, 0, 0, 0, 0, 0]
    [1, 0, 0, 0, 0, 0, 0, 0]
    [1, 0, 0, 0, 0, 0, 0, 0]
  ]
  actions: (state) ->
    state.reduce (total, row, y) ->
      [
        ...total,
        ...[0, 1, 2, 3, 4, 5, 6, 7]
          .filter (x) -> row[x] == 0
          .map (x) -> [y, x]
      ]
    , []
  result: (state, [yMove, xMove]) ->
    state.map (row, y) ->
      row.map (tile, x) ->
        if y == yMove
          if x == xMove
            1
          else
            0
        else
          tile
  value: (state) -> -nrAttackedQueens state

nrAttackedQueens = (state) ->
  attacks = ([y1, x1], [y2, x2]) ->
    y1 == y2 or
    x1 == x2 or
    y2 - y1 == x2 - x1
  combinations \
    state.map (row, y) ->
      [y, row.indexOf 1]
    .sum ([q1, q2]) ->
      attacks(q1, q2) * 1

combinations = (array) ->
  array.reduce (prev, a, i) -> 
    [
      ...prev,
      ...array
        .slice 0, i
        .map (b) -> [a, b]
    ]
  , []

state = completeStateEightQueensProblem.initialState
assert.equal (completeStateEightQueensProblem.actions state).length, 8 * (8 - 1)
assert.equal (completeStateEightQueensProblem.value state), -(8**2 - 8) / 2

state = completeStateEightQueensProblem.result state, [3, 6]
assert.deepEqual state, [
  [1, 0, 0, 0, 0, 0, 0, 0],
  [1, 0, 0, 0, 0, 0, 0, 0],
  [1, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 1, 0],
  [1, 0, 0, 0, 0, 0, 0, 0],
  [1, 0, 0, 0, 0, 0, 0, 0],
  [1, 0, 0, 0, 0, 0, 0, 0],
  [1, 0, 0, 0, 0, 0, 0, 0]
]
assert.equal (completeStateEightQueensProblem.value state), -(28 - 7)

Hill-Climbing Search

Confer section 4.1.1, p. 122.

export hillClimbingSearch = (problem) ->
  recursiveHillClimbingSearch problem, problem.rootNode()

recursiveHillClimbingSearch = (problem, current) ->
  neighbor = (problem.expand current)
    .argmax (x) -> x.value
  if neighbor.value <= current.value
    current
  else
    recursiveHillClimbingSearch problem, neighbor

solution = (hillClimbingSearch completeStateEightQueensProblem).state
assert.deepEqual solution, [
  [0, 1, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 1, 0, 0, 0, 0],
  [0, 0, 1, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 1, 0],
  [1, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 1, 0, 0, 0],
  [1, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 1, 0, 0]
]

Simulated Annealing

Also known as Gradient Descent. From section 4.1.2, p. 126.

Parameter random: A random number generator function. Use seeded function for testing!

export simulatedAnnealing = (problem, schedule, random = Math.random) ->
  schedule ?= (time) -> 1 / time
  randEl = (array) -> array[Math.floor(random() * array.length)]
  current = problem.rootNode()
  time = 1
  temp = schedule 1
  next
  evalSlope
  while temp > 0
    temp = schedule time
    if (temp == 0)
      return current
    next = randEl problem.expand current
    evalSlope = next.value - current.value
    if evalSlope > 0
      current = next
    else if (Math.E**(evalSlope / temp) * random()) > 0.5
      current = next
    time += 1

nSteps = 2
assert.equal \
  (simulatedAnnealing completeStateEightQueensProblem, ((t) -> 1/t - 1/nSteps), rand.random).value, \
  -22

For nSteps = 100, this solves the problem (value == -0). This is excluded from testing because it takes too long.

Games

Confer section 5.1, p. 162.

export class Game extends Problem
  constructor: ({ 
    initialState, @player, actions, result, @terminalTest, utility, @heuristic = ((state) -> 0)
  }) ->
    super
      initialState: initialState
      actions: actions
      result: result
    @_utility = utility

  utility: (state) ->
    @_utility state if @terminalTest state

  rootNode: -> {
    ...super()
    player: @player @initialState
  }

  childNode: (node, action) -> {
    ...super node, action
    player: @player @initialState
  }

Tic Tac Toe

Confer section 5.1, p. 163.

export ticTacToe = new Game
  initialState: [
    [' ', ' ', ' ']
    [' ', ' ', ' ']
    [' ', ' ', ' ']
  ]
  player: (state) ->
    if (count state, 'x') > (count state, 'o')
      'o'
    else
      'x'
  actions: (state) -> [
    [0, 0], [0, 1], [0, 2]
    [1, 0], [1, 1], [1, 2]
    [2, 0], [2, 1], [2, 2]
  ].filter ([y, x]) ->
      state[y][x] == ' '
  result: (state, [yMove, xMove]) ->
    state.map (row, y) ->
      row.map (tile, x) ->
        if y == yMove and x == xMove
          ticTacToe.player state
        else
          tile
  terminalTest: (state) ->
    (threeInaRow state, 'x') or
    (threeInaRow state, 'o')
  utility: (state) ->
    1 * (threeInaRow state, 'x')

threeInaRow = (state, p) -> [
    [ [0, 0], [0, 1], [0, 2] ] # horizontal
    [ [1, 0], [1, 1], [1, 2] ] # horizontal
    [ [2, 0], [2, 1], [2, 2] ] # horizontal
    [ [0, 0], [1, 0], [2, 0] ] # vertical
    [ [0, 1], [1, 1], [2, 1] ] # vertical
    [ [0, 2], [1, 2], [2, 2] ] # vertical
    [ [0, 0], [1, 1], [2, 3] ] # diagonal
    [ [0, 2], [1, 2], [2, 0] ] # diagonal
  ].some (row) ->
    row.every ([y, x]) ->
      state[y][x] == p

count = (state, x) ->
  state
    .flat()
    .filter (square) -> square == x
    .length

state = ticTacToe.initialState

state = ticTacToe.result state, [1, 0]
assert.deepEqual state, [
  [' ', ' ', ' ']
  ['x', ' ', ' ']
  [' ', ' ', ' ']
]

state = ticTacToe.result state, [2, 0]
assert.deepEqual state, [
  [' ', ' ', ' ']
  ['x', ' ', ' ']
  ['o', ' ', ' ']
]

state = ticTacToe.result state, [1, 1]
assert.deepEqual state, [
  [' ', ' ', ' ']
  ['x', 'x', ' ']
  ['o', ' ', ' ']
]

state = ticTacToe.result state, [2, 1]
assert.deepEqual state, [
  [' ', ' ', ' ']
  ['x', 'x', ' ']
  ['o', 'o', ' ']
]

assert not ticTacToe.terminalTest state
assert.equal ticTacToe.utility(state), undefined

state = ticTacToe.result state, [1, 2]
assert.deepEqual state, [
  [' ', ' ', ' ']
  ['x', 'x', 'x']
  ['o', 'o', ' ']
]
assert ticTacToe.terminalTest state
assert.equal ticTacToe.utility(state), 1

MiniMax Algorithm

Confer section 5.2.1, p. 166. Pseudocode.

Changes to the pseudocode:

• A depth limit has been added (Infinity by default).
• maximinDecision has been added for player Min in analogy to minimaxDecision for player Max. This is applicable to zero-sum games only. Note that the terms 'maximin' and 'minimax' are generally used inconsistently.
• The notation is functional.

export minimaxDecision = (game, state, limit = Infinity) ->
  game.actions state
    .map (action) ->
      action: action
      outcome: minValue game, (game.result state, action), limit - 1
    .argmax (x) -> x.outcome

export maximinDecision = (game, state, limit = Infinity) ->
  game.actions state
    .map (action) ->
      action: action
      outcome: maxValue game, (game.result state, action), limit - 1
    .argmin (x) -> x.outcome

maxValue = (game, state, limit) ->
  if game.terminalTest state
    game.utility state
  else
    if limit < 1
      game.heuristic state
    else
      game.actions state
        .reduce (prev, current) ->
          Math.max prev, (minValue game, (game.result state, current), limit - 1)
        , -Infinity

minValue = (game, state, limit) ->
  if game.terminalTest state
    game.utility state
  else
    if limit < 1
      game.heuristic state
    else
      game.actions state
        .reduce (prev, current) ->
          Math.min prev, (maxValue game, (game.result state, current), limit - 1)
        , Infinity

The minimaxDecision algorithm is tested at the end of the next section, together with the alphaBetaSearch algorithm.

Alpha-Beta Search

Confer section 5.3, p. 170. Pseudocode.

Changes to the pseudocode:

• A depth limit has been added (Infinity by default).
• betaAlphaSearch has been added for player Min in analogy to alphaBetaSearch for player Max. This is applicable to zero-sum games only.

export alphaBetaSearch = (game, state, limit = Infinity) ->
  game.actions state
    .map (action) ->
      action: action,
      outcome: alphaBetaMinValue game, (game.result state, action), limit - 1, -Infinity, +Infinity
    .argmax (x) -> x.outcome

export betaAlphaSearch = (game, state, limit = Infinity) ->
  game.actions state
    .map (action) ->
      action: action,
      outcome: alphaBetaMaxValue game, (game.result state, action), limit - 1, -Infinity, +Infinity
    .argmin (x) -> x.outcome

alphaBetaMaxValue = (game, state, limit, alpha, beta) ->
  if game.terminalTest state
    game.utility state
  if limit < 1
    game.heuristic state
  v = -Infinity
  for action in game.actions state
    v = Math.max v, (alphaBetaMinValue game, (game.result state, action), limit, alpha, beta)
    if v >= beta
      v
    alpha = Math.max alpha, v
  v

alphaBetaMinValue = (game, state, limit, alpha, beta) ->
  if game.terminalTest state
    game.utility state
  if limit < 1
    game.heuristic state
  v = +Infinity
  for action in game.actions state
    v = Math.min v, (alphaBetaMaxValue game, (game.result state, action), limit, alpha, beta)
    if v <= alpha
      v
    beta = Math.min beta, v
  v

for algorithm in [minimaxDecision, alphaBetaSearch]
  state = [
    ['x', 'o', 'x']
    ['o', 'x', 'x']
    [' ', 'o', ' ']
  ]

  # player 2
  decision = algorithm ticTacToe, state
  state = ticTacToe.result state, decision.action
  assert.deepEqual state, [
    ['x', 'o', 'x']
    ['o', 'x', 'x']
    ['o', 'o', ' ']
  ]
  assert not ticTacToe.terminalTest state
  assert.equal ticTacToe.utility(state), undefined

  # player 1
  decision = algorithm ticTacToe, state
  state = ticTacToe.result state, decision.action
  assert.deepEqual state, [
    ['x', 'o', 'x']
    ['o', 'x', 'x']
    ['o', 'o', 'x']
  ]
  assert ticTacToe.terminalTest state
  assert.equal ticTacToe.utility(state), 1

Constraint Satisfaction

Confer section 6.1, p. 202.

export class ConstraintSatisfactionProblem extends SearchProblem
  constructor: ({ domains, constraints }) ->
    get = (pairList, key) ->
      pairList.find(([key2, value]) -> key == key2)[1]
    super
      initialState: []
      actions: (state) ->
        if state.length < domains.length
          domains[state.length][1]
            .map (value) ->
              [domains[state.length][0], value]
        else
          []
      result: (state, action) -> [...state, action]
      stepCost: (state) -> 0
      goalTest: (state) ->
        state.length == domains.length and
        (domains.every ([varName, domain]) ->
          domain.some (v) ->
            deepEqual v, (get state, varName)) and
        constraints.every ([varList, constraint]) ->
          varList.every (vars) ->
            constraint \
              ...vars.map (varName) ->
                get state, varName
    @domains     = domains
    @constraints = constraints

  variables: ->
    @domains.keys()

  satisfied: (solution) ->
    @goalTest solution

Map Coloring Problem

Confer section 6.1.1, p. 203.

export mapColoringProblem = new ConstraintSatisfactionProblem
  domains: ['WA', 'NT', 'Q', 'NSW', 'V', 'SA', 'T'] \
    .map (state) -> [state, ['red', 'green', 'blue'] ]
  constraints: [
    [
      [
        ['SA' , 'WA' ]
        ['SA' , 'NT' ]
        ['SA' , 'Q'  ]
        ['SA' , 'NSW']
        ['SA' , 'V'  ]
        ['WA' , 'NT' ]
        ['NT' , 'Q'  ]
        ['Q'  , 'NSW']
        ['NSW', 'V'  ]
      ]
      (a, b) -> a != b
    ]
  ]

state = mapColoringProblem.initialState
assert.deepEqual state, []
assert not mapColoringProblem.satisfied state
assert.deepEqual (mapColoringProblem.actions state), [['WA', 'red'], ['WA', 'green'], ['WA', 'blue']]

state = mapColoringProblem.result state, ['WA', 'red']
assert.deepEqual state, [['WA', 'red']]
assert not mapColoringProblem.satisfied state
assert.deepEqual (mapColoringProblem.actions state), [['NT', 'red'], ['NT', 'green'], ['NT', 'blue']]

state = mapColoringProblem.result state, ['NT', 'green']
assert.deepEqual state, [['WA', 'red'], ['NT', 'green']]
assert not mapColoringProblem.satisfied state
assert.deepEqual (mapColoringProblem.actions state), [['Q', 'red'], ['Q', 'green'], ['Q', 'blue']]

solution = [
  ['WA' , 'blue' ]
  ['NT' , 'green']
  ['Q'  , 'red'  ]
  ['NSW', 'green']
  ['V'  , 'red'  ]
  ['SA' , 'blue' ]
  ['T'  , 'red'  ]
]
assert not mapColoringProblem.satisfied solution

solution = [
  ['WA' , 'red' ]
  ['NT' , 'green']
  ['Q'  , 'red'  ]
  ['NSW', 'green']
  ['V'  , 'red'  ]
  ['SA' , 'green' ]
  ['T'  , 'red'  ]
]
assert not mapColoringProblem.satisfied solution

solution = [
  ['WA' , 'red'  ]
  ['NT' , 'green']
  ['Q'  , 'red'  ]
  ['NSW', 'green']
  ['V'  , 'blue' ]
  ['SA' , 'blue' ]
  ['T'  , 'red'  ]
]
assert not mapColoringProblem.satisfied solution

solution = [
  ['WA' , 'red'  ]
  ['NT' , 'green']
  ['Q'  , 'red'  ]
  ['NSW', 'green']
  ['V'  , 'red'  ]
  ['SA' , 'blue' ]
  ['T'  , 'red'  ]
]
assert mapColoringProblem.satisfied solution

assert.deepEqual (depthFirstSearch mapColoringProblem).state, [
  ['WA' , 'blue' ]
  ['NT' , 'green']
  ['Q'  , 'blue' ]
  ['NSW', 'green']
  ['V'  , 'blue' ]
  ['SA' , 'red'  ]
  ['T'  , 'blue' ]
]

Constraint-Satisfaction 8-Queens Problem

Constraint-satisfaction formulation of the eight-queens problem. Confer section 6.1.3, p. 205.

export constraintSatisfactionEightQueensProblem = new ConstraintSatisfactionProblem
  domains: [0, 1, 2, 3, 4, 5, 6, 7].map (queen) -> [
    queen
    [0, 1, 2, 3, 4, 5, 6, 7].flatMap (y) ->
      [0, 1, 2, 3, 4, 5, 6, 7].map (x) ->
        [y, x]
  ]
  constraints: [
    [
      [0, 1, 2, 3, 4, 5, 6, 7].flatMap (queen1) ->
        [0, 1, 2, 3, 4, 5, 6, 7]
          .filter (queen2) -> queen1 != queen2
          .map (queen2) -> [queen1, queen2]
      (a, b) ->
        attacks = ([y1, x1], [y2, x2]) -> 
          y1 == y2 or
          x1 == x2 or
          y2 - y1 == x2 - x1
        not attacks a, b
    ]
  ]

solution = [
  [1, 0, 0, 0, 0, 0, 0, 0]
  [0, 0, 0, 0, 0, 0, 0, 1]
  [0, 0, 0, 0, 1, 0, 0, 0]
  [0, 0, 0, 0, 0, 1, 0, 0]
  [0, 0, 1, 0, 0, 0, 0, 0]
  [0, 0, 0, 0, 0, 0, 1, 0]
  [0, 1, 0, 0, 0, 0, 0, 0]
  [0, 0, 0, 1, 0, 0, 0, 0]
].map (row, y) -> [y, [y, row.findIndex (x) -> x == 1] ]
assert not constraintSatisfactionEightQueensProblem.satisfied solution

solution = [
  [1, 0, 0, 0, 0, 0, 0, 0]
  [0, 0, 0, 0, 1, 0, 0, 0]
  [0, 0, 0, 0, 0, 0, 0, 1]
  [0, 0, 0, 0, 0, 1, 0, 0]
  [0, 0, 1, 0, 0, 0, 0, 0]
  [0, 0, 0, 0, 0, 0, 1, 0]
  [0, 1, 0, 0, 0, 0, 0, 0]
  [0, 0, 0, 1, 0, 0, 0, 0]
].map (row, y) -> [y, [y, row.findIndex (x) -> x == 1] ]
assert constraintSatisfactionEightQueensProblem.satisfied solution

Node Consistency

Confer section 6.2.1, p. 208.

export makeNodeConsistent = (problem) ->
  new ConstraintSatisfactionProblem
    domains: problem.domains.map ([varName, domain]) ->
      [
        varName,
        domain.filter (value) ->
          applicableUnaryConstraints problem.constraints, varName
            .every ([varList, constraintFunc]) ->
              constraintFunc value
      ]
    constraints: nonUnaryConstraints problem.constraints

applicableUnaryConstraints = (constraints, varName) ->
  unaryConstraints constraints
    .filter (constraint) ->
      constraint[0].some (varName2) ->
        varName2 == varName

unaryConstraints = (constraints) ->
  constraints.filter (constraint) -> constraint[1].length == 1

nonUnaryConstraints = (constraints) ->
  constraints.filter (constraint) -> constraint[1].length > 1

problem = new ConstraintSatisfactionProblem
  domains: [
    ['Northern Australia', ['red', 'blue', 'green'] ]
    ['Southern Australia', ['red', 'blue', 'green'] ]
  ]
  constraints: [
    [['Northern Australia', 'Southern Australia'], (a, b) -> a != b]
    [['Southern Australia'], (a) -> a != 'green']
  ]

problem = makeNodeConsistent problem
assert.deepEqual problem.domains, [
  ['Northern Australia', ['red', 'blue', 'green']]
  ['Southern Australia', ['red', 'blue']]
]

Logic

The following syntax of propositional logic is currently used (in deviation from the book syntax). It would be desirable to refactor the syntax to match the book.

• Operator symbols: ~, &, |, >, =
• Truth symbols: T, F
• Compulsory brackets around each expression. This is pretty ugly.

Confer section 7.4.1, p. 244.

Syntax of Propositional Logic

export plParse = (sentence, vars) ->
  recursiveParse sentence.split(''), vars

unaryOperators  = ['~']
binaryOperators = ['&', '|', '>', '=']
operators       = [...unaryOperators, ...binaryOperators]

recursiveParse = (sentence, vars) ->
  if (levels sentence)[sentence.length - 1] == 0 and
  sentence[0] == '(' and
  sentence[sentence.length - 1] == ')'
    if (levels sentence).some (level) -> level > 1
      if (operatorIndex sentence) > -1
        [
          (sentence.slice \
            (operatorIndex sentence), \
            (operatorIndex sentence) + 1 \
          )[0],
          ...if not unaryOperators.includes sentence[operatorIndex sentence]
            [recursiveParse (sentence.slice 1, operatorIndex sentence), vars]
          else
            []
          recursiveParse (sentence.slice (operatorIndex sentence) + 1, -1)
        ]
      else
        recursiveParse sentence.slice 1, -1
    else if operators.some (operator) -> sentence.includes operator
      'ERROR'
    else if sentence.length == 3 and sentence[1] == 'T'
      true
    else if sentence.length == 3 and sentence[1] == 'F'
      false
    else if typeof vars == 'undefined' or
    vars.includes (sentence.slice 1, -1).join ''
      (sentence.slice 1, -1).join ''
    else
      'UNDEFINED'
  else
    'ERROR'

levels = (sentence) ->
  sentence
    .map (char) ->
      if char == '('
        1
      else if char == ')'
        -1
      else
        0
    .reduce (prev, derivation) ->
      [
        ...prev,
        prev[prev.length - 1] + derivation
      ]
    , [0]
    .slice(1)

operatorIndex = (sentence) ->
  sentence.findIndex (char, i) ->
    (levels sentence)[i] == 1 and operators.includes char

for [proposition, syntax] in [
  [ [ 'A'                   ], 'ERROR'                            ]
  [ [ '(A'                  ], 'ERROR'                            ]
  [ [ 'A)'                  ], 'ERROR'                            ]
  [ [ '(A)', ['B']          ], 'UNDEFINED'                        ]
  [ [ '(A)', ['A']          ], 'A'                                ]
  [ [ '(A)'                 ], 'A'                                ]
  [ [ '(T)'                 ], true                               ]
  [ [ '(F)'                 ], false                              ]
  [ [ '((A))'               ], 'A'                                ]
  [ [ '(((A)))'             ], 'A'                                ]
  [ [ '~(A)'                ], 'ERROR'                            ]
  [ [ '(~A)'                ], 'ERROR'                            ]
  [ [ '(~(A))'              ], ['~', 'A']                         ]
  [ [ '((A)&(B))'           ], ['&', 'A', 'B']                    ]
  [ [ '((A)|(B))'           ], ['|', 'A', 'B']                    ]
  [ [ '((A)>(B))'           ], ['>', 'A', 'B']                    ]
  [ [ '((A)=(B))'           ], ['=', 'A', 'B']                    ]
  [ [ '((~(A))&(B))'        ], ['&', ['~', 'A'], 'B']             ]
  [ [ '((A)&(~(B)))'        ], ['&', 'A', ['~', 'B']]             ]
  [ [ '(((A)|(B))&(~(C)))'  ], ['&', ['|', 'A', 'B'], ['~', 'C']] ]
  [ [ '(((A)|(B)&(~(C)))'   ], 'ERROR'                            ]
  [ [ '((A)|(B))&(~(C)))'   ], 'ERROR'                            ]
  [ [ '(((A)|(B)))&(~(C)))' ], 'ERROR'                            ]
  [ [ '(((A)|(B))&(~(C))))' ], 'ERROR'                            ]
]
  assert.deepEqual (plParse ...proposition), syntax

Learning

Models

export class Hypothesis
  constructor: (@weights) ->

Linear Model

export class LinearModel extends Hypothesis
  apply: (x) ->
    if x.length == (@weights.length - 1)
      @weights[0] +
      @weights
        .slice 1
        .sum (w, i) ->
          w *
          x[i]

  complexity: (q = 1) ->
    @weights.sum (w) ->
      Math.abs(w) ** q

Polynomial

export class Polynomial extends Hypothesis
  apply: (x) ->
    @weights
      .sum (w, i) ->
        w * (x ** i)

For example, f(x) = 2x² + 5x + 3:

f = new Polynomial([3, 5, 2])
assert.deepEqual \
  ([0,  1,  2,  3,  4,  5].map (x) -> f.apply x), \
   [3, 10, 21, 36, 55, 78]

Evaluation

Empirical Loss

Confer section 18.4.2, p. 712f.

export lossFunctions =
  absolute: (correct, predicted) -> Math.abs (correct - predicted),
  squared:  (correct, predicted) -> (correct - predicted) ** 2,
  binary:   (correct, predicted) -> if correct == predicted then 1 else 0

export empiricalLoss = (hypothesis, lossFunction, examples) ->
  (
    examples.sum (pair) ->
      lossFunction pair[1], hypothesis.apply [pair[0]]
  ) /
  examples.length

Cost & Best Hypothesis

Confer section 18.4.3, p. 713.

export cost = (hypothesis, lossFunction, examples, conversionRate = 0) ->
  (empiricalLoss hypothesis, lossFunction, examples) +
  conversionRate *
  hypothesis.complexity

export bestHypothesis = \
  (hypothesisSpace, lossFunction, examples, conversionRate = 0) ->
  hypothesisSpace.argmin (x) -> cost x, lossFunction, examples, conversionRate

Regression

Univariate Linear Regression

Confer section 18.6.1, p. 719

export linearRegression = (trainingSet) ->
  divisor = \
    trainingSet.length *
    ( trainingSet.sum (pair) -> pair[0]  ** 2) -
    ((trainingSet.sum (pair) -> pair[0]) ** 2)
  w1 =
    if divisor == 0
      0
    else
      (
        trainingSet.length *
        (trainingSet.sum (pair) -> pair[0] * pair[1]) -
        (trainingSet.sum (pair) -> pair[0]) *
        (trainingSet.sum (pair) -> pair[1])
      ) / divisor
  w0 = \
    (
      (trainingSet.sum (pair) -> pair[1]) -
      w1 *
      (trainingSet.sum (pair) => pair[0])
    ) /
    trainingSet.length
  new LinearModel [w0, w1]

trueModel = new LinearModel [3, 0.5]
sampleSizes = [1, 5, 10, 100]
assert.deepEqual (
  sampleSizes.map (n) -> 
    examples = [0 .. (n - 1)].map (x) -> 
      [x, (trueModel.apply [x]) + rand.random() - 0.5]
    predictedModel = linearRegression examples
    [n, predictedModel.weights, empiricalLoss predictedModel, lossFunctions.squared, examples]
  ), [
    #   n    w0                    w1                    empirical loss       
    [   1 , [ 2.9863217363830663 , 0                  ], 0                    ]
    [   5 , [ 2.933798302215137  , 0.4203891319253779 ], 0.026432483146730707 ]
    [  10 , [ 3.1695157940114393 , 0.4639499877188505 ], 0.07533178680729899  ]
    [ 100 , [ 3.0419489353360176 , 0.4986560392449387 ], 0.08407918383200677  ]
  ]

Artificial Neural Networks

Activation Function

Confer section 18.7.1, p. 729.

export activationFunctions =
  step:    (x) -> (x > 0) * 1
  sigmoid: (x) -> 1 / (1 + Math.E ** (-x))

Neuron

Confer section 18.7.1, p. 728.

export class Neuron
  constructor: ({
    @inputs             = []
    @threshold          = 0
    @activationFunction = activationFunctions.sigmoid
    weights
  }) ->
    @weights = weights || (Array @inputs.length).fill 1

  output: ->
    @activationFunction \
      (
        @inputs
          .map (input, i) =>
            @weights[i] *
            @inputs[i].output()
          .sum()
      ) -
      @threshold

Neurons as logic gates. Confer section 18.7.2, p. 729f.

inputs = [{}, {}]
AND = new Neuron
  inputs: inputs
  weights: [1, 1]
  threshold: 1.5
  activationFunction: activationFunctions.step
OR = new Neuron
  inputs: inputs
  weights: [1, 1]
  threshold: 0.5
  activationFunction: activationFunctions.step
NOT = new Neuron
  inputs: [inputs[0]]
  weights: [-1]
  threshold: -0.5
  activationFunction: activationFunctions.step

inputs[0].output = -> 0
inputs[1].output = -> 0
assert.equal AND.output(), 0
assert.equal OR.output(),  0
assert.equal NOT.output(), 1

inputs[0].output = -> 0
inputs[1].output = -> 1
assert.equal AND.output(), 0
assert.equal OR.output(),  1
assert.equal NOT.output(), 1

inputs[0].output = -> 1
inputs[1].output = -> 0
assert.equal AND.output(), 0
assert.equal OR.output(),  1
assert.equal NOT.output(), 0

inputs[0].output = -> 1
inputs[1].output = -> 1
assert.equal AND.output(), 1
assert.equal OR.output(),  1
assert.equal NOT.output(), 0

Neurons representing the majority / minority function. Confer section 18.7.2, p. 731.

export majority = (inputs) -> new Neuron
  inputs: inputs
  weights: (Array inputs.length).fill 1
  threshold: inputs.length / 2
  activationFunction: activationFunctions.step

export minority = (inputs) -> new Neuron
  inputs: inputs
  weights: (Array inputs.length).fill -1
  threshold: -inputs.length / 2
  activationFunction: activationFunctions.step

inputs = [0, 0, 0, undefined, 1, 1, 1]
  .map (i) -> ({ output: -> i })

sevenMajority = majority inputs
sevenMinority = minority inputs

inputs[3].output = -> 0
assert.equal sevenMajority.output(), 0 
assert.equal sevenMinority.output(), 1

inputs[3].output = -> 1
assert.equal sevenMajority.output(), 1
assert.equal sevenMinority.output(), 0