CMPS140, Winter 2012, Section 01: Lecture 15

=======================================================================================
NIM:
    alternate taking sticks (as many as one wants but  from a single
    pile at a time) - the player who gets the last stick wins.

   3-5-7 NIM

011
101
111
---
001   ---> add in Nim-sum-wise into pile 1 or 2 or 3.

If pile 1, 11+ 001 = 010  so remove 1 from pile 1 leaving 2-5-7
If pile 2  101+ 001 = 100 so remove 1 from pile 2  leaving 3-4-7.
If pile 3  111+001 = 110  so remove 1 from pile 3 leaving 3-5-6.

Note in all three cases that Nim-sum goes to 0! (equals a
winning configuration).

From any 000 the player must move out, and from any non-zero
we can move in!


This rule works for all numbers and sizes of piles...

We overviewed  learning methods:
 Numerical:
    exponential moving averages     w*Old + (1-w)*New
                    advantages over simple moving averages:
                              only need to store one data point
                              smoother updating
                              favors recent data
                              tunable  (high w is less sensitive, low w is jumpy :)
    perceptron   18
    neural network 18

 Rule-Based:
    nearest neighbor 18
    version space  19
    decision tree 18

  Program-based:
    genetic algorithm 4  (broadly speaking: build populations of agents and keep and share
                         aspects of those which did best, rinse and repeat !)

entropy page 704