algorithms

Create 2314

This is how you create the number 7.

MakeIntVar A
Inc A
Inc A
A=A*A
A=A+A
Dec A

Or

MakeIntVar A
MakeIntVar B
Inc A
Inc B
Shl A, A
Shl A, A
A=A-B

You can do all the basic operations + – * \ and you can shift right and left, and decrease or increase any variable, which you have to “MakeIntVar” first. By doing that, the variable is initialized to zero.

Now, make 2314 with the shortest possible algorithm.

Standard
algorithms

Compiler Error C2431

When you do this inline assembly in MS Visual C

LEA EAX, [EBX+2*EBP]

everything is just fine.

LEA ESP, [EBX+4*EBP]

also compiles well.

LEA ESP, [EBX+ESP]

okay again.

But when you try this

LEA EAX, [EBX+2*ESP]

you get error C2431.

Other compilers also fail to compile it! Like GAS, for example.

I have googled extensively but no valid explanation anywhere. Not a trace of it.

What is going on here?

 

Standard
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.

Standard
algorithms

More of Chess History

The number of possible chess positions is far smaller than the number of possible chess games. So a lot of games have positions in common. I wonder which games intersect in which positions. Aside from the trivial case, whereby every game has a common position with every other game – the opening position.

Then, I want a position that occurs in two games, once for the white player and once for the black player – the position remains the same, but the pieces swap colors. The second requirement is that the next move in both games be a move to the same field and with the same type of piece.

A search engine should be able to understand this, and output a position which conforms to the above requirements, along with the two associated games:

same_pos

 

[Event “Lodz”|Site “Lodz”|Date “1938.??.??”|Round “1”|White “Kolski, Jakub”|Black “Appel, Israel”|Result “1/2-1/2″|ECO “E16”]1. d4 Nf6 2. c4 e6 3. Nf3 b6 4. g3 Bb7 5. Bg2 Bb4+ 6. Bd2 Be7 7. Nc3 Ne4 8. Nxe4 Bxe4 9. O-O O-O 10. Bc3 d5

And a half a century later:

[Event “Budapest”|Site “Budapest”|Date “1994.??.??”|Round “1”|White “Schnelzer, Reinhard”|Black “Leroy, Adrien”|Result “1-0″|ECO “E18”]1. Nf3 e6 2. c4 Nf6 3. g3 b6 4. Bg2 Bb7 5. O-O Be7 6. d4 O-O 7. Nc3 Ne4 8. Bd2 Nxc3 9. Bxc3 Be4 10. d5

This kind of competition for the same field (d5 in this case) is not common, because  it breaks the white/black symmetry implicit to a position conformant to the described constraints.  Admittedly, the “same field” and “same piece” clauses were a bit contrived.

Speaking of contrived constraints: Give me two games, where a part of the first game, is the same as a part of the other in reverse!  Or give me all the games, where a check-mate in one (or in two or in three …) was missed by the looser. Or by either player. Was ever a game played (by grand-masters) where someone forced the other one to check-mate him? (Yes, there was.) Identify all the Zugzwangs! And so on – the possibilities are practically endless.

This is not so much about chess (or even search engines) as it is about the complexity, which is visible only with via computer algorithms digesting data (big or small). It is important to understand that not only do we not have all the answers, we do not even have all the questions. Computer algorithm, please tell me what to ask you!

 

 

Standard