Can chess be analytically "solved" in the forseeable future?

[diep]

Originally Posted by axn

http://en.wikipedia.org/wiki/Shannon_number

Good link!

The estimate from Victor Allis is a bit outdated though since then.

As i have shown already if you count in a manner taking the (impossibilities of) pawns into account, it's difficult to get to 10^40.

[Batalov]

As an aside, Victor Allis is a nice guy. Even though 10 (now 15) years have passed since his gomoku thesis and he had moved on to be a CEO of a sizeable company, he found time to answer my naive questions about gomoku several years ago. It is rare, really.

[diep]

Originally Posted by Batalov

As an aside, Victor Allis is a nice guy. Even though 10 (now 15) years have passed since his gomoku thesis and he had moved on to be a CEO of a sizeable company, he found time to answer my naive questions about gomoku several years ago. It is rare, really.

I saw him give a speech some years ago - it was really good.

His company on other hand is not such a friendly company. Big bunch of low IQ dudes, pretending to be clever, keeping people busy with nonsense - Dutch government very good in paying money to companies for that.

At a total labor force of 7.5 million (which also includes a big bunch of persons who are aged 60-65 and simply not working anymore as they are kind of retired without officially telling that to anyone), about 5.5 million work for (semi-)government in Netherlands.

I just finished an e-mail with another hero from the Game Tree Search community. He works in a company busy with fundmanaging.

They've got bunches of "civil servants" here who 'manage funds' (just a single pension fund here already is managing 1200 billion euro in cash as we speak) and of course they hardly make any profit doing that - yet manage to pay themselves - meanwhile telling fairy tales on how you can still make a profit with long term investment into their fund.

Whereas of course only some of the high frequency traders still make good profit, most of them located in USA.

They are so much behind here - and too arrogant to hire someone who can help them get into the 21th century.

Amazingly few persons from Game Tree Search end up in the HFT business, they're for some weird reason reluctant in hiring people to do what they're good at - whereas it's very similar to what Game Tree Search is doing.

As a result most sit at home and toy some with prime numbers - like me.

[Cazzeo]

Originally Posted by Brian-E

My guessed answer to your question is: yes, I think progressive chess probably can be solved to a clear win for either White or Black (I think it's extremely unlikely that this game is a theoretical draw with best play) if someone chooses to spend the effort and considerable computing time on the question.

Thought I'd jump into this discussion, as arguably the world's foremost expert on this game (I did an exhaustive series of lectures on progressive chess at chessvideos.tv). The game is most likely a theoretical draw after 1.d4 2.d5 c6 (only two-series that draws; everything else loses). 1.e4!? is unclear after 2.e5 f6 or 2.d5 dxe4, but it is unlikely white is winning in either case (2.d5 dxe4 is probably a draw, and 2.e5 f6 a draw or a black win).

As far as solving the game, memory is one of the biggest constraints. When you can make 5, 6, 7, 8, etc. moves in a row, the primary way to reduce the ply count is by recognizing transpositions (i.e. that Nf3-d4-c6-xe7 is the same as Nh3-f4-g6xe7), of which there are many. So you need giant transposition tables. Even accounting for those transpositions, you still have to generate all those moves. If it's white's 7, you still have to generate all sets of 7 consecutive moves, but you will vastly reduce the "leaf" nodes through transpositions, leading to less positions to have to search for black's 8. (Heuristics like "standing mate threat" would also reduce the search space considerably).

A game between myself and another expert on the game, representing progressive chess's "main line", if you're curious how draws happen at high level play: 1.d4, 2.d5 c6, 3.Bf4 Bc7 Bxd8, 4.Kxd8 Bf5 Bxc2 Bxd1, 5.Kxd1 e4 Ba6 Bxb7 Bxa8, 6.Kc7 f5 f4 f3 fxg2 gxh1Q, 7.Kd2 Nc3 Nf3 Rxh1 Ng5 Nf7 Nxh8, 8.g5 g4 g3 g2 gxh1Q Qf3 Bg7 Bxh8, 9.Ne2 Ng1 Nxf3 Ne5 Nxc6 Nxb8 Bxd5 Bxg8 a4, 10.Kxb8 Bxd4 Bxb2 Bd4 Bxf2 Bg3 Bxh2 e5 h6 Bf4+, 11.Kd3 Kc4 Kd5 Ke6 Kd7 a5 a6 Bf7 Be8 Bg6 Bh5, 12.Draw agreed

[Brian-E]

Originally Posted by Cazzeo

A game between myself and another expert on the game, representing progressive chess's "main line", if you're curious how draws happen at high level play: 1.d4, 2.d5 c6, 3.Bf4 Bc7 Bxd8, 4.Kxd8 Bf5 Bxc2 Bxd1, 5.Kxd1 e4 Ba6 Bxb7 Bxa8, 6.Kc7 f5 f4 f3 fxg2 gxh1Q, 7.Kd2 Nc3 Nf3 Rxh1 Ng5 Nf7 Nxh8, 8.g5 g4 g3 g2 gxh1Q Qf3 Bg7 Bxh8, 9.Ne2 Ng1 Nxf3 Ne5 Nxc6 Nxb8 Bxd5 Bxg8 a4, 10.Kxb8 Bxd4 Bxb2 Bd4 Bxf2 Bg3 Bxh2 e5 h6 Bf4+, 11.Kd3 Kc4 Kd5 Ke6 Kd7 a5 a6 Bf7 Be8 Bg6 Bh5, 12.Draw agreed

Leading to the dead position below. Yes, I see now how draws are possible in practice, and hence how the game can be a theoretical draw. Clearly it needs expert play, though, to take the right material off the board to lead to a drawn result. A single minor mistake, and the opponent will win instantly. Thanks for your interesting comments.

[LaurV]

I still can't believe one of the parties can't win if he has to do so many moves... See my post before. Again, my experience in this game consists in reading the rules, I never played a real game. But my "feeling" says that one can win provided he is allowed to do enough moves :D

Are you sure the sequences in that game are "optimal"? :D

Of course, this kind of game needs a lot of study, it is very complicate, even for experts in normal chess, to foresee what the adversary can do if he is allowed to do 5, 6, moves in a row... Ten moves? no way! You need to study a lot. I still believe this game is far from "perfect play". But this is just feeling, nothing concrete to back it up with.

[Cazzeo]

It isn't just about how many moves you have, though. Whether or not you're winning or losing depends on your material at the start of your turn, your opponent's material at the start of your turn, and the number of moves. A simplified way to think of it is to graph # of moves on the x-axis, and total points of your material on the y-axis. Some line through that plane represents equilibrium. Above it, you're winning. Below it, you're losing. Near the line it's balanced.

In other words, 3-4 moves with a queen isn't necessarily going to win, but 5-6 moves is likely to, and 7-8 is almost certain to. With a rook, 5-6 moves isn't necessarily going to win, but 7-8 moves with a rook might, and 9-10 most likely will. So the game is all about taking each others' queens off on the 3-4, and taking one bishop (since two bishops are monsters) + both rooks off on the 5-8. The skill comes in making sure on the 9-10 that your opponent has nothing but minor pieces and all pawn promotions are blocked by pieces or check (since delivering check ends your turn, a king on d2 can stop c-,d-,and e-pawns from getting by him, etc.)

I am fairly certain the main position is a draw, but of course I can't claim absolute certainty. I discover new things about the game all the time (having analyzed it for hundreds of hours). Some Fischer Random positions are almost certainly a win for one side or another. I won the progressive fischer random championship held at chessvariants.com back in 1997/1998, and one of the positions we were given was almost certainly a win for white.

The key factor really is how easy it is to develop your pieces and get your king safe. The starting position of regular chess is very balanced in that respect, so it's likely a draw. Some Fischer Random positions have terribly weak kings, bishops or queens in corners where it's hard to get them out rapidly, etc., and these positions are more likely to be won or lost for one side or the other.

[Batalov]

Remember last year's Rajlich's ruse?

Originally Posted by chessbase.com

Rajlich: Busting the King's Gambit, this time for sure

02.04.2012– Fifty years ago Bobby Fischer published a famous article, "A Bust to the King's Gambit", in which he claimed to have refuted this formerly popular opening. Now chess programmer IM Vasik Rajlich has actually done it, with technical means. 3000 processor cores, running for over four months, exhaustively analysed all lines that follow after 1.e4 e5 2.f4 exf4 and came to some extraordinary conclusions.

It was even slashodoted in haste.

Ha-ha for me. Yes, indeed, this how this whole thread started.

[LaurV]

Originally Posted by Cazzeo

It isn't just about .. <snip>

Now, sir, that is the best thing I ever read about progressive chess, and it totally makes sense... I believe that's the difference when the guy who explains it to you is someone who knows, or someone who doesn't. What you say here made me to look at this game from a totally different angle. It may be even become so interesting that I would start to play it... (not that I would be some precious acquisition for the progressive chess world, I still believe it needs a lot of work and study, and I am generally a lazy person).

[Batalov]

A group of chess enthusiasts checked into a hotel and were standing in the lobby discussing their recent tournament victories. After about an hour, the manager came out of his office and asked them to disperse. "But why?" they asked, as they moved away. "Because," he said, "I can't stand chess nuts boasting in an open foyer."

.

[Xyzzy]

http://arstechnica.com/gadgets/2016/...-in-the-world/

Deepmind, Google's artificial intelligence division, claims to have made a big breakthrough using neural networks, and it recently took on and defeated a Go world champion.