algorithms, artificial intelligence, Uncategorized

Beyond AlphaGo

I have a tremendous respect for what they did. A machine learned a game and won against the human world champion in one of the most complicated games. Perhaps the most complicated game of them all, although I doubt that.

It is not nearly enough, however.

I want an algorithm, the simplest one of them all, which would tell me what the next optimal move is. It always exists, in every possible situation. Perhaps many possible moves exist, each optimal. But at least one is always guaranteed. We know this since John von Neumann.

It doesn’t matter what your opponent might do after that, what strategy he might follow. Your move depends ONLY on the position you see, and nothing else. No game’s history matters either. Be it Go, chess or whichever finite game, there is always an optimal move you have to play to maximize your expectations.

Therefore, an algorithm must calculate which one to play next. Nothing less. An explanation why this particular one – is just an interesting option. Your opponent may also see those reasons, but that will not help him much!

This is very weird and contraintuitive, it goes against all our gut feelings.

That’s why I wrote it here, anyway.

This kind of algorithm which calculates the best move(s) solely from any given position is the holly grail. A human may or may not understand the procedure. A human may or  may not be able to follow its steps with pencil and paper. A machine as big as the Solar system may or may not be able to execute it for the game of Go or even chess. We don’t know that.

I tend to think that a modern smartphone should suffice for an optimal game of Go, but it’s just a guess of mine.

What is certain, at least every finite turn based game can be “hacked” this way. A simple to do list for every different set of possible positions, always exists.

The upper bound for the winning algorithm size in Go is 3^361 IF clauses. It’s only about 500 steps when those IF clauses are sorted by the position number.

An example line of this algorithm would be:

IF (PositionNumber == 100000000400000000000007) MoveTo C9

The algorithm size in bytes is prohibitively large for the observable Universe to store it. So it’s useless, even if there are less than 1000 steps to execute  it.

We can improve it, so that a typical line would be

IF (F_function(PositionNumber) == 100006007) MoveTo C9

F_function is itself say a million lines long, which is not too bad, and then you can store all the IFs inside … well much smaller space.

How far this optimization goes, nobody knows. My wild guess is – less than one million instructions of a smaller than one Giga byte large Phyton program.

Maybe much less. Several kilobytes of code, and never more than a thousand steps algorithm to always win (or at least not to lose) a Go game – that would really impressed me. A very opaque Neural Network machine is just a very good step in the right direction.

BTW ..

IF (Game==Chess) & (Position==OpeningPosition) Move your right knight to f3!

I can’t say I can prove this to you, but I came close. We currently have about 120 million such advices. Not enough on one hand, and not reduced enough on the other hand. But good enough to cheat successfully on