Tic Tac Toe

SPELL NOTEのサンプルプログラムで、Tic Tac Toe分析プログラムを作りました。
CoffeeScriptで関数プログラミングするとどうなるか知りたかったのです。

###
Let's investigate Tic Tac Toe using computer!
Exhaustive searching shows the power of computer.
###

# constants to show the status of each place.
empty = 0
x = 1
o = -1


# utilities

pos2int = (xy) -> xy[0] + xy[1] * 3
# transforms 2d coordinate to index.
  
clone = (array) -> (e for e in array)
# make a clone of array.


class Phase # of game.
  constructor : (xs, os) ->
    # if given one argument, xs is a Phase instance, and returns its clone.
    # if give two arguments, xs is an array of positions of Xs, os is an array of positions of Os.
    if os?
      @data = (empty for i in [0...9])
      @data[pos2int pos] = x for pos in xs
      @data[pos2int pos] = o for pos in os
    else
      @data = clone xs.data
      
  next : ->
    # returns next player.
    unless @nextPlayer?
      @nextPlayer = if (i for i in @data when i isnt empty).length % 2 then o else x
    @nextPlayer

  eachChoice : (fn) ->
    # invokes fn with an argument of each of next phases.
    n = @next()
    phase = new Phase(this)
    for p, i in @data when p is empty
      phase.data[i] = n # put temporarily.
      fn phase
      phase.data[i] = empty # restores.

  hasWon : ->
    # tests if either won.
    played = -@next()
    lines =[[0,1,2]
            [3,4,5]
            [6,7,8]
            [0,3,6]
            [1,4,7]
            [2,5,8]
            [0,4,8]
            [2,4,6]]
    for line in lines when (x for x in line when @data[x] is played).length == 3
      return true 
    false

  isFull : -> (@data.indexOf empty) < 0
    # tests if no empties.


# main 

results = []
collectEnd = (phase) ->
    if phase.hasWon()
      results.push -phase.next()
    else if phase.isFull()
      results.push 0
    else
      phase.eachChoice collectEnd

new Phase([],[]).eachChoice(collectEnd)

console.log results.length
console.log (r for r in results when r is x).length
console.log (r for r in results when r is 0).length

最初、Haskellで書いたように次候補の配列作って、とやったら使用メモリ量が爆発していきました。なので、次候補を列挙せずに個々に再帰するようにしました。思ったよりかなり速かったです。