3 ms·

The number of outcomes in a 50-move chess game does not even come close to the Graham's Number. 10^(number of outcomes in a 50-move chess games) also does not

The number of outcomes in a 50-move chess game does not even come close to the Graham's Number. 10^(number of outcomes in a 50-move chess games) also does not come close.

prezjordan 10y ago
Even 10^10^10... (repeat this the number of outcomes in a 50-move chess game) does not come close to Graham's number.
- wallace_f 10y ago
  Thanks, I was wrong about that. I swore I read that somewhere, turns out it was on a chess forum--not a source I should have committed to long-term memory. I did find this interesting statement about Graham's number (unsure of the veracity): > Graham's number is greater than all of the Planck lengths in the universe. There literally isn't room in the universe to write it out in numerical form. Edit: It looks like we confused Graham's Number for Shannon's number: https://en.wikipedia.org/wiki/Shannon_number https://en.wikipedia.org/wiki/Shannon_number But according to the Wiki on Shannon's number, a the number of possible outcomes in chess does still far exceed the number of atoms in the universe: >Allis also estimated the game-tree complexity to be at least 10123, "based on an average branching factor of 35 and an average game length of 80". As a comparison, the number of atoms in the observable universe, to which it is often compared, is estimated to be between 4×10^79 and 4×10^81.
  - CJefferson 10y ago
    This is a bad kind of argument. There are more 16x16 sudoku boards, and ways of dealing a deck of cards, than there are atoms in the Universe too, but Sudoku and many card games are easy for computers to solve.
    - wallace_f 10y ago
      Well, you should volunteer on the Stockfish engine and show everyone how it's done. I don't believe your comparison between fundamentally different games is sufficient to support your conclusion that an extremely large number of calculations does not pose a challenge for computer programs to solve. Rather, to the best of my knowledge, to support your conclusion what you would need to do is to prove there exists a method or formula for reducing the number of permutations to a manageable number while still coming to an optimal solution. Apparently if Sudoku is easy to solve, that exists in Sudoku, but it certainly does not yet exist in the realm of human knowledge in chess. The fact is that Sudoku and many card games are easy to solve, while chess is in fact a much, much more challenging problem for a computer program, and there are a lot of very smart people that have worked on that problem.
      - CJefferson 10y ago
        I don't disagree that Chess, and Go, and very hard. I don't believe without a major mathematical breakthrough we will see either solved, ever. There just isn't enough possible computing power in the universe. HOWEVER, arguing that they aren't solvable purely from a point of view of "the number of possible games / states is greater than the number of particles in the universe" type arguments is that there are many problems we routinely solve with massive search spaces.
    - wallace_f 10y ago
      Your comment kind of bothers me. Probably because it is both wrong yet says in a rather frank, matter-of-fact way that my argument is bad. Well, you could just do a Google search for yourself to see why your reasoning is wrong. The problem with using a computer to play Go is precisely what I described, the extremely high number of permutations involved, and it's the same concept with chess (Go just has even more of them): https://www.wired.com/2016/01/googles-go-victory-is-just-a-glimpse-of-how-powerful-ai-will-be/ https://www.wired.com/2016/01/googles-go-victory-is-just-a-g...
      - CJefferson 10y ago
        Well, your comment bothered me, so we are all bothered! I still disagree with your argument. The problem with Go isn't just the high number of permutations involved, there are real-world problems, with just as many permutations, which have been solved. The extra problem with Go (and chess to a lesser degree) is that's it's incredibly hard to be sure, with any certainty, to be sure that a move is a "good" choice. Comparing to the sudoku example again, when "playing" sudoku it's usually obvious as soon as you make a bad move, you've put two '1's in the same row/column/box for example. With Go if we want to play well, or perfectly, we really have to explore the entire search space.
        wallace_f 10y ago
        What you're describing is this: Sudoku is a game, and in which to solve it, a computer program has an obvious method to limit possible permutations to compute in finding a solution. In other words, it is not faced with the challenge of a requirement to compute permutations > 10^86 (roughly atoms in the observable universe). In contrast to sudoku, chess and go are games which have no yet discovered or theoretical method to limit permutations to solve, therefore to solve them you would be required to computer permutations > 10^86. So the problem is still with the number of permutations. Like I said in my other post: if you could develop a technique to reduce the number of permutations while still solving the optimal solution then you would be onto something. Right now no one has been able to dream up such a theory and there are a lot of very smart people who have worked on this problem.

The number of outcomes in a 50-move chess game does not even come close to the Graham's Number. 10^(number of outcomes in a 50-move chess games) also does not come close.

prezjordan 10y ago

Even 10^10^10... (repeat this the number of outcomes in a 50-move chess game) does not come close to Graham's number.

wallace_f 10y ago
Thanks, I was wrong about that. I swore I read that somewhere, turns out it was on a chess forum--not a source I should have committed to long-term memory. I did find this interesting statement about Graham's number (unsure of the veracity): > Graham's number is greater than all of the Planck lengths in the universe. There literally isn't room in the universe to write it out in numerical form. Edit: It looks like we confused Graham's Number for Shannon's number: https://en.wikipedia.org/wiki/Shannon_number https://en.wikipedia.org/wiki/Shannon_number But according to the Wiki on Shannon's number, a the number of possible outcomes in chess does still far exceed the number of atoms in the universe: >Allis also estimated the game-tree complexity to be at least 10123, "based on an average branching factor of 35 and an average game length of 80". As a comparison, the number of atoms in the observable universe, to which it is often compared, is estimated to be between 4×10^79 and 4×10^81.
- CJefferson 10y ago
  This is a bad kind of argument. There are more 16x16 sudoku boards, and ways of dealing a deck of cards, than there are atoms in the Universe too, but Sudoku and many card games are easy for computers to solve.
  - wallace_f 10y ago
    Well, you should volunteer on the Stockfish engine and show everyone how it's done. I don't believe your comparison between fundamentally different games is sufficient to support your conclusion that an extremely large number of calculations does not pose a challenge for computer programs to solve. Rather, to the best of my knowledge, to support your conclusion what you would need to do is to prove there exists a method or formula for reducing the number of permutations to a manageable number while still coming to an optimal solution. Apparently if Sudoku is easy to solve, that exists in Sudoku, but it certainly does not yet exist in the realm of human knowledge in chess. The fact is that Sudoku and many card games are easy to solve, while chess is in fact a much, much more challenging problem for a computer program, and there are a lot of very smart people that have worked on that problem.
    - CJefferson 10y ago
      I don't disagree that Chess, and Go, and very hard. I don't believe without a major mathematical breakthrough we will see either solved, ever. There just isn't enough possible computing power in the universe. HOWEVER, arguing that they aren't solvable purely from a point of view of "the number of possible games / states is greater than the number of particles in the universe" type arguments is that there are many problems we routinely solve with massive search spaces.
  - wallace_f 10y ago
    Your comment kind of bothers me. Probably because it is both wrong yet says in a rather frank, matter-of-fact way that my argument is bad. Well, you could just do a Google search for yourself to see why your reasoning is wrong. The problem with using a computer to play Go is precisely what I described, the extremely high number of permutations involved, and it's the same concept with chess (Go just has even more of them): https://www.wired.com/2016/01/googles-go-victory-is-just-a-glimpse-of-how-powerful-ai-will-be/ https://www.wired.com/2016/01/googles-go-victory-is-just-a-g...
    - CJefferson 10y ago
      Well, your comment bothered me, so we are all bothered! I still disagree with your argument. The problem with Go isn't just the high number of permutations involved, there are real-world problems, with just as many permutations, which have been solved. The extra problem with Go (and chess to a lesser degree) is that's it's incredibly hard to be sure, with any certainty, to be sure that a move is a "good" choice. Comparing to the sudoku example again, when "playing" sudoku it's usually obvious as soon as you make a bad move, you've put two '1's in the same row/column/box for example. With Go if we want to play well, or perfectly, we really have to explore the entire search space.
      - wallace_f 10y ago
        What you're describing is this: Sudoku is a game, and in which to solve it, a computer program has an obvious method to limit possible permutations to compute in finding a solution. In other words, it is not faced with the challenge of a requirement to compute permutations > 10^86 (roughly atoms in the observable universe). In contrast to sudoku, chess and go are games which have no yet discovered or theoretical method to limit permutations to solve, therefore to solve them you would be required to computer permutations > 10^86. So the problem is still with the number of permutations. Like I said in my other post: if you could develop a technique to reduce the number of permutations while still solving the optimal solution then you would be onto something. Right now no one has been able to dream up such a theory and there are a lot of very smart people who have worked on this problem.