Story ideas

A underground city is discovered, excavators unearth various tablets and ancient artifacts. A facility is built over the site and soon a gate sealed with molten rock is discovered, writings speak of extreme danger and ultimate power beyond, apparently it is some kind of prison and a uncanny glyph of a skull with horns makes everyone weary. Mining equipment is brought and a spiral staircase downward slowly reveals itself. When they finally break through it is into a tunnel going the opposite way, as if someone had been trying to dig their way out… A broken horn is found on the ground. While exploring the new cave people go missing and the military is called in but the first incursion ends in screams, then the unit defending the gate hear footsteps in the spiral staircase. Suddenly a skeletal beast with large horns emerges, bullets don’t hurt it and those who can still walk are driven out of the city. The skeletal beast follows them into the facility but after much mayhem it is destroyed. Standing over the broken bones someone remarks that this thing has both its horns intact… A decision is made to reseal the gate but as the city is reentered they find that more monsters have emerged, ground level entrances are closed off but there are too many so as the facility is abandoned the things start pouring out into the world.

Commanders are reluctant to nuke the site due to the allure of ultimate power and also further texts speak of innocents locked up in the caverns and the moral obligation to release them. A long running war against the monsters of the depths ensues and eventually a chained bone dragon is found, the skeletal beasts have been gnawing on its body for eons. After the dragon is released it proves a powerful ally and guides rescue missions deeper to sealed caverns guarded by skeletal spiders, the caverns contain hives of zombie ants who devour everything in sight, including themselves. The ants are innocents who have been programmed to torture and have to be saved. Helping these tortured souls is the path to power since those who have suffered most will wield most power in eternity.

Two other stories deal with angels blindly following archaic rules. A god creates a vast realm and the angels within, writes down directions for them, then falls into a coma. After a long time hell starts invading, this lacks precedent and absurd situations arise from the angels obeying ancient orders. A heaven in the fray becomes unable to pay the rent and its residents are instructed to leave their fortress. Since no one wants to travel to this dangerous region the defensive position will simply be left empty. The angels agree that this is not strategically smart but anyone who doesn’t follow the old orders, that contain no considerations for the state of war, gets deleted. The second, related, story follows a civilization that is unable to pay the electricity bill for its star and is forced to leave the solar system.

Danglers and MCTS

Finally made a good function to connect danglers, stones that have to be connected to the main group because they don’t have any eyes on their own. The solution is simple in hindsight, first place stones on all dame points, those with influence from both green and blue, then check which stones have only one liberty. Place a stone of the same color on that liberty and check if the new group is still in atari, repeat until it isn’t or placing on the liberty is suicide. This function greatly enhances automatic marking of dead stones, false eyes are removed and cutoffs can be implemented based on the remaining surrounded territory, a group with more than four surrounded points is going to be hard to kill.

Just thought of a way to check if a group is unconditionally alive. Try placing a stone of the opposite color on all liberties, repeat until no stones are placed. Groups that enclose large territories can easily be captured this way but are pruned as alive based on how much empty space they are close to. Also seki would collapse, so for a more robust solution one needs a way to discern between fatal self atari and self atari required to capture a group from within.

Note that the code of http://triangulargo.club/ defines a group as stones that are solidly connected, whereas in normal speech a group represents what is defined in the code as a influence group, stones connected by proximity. A cluster is all stones connected by empty space and this is currently the type which the auto marker operates on, this causes problems when two groups are obviously separate but haven’t been fully enclosed, additionally since there is a cutoff based on how much space the cluster is connected to stones in a large territory do not get marked despite obviously being dead. Will fix this by making a new automatic marker that operates on influence groups with MCTS. Monte Carlo Tree Search is an algorithm originally designed specifically for Go, it is a basic back propagating learner: a branch is evaluated and then the result is propagated to all nodes, nodes with higher win rate subsequently get a higher probability of being picked.

Have implemented a MCTS for ladders and the AI no longer places moves that can be directly captured! Checking for nets requires much more consideration, not only are there many more moves that have to be evaluated but even if a group can be netted it will still have liberties that allow it to be sacrificed for forcing moves in other places. Blindly disallowing moves that can potentially be captured with several extra moves isn’t sensible. A better case is checking if walls can be broken through, start with a weak point like a shortage of liberties, if a group only has two unprotected liberties the other player essentially gets a free move on one of them, several such places can easily lead to complications. Add additional relevant spots and run some simulations to see if the wall crumbles.

When the MCTS encounters a move that threatens the life of a group that move can be stored in a list and if the move is placed it triggers the calculated response. A problem is that if two moves are required to threaten none of them are stored so when the opponent places one of them the other wont be on the radar so the group still needs to be reevaluated…

A problem is avoiding the most fundamentally bad move: filling your own eyes; while still allowing false eyes to be filled. If green is filling its own eyes bad moves by blue might still capture a group, the MCTS will eventually learn that those moves don’t work but meanwhile a lot of false positives are generated. A possible solution is calling connect danglers after every move that could generate a dangler, the complications being determining such moves and juggling stones actually placed and those placed by the dangler connector. Another way of identifying a real eye is by checking if the stones surrounding it belong to the same solidly connected group, this approach was not so good with the old automatic marker because there are eyes formed from stones that are only diagonally connected so groups with only such eyes would get marked dead. The MCTS approach however would quickly learn that passing is better than playing in these rare special circumstances.

It is important to take performance into consideration, there are only so many algorithms we can fit before the AI starts running slow on old computers and large boards.

Types

All the types associated with a database become like a Russian doll. Complex type systems are typical for languages like C++ where Kreti & Pleti implement their own types. Normally you may have to choose between a raw array (faster but more complicated to use), std::array, std::vector, std::list, std::queue or why not one of all alternatives in boost? Qt however uses QVector which apparently is a little bit slower, in Shark there is RealVector… If you try a OpenGL function and expect a number you might get a GLfloat which has to be “opened” to get a ordinary number. Vice versa you have to convert your data to the correct types for the package you are using: “Oh, this function doesn’t want a number, it wants a KretiNumber..”, then you have to look up how to create KretiNumbers. With composite types this can quickly get complex, what do you do with a KretiComponent<KretiVector<pleti::thing>,pleti::stuff>? Then every function that uses that type has to write out the type declaration and if you decide to start using KretiArray you have to change it everywhere…

JavaScript simplifies this by radically removing all type declarations, the functions try operating on whatever they get and if something goes wrong the result becomes slightly undefined, this is propagated further through the system making it hard to determine where the error arose. Go offers a sort of compromise, like Julias ::Any.

So to our Russian doll, the first doll is the database, to open it we create a client. Through the client we get a collection, for example with chat messages. So by opening the collection we get the messages? Not yet, we get a cursor that points to the messages. Ok, so by getting what is pointed to we get a message? Almost, we get a “empty interface”. A what? Empty interfaces in Go are like saying “this is anythingatall!” So depending on what is inside we need different methods to get it out, a string can be extracted with fmt.Sprintf.

What if the thing we are getting is supposed to be a list? Could it perhaps be stored as an array? Nope… After digging through the MongoDB manual I realized that aha, it is a primitive.A! How do we open primitive.A’s then? The code yielded an empty primitive.A… After a while I realized the field in the type that the result is saved to needs to be capitalized, so even though board operations are stored under “ops” in the database they have to be retrieved with a field named “Ops”! Confusing, yea. It is because capitalization controls exportation: if something should be accessible from different contexts. First time I’ve encountered functionality governed by capitalization of variable names.

Connecting danglers

Today I figured out how to get the AI to save stones dangling on the edge, an issue related to identifying false eyes. Building an efficient algorithm to determine if extra stones have to be placed to connect a group is tricky, it requires getting all connected stones and determining where the real eyes are, we don’t want to be filling those… So instead of an algorithm to determine if a spot is adjacent to a dangler on one side and a living group on the other I simply let the AI continue playing, finishing the game on a copy of the board. Such an operation is potentially time consuming so only when the AI finds no moves does it play the game to an end to determine if any of its stones get captured, those stones are then marked as dead on (another copy of) the original board and the AI reevaluates to fix any holes in the walls.

The AI is still oblivious to life & death invasions, but I already have a method for determining if a group can be captured via Monte Carlo simulations, so that only needs to be expanded to the more intelligent Monte Carlo Tree Search (originally developed just for the game of Go) and combined with the AI.

Now I am working on setting up a database for the Go server.

Pointers

One of the worst pitfalls in programming is a memory leak, something modern languages go to great lengths avoiding with reference counting garbage collectors. So what are these references? Or, as they are also known, pointers.

One can think of a pointer as a fishing line, you can’t just throw a bait into the ocean without something attached to it. It is also important to not lose the line, for even though setting up a new one may be cheap eventually some diver will get a hook through their ear…

A garbage collector would then be a device following your boat checking baits to see if they are connected to the boat and removing them if they aren’t. This prevents accidents, so why doesn’t all languages have them? It is easy to see that the resources required for cleaning up the ocean are greater than simply remembering to always pull in your lines. Having full control over exactly when new objects are allocated in memory is also useful, as the creator of Linux said, “any compiler or language that likes to hide things like memory allocations behind your back just isn’t a good choice for a kernel.”

It is important to know if an object is new or referenced somewhere else. Say you write a function that takes an argument, can you modify this argument or do you have to make a copy? Be sure to study the specifics for your language and take pointer design into consideration for your project architecture from the start. When making the Trigo app initially the triangles in the moves list where in fact references to the same triangles in the triangle grid, but when a board was copied they weren’t! This caused hard to find bugs and eventually I realized the design was simply bad, if one places a move on a location someone else placed on earlier you don’t want the information in the list of moves to change… A convenience in C++ is that one can overload the fundamental operators like == so that built in functionality such as determining if an array contains a specific element can work the way you want rather than checking if objects are identical (share the same memory location). In JavaScript ‘var t1=new Trigo.Triangle(0,0);var t2=new Trigo.Triangle(0,0);t1==t2′ returns false!

As a beginner it is probably better to stick to a garbage collected language, but does that mean you are completely safe from leaks? JavaScript is garbage collected but if you forget the var keyword a global variable is created, add the line ‘use strict’; to check for this. C++ is sort of garbage collected when using smart pointers (but they can’t release memory that is cyclically referenced, one object holds a pointer to another object that holds a pointer to the first object… the reference count never goes to zero), be very careful with raw pointers and the new keyword. Also any language can write files to the disk, if you keep doing that without ever deleting anything you will eventually run out of storage. Another example is programs running other programs. Say you have a website with a game, when a user connects the web server starts up a game server for that user which computes all the logic for the game and when the user disconnects the web server turns of the connected game server. Now say someone writes a function for transferring the game state to another web server… Your web server hands the pointer attached to the game server to the function but sometimes the function encounters an error before it can hand the pointer to the other web server. Now there is no one left who can turn of the game server!

Memory leaks can have devastating consequences, especially in embedded software with limited memory. Say we have an elevator that allocates memory for information about the destination floor when a passenger presses the corresponding button but whenever someone presses the emergency stop this memory block is not freed. The elevator may run fine for years but one day after someone has pressed emergency stop the elevator wont start back up…

Trigo

Currently working on a project involving AI for triangular Go, it is very interesting.

Have made Go like games before on a hexagonal board, in Julia and Ruby on Rails. This time I started out making a simple GUI in Java and then migrated that to C++ to use the Shark machine learning library. After a while I realized three things: the neural networks need solid algorithms to back them up, debugging such algorithms without an interactive console is a pain and also I would like the whole thing on the web. Thus I translated the project once again to JavaScript. It can be found here: https://github.com/jhlq/Trigo

The AI can atleast finish a game, soon I will run a bunch of simulations to determine a good komi and make some functions for Monte Carlo Tree Simulations, this will result in plentiful data for the neural networks to learn on. One issue I ran into when trying to implement convolutional neural networks was that they aren’t used to triangular coordinate systems… writing a custom kernel would be an interesting endeavour.

Now I am thinking about how to improve the automatic marking of dead stones, it has trouble when there are KOs along the edge… One possible solution is to first make sure all the stones are properly connected while taking care not to fill up eyespace, finding an algorithm for this is tricky…

Determining if two stones can connect (when the other player plays too) is a perfect task for neural networks!

An agile mutator

The agile mutator is being developed at the artai repo: https://github.com/jhlq/artai.co

In the Hexago folder the file called mutator.jl contains code that learns from the mutations it performs where it is beneficial to mutate. Try the Hexago game here: https://hexago.herokuapp.com/ (soon at http://artai.co/hexago/ )

The other thing we said we would do in association with that treacherous company with which we previously collaborated has been completed and they will not be mentioned again.

Congo

“The wars in that country have claimed nearly the same number of lives as having a 9/11 every single day for 360 days, the genocide that struck Rwanda in 1994, the ethnic cleansing that overwhelmed Bosnia in the mid-1990s, the genocide that took place in Darfur, the number of people killed in the great tsunami that struck Asia in 2004, and the number of people who died in Hiroshima and Nagasaki — all combined and then doubled.”
http://edition.cnn.com/2012/11/27/opinion/congo-war-ignored-vava-tampa/

The mutator

This time we consider a mutator with memory, first obtain the code from:
https://github.com/jhlq/trademaker/blob/master/AI2.jl
Then load it into julia:
julia -L AI2

Create the mutator and its neural network:
mutator=init()

The mutator keeps track of the network, now we need some training samples.
example,target=rsample()

Examples consist of bars describing how dispersed the previous hundred trades were and a target value to assign to these bars depending on how fast two bids on the spread are bought.

The net is untrained so the result is random:
score(mutator.net,example,target)

Let’s poke it.
poke!(mutator,example,target)

The mutator pokes the net in various ways to make it conform to the target and also remembers the effect of poking a specific node, maximum score per example is 1.
score(mutator.net,example,target)

Ever had your brain poked continuously a thousand times?
for poke in 1:1000;println(poke!(mutator,example,target));end
score(mutator.net,example,target) #0.9999999

Let’s see what result we get on several samples
examples,targets=rsamples(10)

The score function is overloaded to handle sample arrays.
score(mutator.net,examples,targets)
poke!(mutator,examples,targets)
score(mutator.net,examples,targets)
sum(score(mutator.net,examples,targets))

The poke! function also, the exclamation point is a julia convention for functions that modify their arguments.
poke!(mutator,examples,targets)
sum(score(mutator.net,examples,targets))

The overloaded poker pokes once for each sample, because of this the end result is sometimes worse. So we use the pocket algorithm, it works like this: we take the best result so far, and put it in our pocket.

The pocket algorithm is part of the evolve function, let’s do ten iterations:
mutator=evolve(mutator,examples,targets,10);

Each time a better net is pocketed the new score is printed. Let’s evolve a lot.
mutator=evolve(mutator,examples,targets,10000);

After a while the rate of improvement decreases, this means we need to decrease the mutation factor which defaults to 0.1, a value that determines the strength of the poke!
mutator=evolve(mutator,examples,targets,1000,0.03);
mutator=evolve(mutator,examples,targets,1000,0.01);

Next up we will download the full trade history and make the mutator more agile.

Neural networks in Ripple

We need data. We need a model to process the data. We need the model to evolve.

The full code can be found at https://github.com/jhlq/trademaker/blob/master/AI.jl

All trades in the Ripple network are stored, the first thousand BTC trades are here: https://ripple.com/chart/BTC/XRP/trades.json?since=1

To get a random set of a thousand trades in Julia we first define
start=1000*abs(rand(Int)%100)
Then do:
trades=JSON.parse(readall(`curl https://ripple.com/chart/BTC/XRP/trades.json?since=$start`))
Or, using the Requests package:
trades=JSON.parse(get("https://ripple.com/chart/BTC/XRP/trades.json?since=$start").data)

This will yield non overlapping sets which facilitates database storage (there is a SQLite package) however for training purposes overlapping sets are often better since this translates to more training examples.

Next we divide the trades, one part the model looks at to predict the other part.
np=100
peek=zeros(np,2)
for t in 1:np
  peek[t,1]=float(trades[t]["price"])
  peek[t,2]=float(trades[t]["amount"])*(0.5+0.5*t/100)
end
The amount is scaled so that a most recent trade contributes twice as much as one a hundred trades ago.

Now we make a histogram, for algorithmic reasons the number of intervals should be odd.
ma=maximum(peek[:,1])
mi=minimum(peek[:,1])
niv=33
bars=zeros(niv)
intervall=(ma-mi)/niv
for t in 1:np
  for iv in 1:niv
    if peek[t,1]<mi+intervall*iv
      bars[iv]+=peek[t,2]
      break
    end
  end
end

Here is where the model decides which bids to place, lets put one each in two of the most popular intervalls:
maxi=sortperm(bars,rev=true)
bidiv1=maxi[1]*intervall+mi
bidiv2=maxi[2]*intervall+mi

If they both get bought we make a profit so lets grade the bids based on how long it takes for one BTC to be traded in both intervalls.
bid1val=0
bid2val=0
barval=0
for testi in 101:1000
  test=[float(trades[testi]["price"]),float(trades[testi]["amount"])]
  for iv in 1:niv
    if test[1]bidiv1-intervall
      bid1val+=test[2]
      break
    elseif test[1]bidiv2-intervall
      bid2val+=test[2]
      break
    end
  end
  if bid1val>1 && bid2val>1
    println(testi)
    barval=1-(testi-101)/900
    break
  end
end

The bars and barval are what matters, they are the training sample and its prediction target. Lets make some functions for working with neural networks, the ones in AI.jl are called: makenet, mutate and feed. The bars are not quite ready to be fed to a network, first we need to make them spatially invariant since a vector of [1,0,1,0,0] contains essentially the same information as [0,0,1,0,1] but they will be treated entirely different, lets see them both as a vector containing a gap of length one.
function transpatinvari(d)
  dn=d/maximum(abs(d))
  nd=length(dn)
  if nd%2==0
    push!(dn,0) #for symmetry
    nd+=1
  end
  t=zeros(nd)
  for da in 1:nd
    for dat in 0:nd-da
      t[1+dat]+=dn[da]*simil(dn[da],dn[da+dat])
      #simil is a custom similarity measure
    end
  end
  return t
end

After feeding the network these transformed bars its prediction is scored based on the similarity to barval. Many algorithms can be based on such a score, below is one which randomly mutates the top performers in each generation.
function evolve(net=makenet(33,50,3),gens=3,its=9)
  #its is the number of iterations per generation
  nn=9
  m1=6
  nets=mutate(net,nn)
  tnets=nets
  scores=Array(Array,gens)
  for gen in 1:gens
    scores[gen]=score(nets,its)
    tops=sortperm(scores[gen],rev=true)
    tnets[1:m1]=mutate(nets[tops[1]],m1)
    tnets[m1+1:end]=mutate(nets[tops[2]],nn-m1)
    nets=tnets
  end
  return nets,scores
end

nets=evolve()

Evolution can be boosted by having the mutator evolve. Each time a neuron is perturbed the result is logged and the mutator remembers the effect of mutating that neuron.