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 http://www.chess.com.

Advertisements
Standard

4 thoughts on “Beyond AlphaGo

  1. alpha007org says:

    Shall we try? My Nexus 5 with Stockfish vs your solution? Let’s test. When, date, time in UTC and where. Time constraints? I think 2 min per move is enough.

    • No, not yet. You will still win too easily. I believe my first few moves would be optimal, but soon I’ll be in the dark, for there will be no advice from my system for me what to do . At least in some positions. Which can already be deadly for a human against Stockfish.

      I could use Stockfish moves in the dark and then it would be a game between Stockfish and Stockfish+.

      I had an idea, to milk Stockfish for rules already. As I milked chess history database. But you see, people (and computer programs) don’t play the logically proven move. They don’t try to prove that a particular move is the best before playing it.

      I roughly estimate, that Stockfish average move is 1.05 the best. An optimal player would have 1.0 and a top human player has 1.1. When an amateur like me is lucky to have 2.0 or there about. For there is often the twentieth best move which I actually play. It looks good in my eyes, but it’s a death sentence in fact.

      I am not putting any manual effort in this. This chess engine might evolve to a full maturity one day, but it will be (as) a side effect. A chess toy model, since a tic-tac-toe toy model doesn’t sound too good.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s