Gábor Melis' () blog - AI

As promised my UCT implementation is released, albeit somewhat belatedly. It's in Micmac v0.0.1, see test/test-uct.lisp for an example. Now I only owe you Alpha-beta.

For what has been a fun ride the official results are now available. In the end, 11th out of 700 is not too bad and it's the highest ranking non-C++ entry by some margin.

I entered the contest a bit late with a rather specific approach in mind: UCT, an algorithm from the Monte Carlo tree search family. It has been rather successful in Go (and in Hex too, taking the crown from Six). So with UCT in mind, to serve as a baseline I implemented a quick minimax with a simple territory based evaluation function ... that everyone else in the competition seems to have invented independently. Trouble was looming because it was doing too well: with looking ahead only one move (not even considering moves of the opponent) it played a very nice positional game. That was the first sign that constructing a good evaluation function may not be as hard for Tron as it is for Go.

But with everyone else doing minimax, the plan was to keep silent and Monte Carlo to victory. As with most plans, it didn't quite work out. First, to my dismay, some contestants were attempting to do the same and kept advertising it on #googleai, second it turned out that UCT is not suited to the game of Tron. A totally random default policy kept cornering itself in a big area faster than another player could hit the wall at the end of a long dead end. That was worrisome, but fixable. After days of experimentation I finally gave up on it deciding that Tron is simply too tactical - or not fuzzy enough, if you prefer - for MC to work really well.

Read more

Tron is a fun little game of boxing out the opponent and avoiding crashing into a wall first. The rules are simple so the barrier to entry into this contest is low. Thanks to aeruiqe who made to Common Lisp starter pack it took as little as a few hours to get a very bare bones algorithm going. It's doing surprisingly well: it is number 23 on the leaderboard at the moment with 43 wins, 2 losses and 9 draws.

Let me interrupt the flow of the MGL introduction series with a short report on what I learnt playing with Deep Boltzmann Machines. First, lots of thanks to Ruslan Salakhutdinov, then at University of Toronto now at MIT, for making the Matlab source code for the MNIST digit classification problem available.

The linked paper claims a record of 99.05% in classification accuracy on the permutation invariant task (no prior knowledge of geometry). A previous approach trained a DBN in an unsupervised manner and fine tuned it with backpropagation. Now there is one more step: turning the DBN into a DBM (Deep Boltzmann Machine) and tune it further before handing the baton over to backprop. While in a DBN the constituent RBMs are trained one by one, the DBM is trained as a whole which, in theory, allows it to reconcile bottom-up and top-down signals, i.e. what you see and what you think.

Read more

In the previous part we went through a trivial example of a backprop network. I said before that the main focus is on Boltzmann Machines so let's kill the suspense here and now by cutting straight to the heart of the matter.

Cottrell's Science article provides a clear and easy to follow description of the spiral problem that we are going to implement. The executive summary is that we want to train an auto-encoder: a network that reproduces its input as output with a small encoding layer somewhere in between. By forcing the information through the bottleneck of the encoding layer the network should pick up a low dimensional code that represents the input, thus performing dimensionality reduction.

The function under consideration is f(x) = [x, sin(x), cos(x)]. It is suprisingly difficult to learn the mapping from x to f(x). A network architecture that is able to represent this transformation has 3 inputs, 10 neurons in the next layer, 1 neuron in the encoding layer, 10 neurons again in the reconstruction part and 3 in the output layer. However, randomly initialized backpropagation fails at learning this; a better solution is to first learn a Deep Belief Network, "unroll" it to a backprop network and use backprop to fine tune the weights.

Read more

Having been motivated, today we are going to walk through a small example and touch on the main concepts related to learning within this library.

At the top of food chain is the generic function TRAIN:

 (defgeneric train (sampler trainer learner)
   (:documentation "Train LEARNER with TRAINER on the examples from
 SAMPLER. Before that TRAINER is initialized for LEARNER with
 INITIALIZE-TRAINER. Training continues until SAMPLER is finished."))

Read more

This is going to be the start of an introduction series on the MGL Common Lisp machine learning library. MGL focuses mainly on Boltzmann Machines (BMs). In fact, the few seemingly unrelated things it currently offers (gradient descent, conjugate gradient, backprop) are directly needed to implement the learning and fine tuning methods for different kinds of BMs. But before venturing too far into specifics, here is a quick glimpse at the bigger picture and the motivations.

Most of the current learning algorithms are based on shallow architectures: they are fundamentally incapable of basing higher level concepts on other, learned concepts. The most prominent example of succesful shallow learners is Support Vector Machines, for which there is a simple CL wrapper around libsvm, but that's a story for another day.

On the other hand, deep learners are theorethically capable of building abstraction on top of abstraction, the main hurdle in front of their acceptance being that they don't exist or - more precisely - we don't know how to train them.

Read more

Along the lines of active learning with python & libsvm, I added support for calculating distance of a point from the separating hyperplane to cl-libsvm. In binary classification there is only one SVM involved and one hyperplane. However, with N class problems there is a binary SVM for each of the N*(N-1)/2 pairs of classes and there are as many separating hyperplanes, something the linked python code fails to take into account. As per the libsvm FAQ, the absolute value of the decision value (see PREDICT-VALUES, wrapper of svm_predict_values) divided by the norm of the normal vector of the separating hyperplane is the distance. PREDICT-VALUES and MODEL-W2S are sufficient to calculate it. Note that among the distributed binaries only the linux-x86 version has been recompiled with the necessary changes, but patched sources are also included for your recompiling pleasure.

It seems that the competition has not been standing still (as opposed to Six) and this year marks the end of the golden era. Congratulations to both Wolve and MoHex who beat Six! Thanks to Ryan Hayward who, again, kindly registered Six for the Olympiad.

About the future, I don't really plan on resuming work on Hex in general (and Six in particular), although losing does irk me a bit.