Since there's only finitely many possible chess games, each taking only finitely many moves, it seems straightforward enough to search mechanically through the entire space, even though this process would take billions of years. Does that mean it's relatively straightforward to write a perfect chess program, even though it would be completely useless?

Yes, it would be straightforward and useless to write an algorithm to play perfect chess. Writing the code to search the entire space is no problem though. Then you run the code, and you wait... and wait.

It would take way longer than billions of years. More like septillions of years.

It's not that easy. In addition to needing a very long time, you also need a very large amount of memory. You can't do a min-max search of the entire game tree without essentially having it all in memory. Since there are about 10^120 positions in chess, the memory required to solve the game tree seems beyond the limits of our universe.

Algorithmically it's easy though, I think was the point.

You don't need to store the entire game tree in memory all at once. Using depth first search the memory requirements are actually quite manageable. If only it didn't take so long...

No. Assuming this isn't some strange level, you and some others are really missing the scale of things here.

As mentioned, there's somewhere around 10^120 positions necessary in the game tree. There's around 10^80 atoms in the universe. If you could somehow store an entire chess position in a single atom of space, the PHYSICAL SIZE of the storage device would still be bigger than our universe! In fact, the size of the "hard disk" would be larger than 1,000,000,000,000,000,000,000,000,000,000,000,000, 000 of our universes. Starting to get a grasp of the scale?

And again, this is all based on the assumption that we could store a chess position in a single atom, which if not impossible - would only happen after a number of revolutionary breakthroughs in our most fundamental understanding of physics.

Nonsense. There are way way less than 10^120 legal chess positions, and you only need to evaluate each one once.

In fact, using conventional hard drive technology you could probably store them all in a hard drive no bigger than our sun. Still impossible, for all intents and purposes, but a googol times more possible than what you suggested.

Mostly I think people see big numbers (like 10^45 or 10^120) and their eyes glaze over. This is acceptable if you are just reading the material, but if you're attempting to lecture others you could be a bit more accurate.

edit: also, as evilsteve mentions, you could solve the problem quite easily with a tiny amount of memory. You don't have to hold all the positions in memory at once. So if you have unlimited time, it really is that simple.

The game tree complexity is vastly greater than the number of positions. I was intentionally precise in my language. And the whole "in memory" debate is a complete red herring here. The scale of this computation is such that memory, in storage, or having people raise or lower their hands to represent bits of storage isn't really going to change the computation time at all, well relative to perceivable time.

You should be more precise yourself before attempting to lecture the lecturer.

Let's just say there are many ways to put them there pieces on that there board.

yes, but that is totally irrelevant. That is why I said you only need to represent each position once, your way involves a googol different copies of each position.

For example, you could solve the game by solving all positions with three pieces left on the board, then four, then five, etc like the Nalimov method for creating tablebases. Every time a piece is captured, you already know the result for the resulting position.

Pretty sure nobody is saying the time complexity is feasible, so let's not argue about that. But RoundTower and I are saying that if you gave the search algorithm an unlimited amount of time to run, it would eventually find the optimal move from any given position. And furthermore it could be implemented to run in a modest amount of memory. That's the part that might be surprising so I'll try to explain how depth first search works.

From the opening position, white has 20 possible moves. A depth first search completes its evaluation for each move before moving on to the next candidate. So once it evaluates 1. a3 as either a win, a loss, or a draw, it no longer needs to store the 1. a3 subtree in memory. It then moves on to 1. a4.

You might say, ok fine so it only has to store 1/20th of the game tree in memory at a time. That's still ridiculously huge and it won't fit in memory. But depth first search is recursive, and the space savings apply at every level of the game tree, not just the top level. A depth first evaluation of any non-terminal position involves performing a depth first search on each possible move from that position, and returns the most favorable of those evaluations for the side to move. So when evaluating the 1. a3 subtree, a depth first search will be applied to each of black's 20 responses. Once 1. a3 a6 has been evaluated, that subtree is no longer stored in memory and the search moves on to 1. a3 a5.

Time complexity increases exponentially with each ply of lookahead. But due to the way memory is freed up after each subtree's evaluation, memory usage only increases linearly as search depth increases. Only one subtree from any given node is ever expanded. I've included skeleton code for depth first search in Java (no I haven't compiled and run it, it's skeleton code because it would rely on the existence of other functions and data structures that I haven't actually written, but I think the names make clear what those would be).

A few obvious ways this could be improved, like it doesn't use alpha/beta pruning which any real chess program would. And as written it wouldn't prefer a mate in 3 over a mate in 50, as long as there's a forced mate. It also doesn't return which move is the best move from a given position, only the position's evaluation. So if you want to know the best move, you'd call depthFirst on the position resulting from each possible move and compare the evaluations.

Well, twice for each position. Once for each player's turn.

Black to move imo

I'm well aware of how searches works. In a past life, I was a software person.

Naive depth first will not work. Nodes are circularly connected = infinite path length possible meaning you need to remember past nodes visited and then the memory saving is gone.

You've heard of threefold repetition and the fifty move rule?

I think the easiest way to solve it would be to start from endgames where the result is known. Then you can slowly add an additional piece or pawn, and solve all those. etc.

Yes I think this is a good way of seeing why total knowledge would allow you to play perfectly. Is there some kind of "dual" game here where you start with a checkmate position and play backwards, sometimes adding pieces to the board, playing the reverse of legitimate moves? How would the winner be decided? Is it some trivial game?

Actually you're right. The current moves without a pawn move and the repetition could just be passed as parameters. I don't see any reason this wouldn't work.

Except the time complexity of this would make the 10^120 number look like a millisecond in comparison as you're searching literally the entire possible gamespace, whereas the 10^120 figure came from games of 40 moves. With legal games beyond 5,000 moves - I can't even fathom the estimated time complexity of this.

Throw together some 20 line pseudo-code for working from mate to start to restrict the gamespace and I'd be impressed.

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

RoundTower, Nalimov tablebases already rely on absolutely enormous amounts of space/memory in their current primitive format and have nothing to do with the depth first deal. And they were never designed to 'solve' chess. They use a ton of hacks/simplifications that become impossible as you increase the number of pieces. It's not like you just go: tbgen 32 and you're set to go if you had infinite time/space. There's no way you can come even remotely close to a reasonable estimate of the space/memory complexity required based on current tablebase data.

With tablebases you solve the time complexity problem but the memory requirements for a 32 piece tablebase are outrageous (not enough atoms in the universe, etc). With depth first search you solve the memory problem but the time requirements are outrageous (heat death of the universe, etc). Not so easy to solve both problems at once. Maybe quantum computing? I know practically nothing about it, just throwing it out there.

Nowhere near this much, like I said earlier it would only take a hard drive approximately the size of the sun (that's still pretty big, of course).

I wonder if there would be a compromise solution: generating (say) 15-piece tablebases and searching the game tree exhaustively up to there.

Of course even if this made the process a trillion times shorter it would still be unachievable.

OK not *all*. But many. :-)

What if the 'perfect' game of chess has absolutely nothing to do with contemporary knowledge, and it's actually a move like 1. a4 with black's only defense being the prophylactic 1. .. g5!!