What is the purpose of chess engines?

[chrisw]

Ah! I thought this was a philosophical discussion about approaching some perfect database (map) for everybody to use.

But it turns out to be about a database of your games plus a chess engine to operate on the leaf nodes in the database, at the time of meeting them, and dependent on what your opponent did to get you there.

But this discussion has been never about *me*. Switch me for anybody else, and the person you switch me for would have a database that works for everything they'll need in their life. Switch me for *you*, and now it's you who would have something you couldn't tell apart from EGTB32 if you had access to them (because you'd only need covered the positions you'd check, not all of chess.)

Let me remind you how these discussions started, I was talking to Uri Blass about this, and he was claiming that this was impossible to do. The discussions turned about how it'd be impossible even in principle, to being impossible because of time constrains to being impossible because we don't have where to store them to being impossible because of time travel requirements.

But if in the end you accept it is possible for a single person (which in the examples was me) then you have to accept that it'd be possible for at least 2 persons (someone else just does what I'm doing.) And then 3.

What is the maximum number of persons that would be able to have a such database for the positions they'll see on their life?

I claim that anybody in the world that wanted to know the best move ranked in a position could have it. Not everyone in the world is going to request a position checked. Not all positions, just those requested. noobpwnftw could actually give us data about how many people have visited his site and how many positions have been queried (those where you have to click a request because the position you want information about is outside of the DB) to get an idea of the positions that would need to be checked for a chess map.

If you only fulfill the wishes of the people interested, and only about the positions that interest them, a chess map for everyone is within reach. And who knows if nobody will ever be interested in a 1.f3 f6 variation, so everyone wanting to solve chess with the tablebase approach is a fool, because we could already have solutions of some 9piece and 10piece endgames instead of trying to build a 8men monstrosity full of positions nobody will ever check.

Time travel problem again.
What you MIGHT need in some future time line is the SUM of all possible time lines from the present point. Which brings you back to the space problem again. Not enough space, nor time to generate the data to fill the space.
It is surely true your past history can be stored in a database, ChessBase for example, but your future histories not, you don’t know what they are and the possible permutations are explosively too great.

[Ovyron]

Time travel problem again.

What? No! We have gone over this already, you don't need to store what you will need on your life, because if you'll need to check a positions 50 years from now, what's the point in it being in there all these years? You get that part of the map figured out when you need it, time travel is only necessary if you want it to be on the map already (but for what reason?, if you won't use it for the next 49 years?) What I'm solving is the space problem because all the positions everyone needs right now are very few (relative to the whole of chess) and perfectly manageable.

My point is that if in 50 years you can rank a position to the top as if you could see the whole map then there's no difference between it being there all along or it appearing when you need it.

Anyway, since we're now running in circles I'm done discussing this topic with you. Congrats on having the last word in the issue, whatever you'll say.

As for the general public (which I'm still willing to discuss this with), I'll leave you with my last two statements about this, with titles and all:

The Pi Parable

Pi is the most famous non-integer number, people even have a day of the year where they celebrate it. Its construction is related to circles.

The interesting thing about it is that is has a decimal expansion that never ends. Another interesting thing is that it contains any arbitrary integer that you can think of, like 999999 for an arbitrarily long string of 9 (but not infinite! The 9s have to end to leave space for some other number), or whatever else you think of. Its decimal expansion in binary also contains every possible combination of 0s and 1s, so within Pi exists the same 0 and 1s that would produce a Binary file for a program that when you input some fen it outputs a top chess map move, along with all possible programs that could exist. With all audio files, and videos that could exist. But I digress.

Let's turn Pi into a game that resembles chess. So we have 2 players, white and black, and the game starts at Pi after the "3." part of Pi. The task of White is to play any 1 digit number that does NOT follow in Pi. Pi starts with 3.1, so on their first move White is fine if she sends a 0, or a number from 2 to 9. And then it's black turn. For the sake of simplicity we forget what white plays and just record Pi's next digit, so the position is 3.1 and it's black to move. Black needs to send a number that does not follow in Pi.

The next part is 3.14, so black's losing move is 4, anything else and it's white's turn, to avoid losing by playing something other than 1, because Pi continues 3.141.

This is a game that mostly everyone would eventually lose (there's a 10% chance that you will not lose on your first turn and probability is against you being able to keep up), but you can always do something to avoid losing by figuring out what is the next digit and not say it.

Well, let's spin this game and change the rules, so that instead of starting from "3.", before the game starts black names an arbitrary integer, and white has to say a number that is NOT that integer's position in Pi. Say, black says 999, now white has to say a number that is not in the 999th position on Pi's expansion. After it the game continues as normal, if white survives we move on to 1000th position for black, and so on.

The question is now, can we build a Pi Map that allows you to always survive no matter what number black picks? And that if you were black and white survived you'd be able to survive the rest of the game? This would be the End Game TableBases of this game for all positions of Pi.

Please note this is infinitely harder than doing it for chess! Even if you had all the time in the world and all the space in the world you'd never be done, as black could always pick a number higher than what you have checked and make the whole attempt pointless!

But a Pi Map exists.

Fabrice Bellard has come with a formula (based on Bailey–Borwein–Plouffe's) that allows you to know any arbitrary digit of the Pi's expansion in base 16, and there are methods to convert it to base binary, so it can be converted back to the base 10 that the game uses. In fact this formula is necessary to play the game at all because, how else are you going to check if a move by white or black loses?

With the Bellard formula you can build a Pi map of the part you're interested in (the position where you have to send a move), and play perfectly. You don't need to store all digits of Pi!

A Map of the Multiverse

This is the reason I like the name "map" very much.

Imagine that to get anywhere in your city you needed a map OF YOUR WHOLE COUNTRY. Or OF THE WHOLE WORLD. Or OF THE WHOLE GALAXY. Or OF THE WHOLE UNIVERSE. But it doesn't stop there, some people say that multiple universes with different physical rules exist, and call the whole the Multiverse, or one that contains all possible pasts and futures of the Multiverse the Metaverse. Do you need a map that large to get anywhere in your city?

I mean, you may think it's a long way down the road to the chemist's, but you only need a map from where you are to there to get there, requiring a map of everything that exists would be ludicrous.

A chess map is the same, you don't need a complete map, just a map from this position to the next, and as long as you don't leave this map, you'll be okay. You don't need the solution of all chess positions just like you don't need all the infinite digits of pi.

[mclane]

Maybe it is time to leave computerchess.
The last innovative development came from Fabien letouzey, an outsider. The next new development from Google via the neural net approach. From insiders there was nothing.
Despite clones of known sources.

Programmers are not interested anymore in chess. They are interested in ELO increase and new hardware. But to try out new ideas has stopped.

[dragontamer5788]

Maybe it is time to leave computerchess.
The last innovative development came from Fabien letouzey, an outsider. The next new development from Google via the neural net approach. From insiders there was nothing.
Despite clones of known sources.

Programmers are not interested anymore in chess. They are interested in ELO increase and new hardware. But to try out new ideas has stopped.

I know I've been a bit slow with my programming, but I am making steady progress in my GPU-alpha beta search ideas.

http://talkchess.com/forum3/viewtopic.php?f=7&t=71058

256-way parallel SIMD depth-first AB search is possible, see this more recent post of mine, where I walk through a 4-way SIMD parallel search by hand. I've got basic tests that show that 256x way is possible on my Vega GPU. (1024x workgroups are advertised on Vega64, but in practice there seems to be synchronization bugs when you go above 256x way per workgroup on Vega64)

The issue is that Vega 64 has not 256-threads, but in practice requires 16384 minimum number of threads to fully utilize the system. Scaling this depth-first search from 256x way parallel to 16,384x parallel is my next step. I've got some ideas for how to continue, but I don't think anyone has tried my approach before, so its a bit of guess-and-check for now.

[mclane]

This is all nice but reminds me on STAR trek 5: why does god need a space ship ?!

Why does chess need this enormous hardware?
When I said programmers have no new ideas I did not thought about using more cores.

[smatovic]

This is all nice but reminds me on STAR trek 5: why does god need a space ship ?!

Why does chess need this enormous hardware?
When I said programmers have no new ideas I did not thought about using more cores.

Come on Thorsten, you are really a killjoy, we have the new neural network toys
finally working with chess, and the gearheads build their multi-gpu setups,
yourself said that LC0 plays marvelous on your iPad...so what? And this nn-stuff
really just took-off...

--
Srdja

[mclane]

I said I have it on an old android 10” pad and there it makes 10 NPS and plays marvellous.
That’s not I put it on 256 or 16384 cores and it plays strong.

Is there an app on iPad ? I doubt because ipad is a closed system.

These LC0 NN are very nice indeed. But most idiots only let it run on expensive hardware against stockfish.
I wonder why.

This is a killroy.

The fascination is that it is DIFFERENT.

I am not really interested if it has 1900 or 3200 elo or anything in between.
The fact it is different makes the fun.

[Paloma]

Oh, then i take an engine, change it and then it plays weaker but different, maybe 2400 Elo

[Ovyron]

Maybe it is time to leave computerchess.

I've done it many times. Not just computerchess, but chess entirely.

The problem is that I haven't found a better hobby, so there's no place to run, computerchess sucks you back.

...

Well, last time I came back because of Alpha Zero, I guess it's plausible I try quitting again and leave for good if nothing interesting ever happens. But I expect something big will happen soon, and it not, maybe in 2 years...

[dragontamer5788]

This is all nice but reminds me on STAR trek 5: why does god need a space ship ?!

Why does chess need this enormous hardware?
When I said programmers have no new ideas I did not thought about using more cores.

The Vega64 is $400, uses 300W, and is mass produced for the video-game market. The Vega56 has 88% of the compute power of the Vega64 and is only $280 on Newegg right now. All else considered, this is positively tiny hardware on a shoestring budget.

Its not actually "enormous hardware", this is cheap, commodity hardware that no one really knows how to program well yet. The Chess Community's #1 use of these things is to perform neural-net calculations at apparently only 10% utilization. Which means that if people can figure out the "utilization" problem, they can increase the number of calculations by a factor of 1000%.

There seems to be a multitude of issues that need to be solved with GPU-compute.

I said I have it on an old android 10” pad and there it makes 10 NPS and plays marvellous.
That’s not I put it on 256 or 16384 cores and it plays strong.

Is there an app on iPad ? I doubt because ipad is a closed system.

These LC0 NN are very nice indeed. But most idiots only let it run on expensive hardware against stockfish.
I wonder why.

This is a killroy.

The fascination is that it is DIFFERENT.

I am not really interested if it has 1900 or 3200 elo or anything in between.
The fact it is different makes the fun.

GPU programming is grossly different than CPU programming. Incredibly, extremely different. That's why no one really has good chess engines that fully utilize a GPU yet (no, not even Leela Zero). There's a lot we can do to improve chess engines.

At a minimum, GPU-SIMD style programming could still be approached from a CPU-programmer (in case you don't have any GPUs lying around). AVX2 instructions (8-way 32-bit vectors) are on any system released in the last 5 years, while SSE instructions (4-way 32-bit vectors) have been around for over a decade.

There's numerous people who have tried little SIMD acceleration to parts of their engine. So the concept of SIMD-acceleration has been with us for years, but there are very, very few SIMD engines out there. The one and only successful implementation uses the GPU not for symbolic manipulation, but for matrix-multiplications to accelerate a neural net. The actual search-logic remains in CPU land for LeelaZero.