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!

 

 

Advertisements
Standard
algorithms

Beyond Google

What should we expect of search engines and companies behind them today?

To be able to find the richest (with the most material on board) chess position ever seen in a real high ranking tournament, for example!

Heavy

[Event “Australia”|Site “Australia”|Date “1965.??.??”|Round “1”|White “Sumpter”|Black “King”|Result “1-0″|ECO “B47”]1. e4 c5 2. Nf3 Nc6 3. d4 cxd4 4. Nxd4 e6 5. Nc3 Qc7 6. Be2 a6 7. O-O b5 8. Kh1 Nf6 9. f4 b4 10. e5 bxc3 11. exf6 cxb2 12. fxg7 bxa1=Q 13. gxh8=Q Qxa2 14. Qxh7 a5 15. h4 a4 16. h5 a3 17. h6 Qb1 18. Qg8 a2 19. h7 a1=Q 20. h8=Q …

88 points in pieces. 10 more than in the opening position. It ends like this:

Qb4 21. Be3 Nxd4 22. Bxd4 Qaa3 23. Bh5 d5 24. f5 Ba6 25. fxe6 O-O-O 26. Rxf7 Qca5 27. c3 Qd6 28. Bg4 Re8 1-0

 

And how about a position with the most queens ever?

6queens

Event “FSIMB October”|Site “Budapest HUN”|Date “2009.10.04”|Round “2”|White “Szalanczy, E.”|Black “Nguyen, T.”|Result “1/2-1/2″|WhiteElo “2354”|BlackElo “2437”|ECO “B90”] …

6 queens only, just as many as in the first (the heaviest of them all) situation. There are more than 35 of such among more than two hundred fifty million positions derivable from 2 million games recorded in the last 200 years or so.

Which game ever played has returned to the opening position as late as possible?

It was: [Event “Australian Open”|Site “Cammeray AUS”|Date “2011.01.13”|Round “11.24”|White “McGuirk, Michael”|Black “Perera, Pasan”|Result “1/2-1/2″|BlackElo “1866”|ECO “A05”]1. Nf3 Nf6 2. Nc3 Nc6 3. Nh4 Nb8 4. Nf3 Na6 5. Nb1 Nc5 6. Nd4 Na6 7. Nb5 Nb8 8. N5a3 Nh5 9. Nc3 Nf4 10. Na4 Ne6 11. Nb6 Nc6 12. Nd5 Nc5 13. Nc4 Nd4 14. Na3 Nf5 15. Nb5 Na6 16. Nd4 Nd6 17. Ne3 Nb8 18. Nef5 Ne4 19. Nf3 Nc6 20. N5h4 Nc5 21. Ng1 Na6 22. Ng6 Nab8 23. Ne5 Nd4 24. Nc4 Nf5 25. Na3 Nh6 26. Nb1 Ng8 …

They played 52 plys or half moves only with horses. Returning them back home and begin to play for real only then.

Which was the “bloodiest” game ever played by grand masters? The most aggressive from both sides?

The answer is:

[Event “Steinhart Mem”|Site “Herzeliya ISR”|Date “2006.12.08”|Round “2”|White “Haimovich, T.”|Black “Zifroni, D.”|Result “1/2-1/2″|WhiteElo “2436”|BlackElo “2523”|ECO “A10”]1. c4 d5 2. cxd5 Qxd5 3. Qc2 Qxg2 4. Qxc7 Qxg1 5. Qxb7 Qxh2 6. Qxb8 Qe5 7. Qxc8+ Rxc8 8. Rxh7 Qxb2 9. Rxh8 Qxa2 10. Rxg8 Qxd2+ 11. Kxd2 Rxc1 12. Rxg7 Rxb1 13. Rxf7 Rxf1 14. Rxf8+ Kxf8 15. Rxa7 Rxf2 16. Rxe7 Rxe2+ 17. Kxe2 Kxe7 1/2

All pieces except kings have fallen in 34 plys or half moves. As if it was a staged game.

Well … Google should know where the so called million chess base is, on the Internet. Google should also know where to get and how to run those PGN algorithms, scattered all around – on the Internet. And how to further advance chess knowledge from there. Automatically, 100%. And to suggest not only answers but questions as well.

Have you ever wondered which position is the earliest, from which grand-masters have always won?

Have you ever wondered what is the largest cycle from position X, back to the position X?

You may wonder that now!

Of course, it’s not only chess, it is everything.

Standard
Uncategorized

More of NYR

Scott Aaronson : How Widely Should We Draw The Circle?

It’s about quantum computing. It looks like at least one acceleration is possible here. In his words:

there exist Boolean functions with super-quadratic quantum speedups

How can I believe him, when he laments about Antarctica’s snow melting for the best part of his article? Especially now, when we have record ice down there? I am giving him 6/10.

Max Tegmark: Wisdom Race Is Heating Up

He is more afraid of another kind of warming – the technology warming. More real and far more dangerous process. Will we be smart and wise enough to handle intelligent machines when they will be ever more smart and ever more common? Still he finds a place in his article to say:

Many of humanity’s most stubborn problems, from destructive infighting to deforestation, overfishing and global warming

Well … this overfishing question is kind of intrigued me before. If I catch a big fish, a lot of smaller fish will therefore not be eaten by it. A big fish ate a ton of smaller fish to gain this much weight, right? Now, a ton of smaller fish will be spared in the year ahead. I have just killed 100 kg fish meat and therefore rescued much more than that of a fish meat in a smaller packages. Still, some even bigger fish will have less to eat. But their total mass is not that great anyway.

In fact, there is a pretty constant amount of fish meat in the ocean. It depends of how much plants are in the bottom of the marine food chain. It’s difficult to exterminate all the marine animals, but will be possible one day. When and if those smart machines Tegmark (and almost everybody else now) is talking about, are going to go the Terminator’s way.

I am giving him 8/10.

 

 

Standard
Uncategorized

NYR, continued

Joscha Bach: Everything Is Computation

After some lamenting about how hot it’s going to be on our planet due to anthropomorphic climate change (many Edge contributors have this urge, as they want to establish themselves among Algore’s flock as devoted – or what?) … he goes to the point.

A growing number of physicists understand that the universe is not mathematical, but computational, and physics is in the business of finding an algorithm that can reproduce our observations.

And that

Everything is computation.

I agree with those two points and I am giving him 8/10. The score would be much higher, if the CC thing hadn’t even been mentioned.

The point is that we are DEFINING computation, information, intelligence and so on, quite arrogantly. Just as Newton (or Galileo) defined force as something totally separate from the way Shakespeare or Dante would use it. It’s the right thing to do. Loose everyday words such as “mass” or “temperature” are just floating among people, until they are defined as a scientific term. Explicitly or rather implicitly.  Shedding some light on the matter instead of creating confusion.

Rory Sutherland: The Dematerialization Of Consumption

He concludes, that our consumption consists of less and less so called material goods. Even if you spend ever more money per year, the mass of the purchased pile per year goes down. It peaked at 12 tons per year already.

I think he is wrong on the long term. It will peak someday, but with a much larger amount. Still an interesting line of reasoning, I’ll give him 8/10.

Peter Turchin: Fatty Foods Are Good For Your Health

Once again, an entire scientific community was completely wrong for decades. They have had a scientific consensus among themselves where almost everybody was reluctant to challenge it, for fear of being derided as a crank, and most further intimidated everybody else. Don’t eat that fatty meat, or you will die! Eat wheat! (I other words – Eat starch and become obese! We will blame fast food restaurants and their hamburgers for this, you sinner!)

I give him 9/10. Hoping that the Global Warming crowd also took something from this. No, they haven’t – not yet.

 

 

Standard
Uncategorized

New Year’s Reading

For years now, my favorite is the edge.org’s annual question. This year was:

2016 : WHAT DO YOU CONSIDER THE MOST INTERESTING RECENT [SCIENTIFIC] NEWS? WHAT MAKES IT IMPORTANT?

You can go there and read it by yourself. Just bellow two hundred answers in more than 130 thousand words all together.

At least one answer is a pure shame. Mostly they are much better, some even extraordinary. I’ll engage here with some of those, so you don’t have to read them all.

Or take this as a recommendation to read it by yourself.

Andrei Linde: Energy Of Nothing

He argues that the density of vacuum energy is approximately the same as the energy of the ordinary matter, scattered all over the Universe. It’s a special moment in history, when those two are equal. In the future dark energy will prevail and will be our demise. According to him and most of astrophysicists. Enjoy this calibration while you can!

I give him 8/10.

Freeman Dyson: Doing More With Less

A small budget astronomy program named Dragonfly brought as a discovery. 50 dwarf galaxies orbiting our Milky Way have been discovered. They are made of  1 percent of visible and 99 percent of dark matter. While it’s 10 agaist 90 percent in the case of our central Galaxy. He pledged for more small budget programs like this.

I give him 9/10.

Jim Holt: The Ironies of Higher Arithmetic

There is the abc conjecture. Unproven, except by one Japanese man Shinichi Mochizuki with a proof so difficult, that nobody understands it. A whole team of experts tried, but nobody was able to digest it. They will try again, this year.

I give him 8/10.

John Naughton: A New Algorithm Makes Us Rethink What Computers Can—and Cannot—Do

After decades a Hungarian born László Babai has managed to significantly improve his own algorithm which solves the graph-isomorphism problem. Are those two graphs in fact the same? The old algorithm was already quite useful, but it was factorial, the new one is only slightly worse then polynomial. Can be an important achievement.

I give 8/10 to Naughton  and 10/10 to Babai, of course.

Pamela McCorduck: Identifying The Principles, Perhaps The Laws, Of Intelligence

She argues, that all kinds of intelligence, be it biological, human, animal, plant or computer are essentially the same thing. Just like rock throwing and satellite orbiting and many more are just examples in Newtonian mechanics. The time is coming, she says, when we will understand this what she calls the computational rationality, just as we understand mechanics. It’s time to cut the various crap here.

I agree with her and I give her 10/10. Even if it sounds like an old news for some of us.

To be continued …

 

 

 

 

 

 

 

Standard