*Author

Offline LeodipTopic starter

  • Sr. Member
  • ****
  • Posts: 786
  • Country: it
  • Reputation Power: 11
  • Leodip is taking their first peeks out of the Antlion's burrow.Leodip is taking their first peeks out of the Antlion's burrow.
  • Go home Homura, you're drunk.
  • Awards: Slice of Elements 5th Birthday CakeSlice of Elements 4th Birthday Cake
The Perfect Chess Game https://elementscommunity.org/forum/index.php?topic=54643.msg1138791#msg1138791
« on: June 02, 2014, 08:30:37 pm »
In the world of math, games aren't meant for children. Instead, math tries to get everything from the "overly difficult" stage it was at the start to the "completed" status to reach a definite answer.
What would be a definite answer in the game of Chess? The perfect game, of course.
But, what is a perfect game? Before starting this let's define "perfect". When you call a game "perfect" it means that every play was the best possible. The biggest trouble is in exstablishing whether a move is the best possible or it isn't. While there are some obvious things (let's say, the field is only made up of two kings and a queen: letting the queen checkmate the king is, of course, the best move), there are other in which you can't as easily decide.
I've then come up with this method:
Starting with the premise that it involves tons of computations, I think that if a machine with the right algorithm is left to work for a year it MIGHT finish it (however, I'm no computer engineer, I may be wrong).
In Chess, the perfect game is a game that, no matter the opponent move, you won't lose. Thus, if we calculated all of the games, we could build a tree for every move: if a move has at least one path in which everytime it's the opponent's turn he'll have to pick a move that will result into entering another path in which he'll have to enter another path, and so on, until they'll have to choose a path in which you'll either win or draw, it's the perfect game. (I'm aware the explanation might not have been too clear, don't hesitate to ask.)
To ease the calculations, if there's even only one loss, you can delete the whole path from calculations.


I'm no genius, either, and I'll guess this has been though before, so why hasn't this been done yet? is it, indeed, due to a computational problem?

Offline Naesala

  • Legendary Member
  • ******
  • Posts: 3431
  • Country: us
  • Reputation Power: 52
  • Naesala brings all the vitality and activity of a Life Nymph.Naesala brings all the vitality and activity of a Life Nymph.Naesala brings all the vitality and activity of a Life Nymph.Naesala brings all the vitality and activity of a Life Nymph.Naesala brings all the vitality and activity of a Life Nymph.Naesala brings all the vitality and activity of a Life Nymph.Naesala brings all the vitality and activity of a Life Nymph.Naesala brings all the vitality and activity of a Life Nymph.Naesala brings all the vitality and activity of a Life Nymph.Naesala brings all the vitality and activity of a Life Nymph.
  • Awards: Slice of Elements 7th Birthday CakeSlice of Elements 6th Birthday CakeSlice of Elements 5th Birthday CakeSlice of Elements 4th Birthday Cake
Re: The Perfect Chess Game https://elementscommunity.org/forum/index.php?topic=54643.msg1138792#msg1138792
« Reply #1 on: June 02, 2014, 08:40:01 pm »
An error I could see occurring would be an infinite loop of 4 moves, e.g. Player one moves their Knight, 2 moves their rook to threaten, 1 retracts the Knight, 2 retracts the rook. The compute might see these four as the best responses to eachother, and loop this forever.
Your favorite Hotyugh

Offline CuCN

  • Hero Member
  • *****
  • Posts: 1756
  • Reputation Power: 25
  • CuCN is a proud Wyrm taking wing for the first time.CuCN is a proud Wyrm taking wing for the first time.CuCN is a proud Wyrm taking wing for the first time.CuCN is a proud Wyrm taking wing for the first time.CuCN is a proud Wyrm taking wing for the first time.
  • Toxic
  • Awards: Slice of Elements 5th Birthday CakeSlice of Elements 4th Birthday Cake
Re: The Perfect Chess Game https://elementscommunity.org/forum/index.php?topic=54643.msg1138793#msg1138793
« Reply #2 on: June 02, 2014, 08:40:20 pm »
http://en.wikipedia.org/wiki/Solving_chess

An error I could see occurring would be an infinite loop of 4 moves, e.g. Player one moves their Knight, 2 moves their rook to threaten, 1 retracts the Knight, 2 retracts the rook. The compute might see these four as the best responses to eachother, and loop this forever.
This would evaluate as a draw by the threefold repetition rule. Every game of chess is guaranteed by the rules to terminate in finite time.
« Last Edit: June 02, 2014, 08:42:09 pm by CuCN »

Offline Naesala

  • Legendary Member
  • ******
  • Posts: 3431
  • Country: us
  • Reputation Power: 52
  • Naesala brings all the vitality and activity of a Life Nymph.Naesala brings all the vitality and activity of a Life Nymph.Naesala brings all the vitality and activity of a Life Nymph.Naesala brings all the vitality and activity of a Life Nymph.Naesala brings all the vitality and activity of a Life Nymph.Naesala brings all the vitality and activity of a Life Nymph.Naesala brings all the vitality and activity of a Life Nymph.Naesala brings all the vitality and activity of a Life Nymph.Naesala brings all the vitality and activity of a Life Nymph.Naesala brings all the vitality and activity of a Life Nymph.
  • Awards: Slice of Elements 7th Birthday CakeSlice of Elements 6th Birthday CakeSlice of Elements 5th Birthday CakeSlice of Elements 4th Birthday Cake
Re: The Perfect Chess Game https://elementscommunity.org/forum/index.php?topic=54643.msg1138795#msg1138795
« Reply #3 on: June 02, 2014, 08:42:06 pm »
Ah, didn't know that'd count as a draw. Also, thanks for the link ^_^
Your favorite Hotyugh

Offline andretimpa

  • Master of Gravity
  • *
  • ******
  • Posts: 3812
  • Country: br
  • Reputation Power: 58
  • andretimpa is truly a Titan, worthy of respect and acknowledgement.andretimpa is truly a Titan, worthy of respect and acknowledgement.andretimpa is truly a Titan, worthy of respect and acknowledgement.andretimpa is truly a Titan, worthy of respect and acknowledgement.andretimpa is truly a Titan, worthy of respect and acknowledgement.andretimpa is truly a Titan, worthy of respect and acknowledgement.andretimpa is truly a Titan, worthy of respect and acknowledgement.andretimpa is truly a Titan, worthy of respect and acknowledgement.andretimpa is truly a Titan, worthy of respect and acknowledgement.andretimpa is truly a Titan, worthy of respect and acknowledgement.andretimpa is truly a Titan, worthy of respect and acknowledgement.
  • OMG how did I get here I'm not good with computers
  • Awards: Slice of Elements 12th Birthday Cake14th Trials - Master of GravitySong of the Day Tourney Most Creative DeckSlice of Elements 11th Birthday Cake13th Trials - Master of GravitySlice of Elements 10th Birthday CakeArt Competition - RedecoratingSlice of Elements 9th Birthday CakeArt Competition: MS Paint #9 WinnerArt Competition: League of the Battle Champion WinnerArt Competition: Foil ArtWeekly Tournament WinnerSlice of Elements 8th Birthday CakeArt Competition: Paint With Elements - The Elemental AvatarsSlice of Elements 7th Birthday CakeCompetition - A Challenge of Challenges1st Place WC Winner: October 20151st Place Weekly Challenge Winner: September 2015Weekly Design August 2015 - GoldWeekly Design July 2015 - SilverSlice of Elements 6th Birthday CakeForum Brawl #4 WinnerPaint with Elements Competition WinnerSlice of Elements 5th Birthday CakeWeekly Tournament WinnerSlice of Elements 4th Birthday Cake
Re: The Perfect Chess Game https://elementscommunity.org/forum/index.php?topic=54643.msg1138796#msg1138796
« Reply #4 on: June 02, 2014, 08:57:39 pm »
I'm no genius, either, and I'll guess this has been though before, so why hasn't this been done yet? is it, indeed, due to a computational problem?

As you can see in the link CuCn posted it'd take many times the age of the universe with current technology.
Every time a graboid evolves, an elemental gets his wings.
:gravity Guild (old), War 9 & 13 (gen) / :time Brawl 2 & 3, War 7 & 14 / :death War 8 & 12 / :fire Brawl 4 / :entropy Brawl 5 / :darkness War 10

Offline dragonsdemesne

  • Legendary Member
  • ******
  • Posts: 5283
  • Country: aq
  • Reputation Power: 63
  • dragonsdemesne shines with the light of the Morning Glory!dragonsdemesne shines with the light of the Morning Glory!dragonsdemesne shines with the light of the Morning Glory!dragonsdemesne shines with the light of the Morning Glory!dragonsdemesne shines with the light of the Morning Glory!dragonsdemesne shines with the light of the Morning Glory!dragonsdemesne shines with the light of the Morning Glory!dragonsdemesne shines with the light of the Morning Glory!dragonsdemesne shines with the light of the Morning Glory!dragonsdemesne shines with the light of the Morning Glory!dragonsdemesne shines with the light of the Morning Glory!dragonsdemesne shines with the light of the Morning Glory!
  • Leeeeeeeeeeroyyyyyyyyy....
  • Awards: Weekly Tournament WinnerWeekly Tournament WinnerWeekly Tournament WinnerWeekly Tournament WinnerWeekly Tournament WinnerWeekly Tournament WinnerWeekly Tournament WinnerBattle League 1/2014 2nd PlaceWeekly Tournament WinnerBattle League 3/2013 2nd PlaceWeekly Tournament WinnerWeekly Tournament WinnerWeekly Tournament WinnerBattle League 2/2013 WinnerBattle League 1/2013 2nd PlaceWeekly Tournament WinnerChampionship League 3/2012 2nd PlaceWeekly Tournament WinnerWeekly Tournament WinnerChampionship League 2/2012 3rd Place
Re: The Perfect Chess Game https://elementscommunity.org/forum/index.php?topic=54643.msg1138815#msg1138815
« Reply #5 on: June 02, 2014, 11:24:11 pm »
It would be theoretically possible to do this for chess.  However, the complexity is beyond current computation.  In fact, it was only in 2007 that -checkers- was solved in a similar manner to what you describe, and that's obviously way simpler than chess.  (technically, it was only a weak solution, so it wasn't even as good as what you posit)  It was, in fact, solved by a team at the university I attended.  As an aside, my brother also attended there, and studied computer science, and knew the team leader of the people who solved checkers.  Apparently, this professor's 1337 management skillz in the computer science department resulted in their enrollment falling to quite literally -zero- students one year :p  It seems he was a much better researcher than a bureaucrat.

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

For chess, they've solved all the endgames back to about 6 or 7 moves prior to checkmate, but that's as far as they've gotten, unless breakthroughs have been made since I last looked into it, so a lot of work still remains.

Offline BluePriest

  • Legendary Member
  • ******
  • Posts: 3771
  • Reputation Power: 46
  • BluePriest is towering like an Amethyst Dragon over their peers.BluePriest is towering like an Amethyst Dragon over their peers.BluePriest is towering like an Amethyst Dragon over their peers.BluePriest is towering like an Amethyst Dragon over their peers.BluePriest is towering like an Amethyst Dragon over their peers.BluePriest is towering like an Amethyst Dragon over their peers.BluePriest is towering like an Amethyst Dragon over their peers.BluePriest is towering like an Amethyst Dragon over their peers.BluePriest is towering like an Amethyst Dragon over their peers.
  • Entropy Has You
  • Awards: Slice of Elements 5th Birthday Cake
Re: The Perfect Chess Game https://elementscommunity.org/forum/index.php?topic=54643.msg1138840#msg1138840
« Reply #6 on: June 03, 2014, 03:42:39 am »
From wikipedia link cucn calculated....
(according to Shannon, 1090 years on a 1 MHz processor) puts this possibility beyond the limits of any "feasible" (as of 1950) technology.


http://blogs.nvidia.com/blog/2012/11/14/why-the-worlds-fastest-computer-is-a-scientific-time-machine/

Titan has a peak performance of more than 27 petaflops – or 27 thousand trillion calculations per second


So math it up....
That means it can calculate the solution in 1.1744367e+96 years
This sig was interrupted by Joe Biden

Offline RootRanger

  • Legendary Member
  • ******
  • Posts: 3118
  • Reputation Power: 51
  • RootRanger brings all the vitality and activity of a Life Nymph.RootRanger brings all the vitality and activity of a Life Nymph.RootRanger brings all the vitality and activity of a Life Nymph.RootRanger brings all the vitality and activity of a Life Nymph.RootRanger brings all the vitality and activity of a Life Nymph.RootRanger brings all the vitality and activity of a Life Nymph.RootRanger brings all the vitality and activity of a Life Nymph.RootRanger brings all the vitality and activity of a Life Nymph.RootRanger brings all the vitality and activity of a Life Nymph.RootRanger brings all the vitality and activity of a Life Nymph.
  • R A I N B R O S
  • Awards: Slice of Elements 13th Birthday CakeSlice of Elements 9th Birthday Cake10th Trials - Master of FireElemental Conquest WinnerWriting Competition - Across(tic) the World of ElementsWeekly Tournament Winner1st Grandmaster Battle Winner - FireThere Can Be Only One - 2016 WinnerGold DonorChampionship League 2/2015 2nd Place9th Trials - Master of FireElements: A Game of Politics - WinnerEnder of War War #8 Winner - Team FireWeekly Tournament WinnerWeekly Tournament WinnerWeekly Tournament WinnerWeekly Tournament WinnerChampionship League 1/2013 WinnerWeekly Tournament WinnerWar #4 Winner - Team DeathChampionship League 3/2011 3rd PlaceWeekly Tournament WinnerWeekly Tournament WinnerWeekly Tournament WinnerBeginners League 2/2011 2nd PlaceWeekly PvP Tournament WinnerWeekly PvP Tournament WinnerBeginners League 1/2011 2nd PlaceWeekly PvP Tournament Winner
Re: The Perfect Chess Game https://elementscommunity.org/forum/index.php?topic=54643.msg1138842#msg1138842
« Reply #7 on: June 03, 2014, 03:47:54 am »
So, here's a fun question. If two computers both play a perfect game against each other, is it a draw or does white win?

In the case of tic-tac-toe, it's easy to see that it's a draw. Connect 4 ends in a victory for the player that goes first.

Any thoughts on how chess would end?
Somehow still around, somewhat

Offline Pineapple

  • Legendary Member
  • ******
  • Posts: 4105
  • Country: us
  • Reputation Power: 0
  • Pineapple hides under a Cloak.
  • Master of Cake
  • Awards: Silver DonorSlice of Elements 5th Birthday CakeSlice of Elements 4th Birthday CakeSlice of Elements 3rd Birthday CakeSlice of Elements 2nd Birthday Cake
Re: The Perfect Chess Game https://elementscommunity.org/forum/index.php?topic=54643.msg1138849#msg1138849
« Reply #8 on: June 03, 2014, 06:01:49 am »
Food for thought: what's the perfect game in Rock, Paper, Scissors?
For there to be a "perfect move" in any instance of the game, all other moves must undeniably lead to a loss.

Offline BluePriest

  • Legendary Member
  • ******
  • Posts: 3771
  • Reputation Power: 46
  • BluePriest is towering like an Amethyst Dragon over their peers.BluePriest is towering like an Amethyst Dragon over their peers.BluePriest is towering like an Amethyst Dragon over their peers.BluePriest is towering like an Amethyst Dragon over their peers.BluePriest is towering like an Amethyst Dragon over their peers.BluePriest is towering like an Amethyst Dragon over their peers.BluePriest is towering like an Amethyst Dragon over their peers.BluePriest is towering like an Amethyst Dragon over their peers.BluePriest is towering like an Amethyst Dragon over their peers.
  • Entropy Has You
  • Awards: Slice of Elements 5th Birthday Cake
Re: The Perfect Chess Game https://elementscommunity.org/forum/index.php?topic=54643.msg1138851#msg1138851
« Reply #9 on: June 03, 2014, 06:06:23 am »
to compound on my previous post.... Lets assume moores law that processor speed doubles every 2 years is correct.

In 10 years it would take 3.6701148e+94 years. That means it takes off 1.1377356e+96 years. Now many people assume moores law is on the decline due to limits of the materials we use to make the processors. Silicon overheats too easily, and thats just one of its limitation. Who knows how far computer power will go. Now there are 64 squares on a chessboard, so lets assume you use 64 of the computers that were mentioned in my last post. Each of them are checking a seperate path. That would mean it would take 5.7345544e+92 years if we had 64 of those computers.  How many of those computers do we need to have it be a reasonable amount of time to figure this out? Lets say we want it to be figured out in 1000 years. Im sure theres a mathy way to solve for 1000 using x, but its too late for algebra. Im going to use 1,000,000 computers (which Id say we all agree is a completely outlandish amount of these computers to make). If we had 1,000,000 of these computers calculating nonstop, each a different combination, then it would take 3.6701148e+88 years to figure this out. 

Now, there are 1,966,514,816 computers connected to the internet. Lets assume that each of these are this super computer. If all of these computers teamed up to solve that task, it would take 1.8663042e+85 years.

tldr, dont expect an answer to come up any time soon, unless theres some breakthrough and a mathematical formula is discovered that would be able to be used to calculate this. The number is going down, but not nearly fast enough.

11744367000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 years if just that one computer tried to calculate it.
186630420000000000000000000000000000000000000000000000000000000000000000000000000000000 years if all the computers connected to the internet were this supercomputer and tried to calculate it

The formula I used to calculate this was 1e+120/(8.64e+17 * x)/86400/365. x is the amount of computers calculating this, 86,400 is the amount of seconds in a day, and 365 is the amount of days in a year (obviously i didnt calculate leap year, I could have used 365.25 if I wanted to be more accurate). Im assuming thats the correct way isnt it?
This sig was interrupted by Joe Biden

Offline andretimpa

  • Master of Gravity
  • *
  • ******
  • Posts: 3812
  • Country: br
  • Reputation Power: 58
  • andretimpa is truly a Titan, worthy of respect and acknowledgement.andretimpa is truly a Titan, worthy of respect and acknowledgement.andretimpa is truly a Titan, worthy of respect and acknowledgement.andretimpa is truly a Titan, worthy of respect and acknowledgement.andretimpa is truly a Titan, worthy of respect and acknowledgement.andretimpa is truly a Titan, worthy of respect and acknowledgement.andretimpa is truly a Titan, worthy of respect and acknowledgement.andretimpa is truly a Titan, worthy of respect and acknowledgement.andretimpa is truly a Titan, worthy of respect and acknowledgement.andretimpa is truly a Titan, worthy of respect and acknowledgement.andretimpa is truly a Titan, worthy of respect and acknowledgement.
  • OMG how did I get here I'm not good with computers
  • Awards: Slice of Elements 12th Birthday Cake14th Trials - Master of GravitySong of the Day Tourney Most Creative DeckSlice of Elements 11th Birthday Cake13th Trials - Master of GravitySlice of Elements 10th Birthday CakeArt Competition - RedecoratingSlice of Elements 9th Birthday CakeArt Competition: MS Paint #9 WinnerArt Competition: League of the Battle Champion WinnerArt Competition: Foil ArtWeekly Tournament WinnerSlice of Elements 8th Birthday CakeArt Competition: Paint With Elements - The Elemental AvatarsSlice of Elements 7th Birthday CakeCompetition - A Challenge of Challenges1st Place WC Winner: October 20151st Place Weekly Challenge Winner: September 2015Weekly Design August 2015 - GoldWeekly Design July 2015 - SilverSlice of Elements 6th Birthday CakeForum Brawl #4 WinnerPaint with Elements Competition WinnerSlice of Elements 5th Birthday CakeWeekly Tournament WinnerSlice of Elements 4th Birthday Cake
Re: The Perfect Chess Game https://elementscommunity.org/forum/index.php?topic=54643.msg1138852#msg1138852
« Reply #10 on: June 03, 2014, 06:12:29 am »
@Root That is easier to prove (its what they call ultra weak solving). Even this one has not been done, so no one knows.

@Pinapple The players don't play alternatedly, so RPS doesn't satisfy the hypothesis of the theorem that says an optimal strategy exists http://en.m.wikipedia.org/wiki/Zermelo's_theorem_(game_theory)

An even worse game than RPS is the minority game. Put an odd number of friends together and everyone chooses either A or B. The ones that choose the same as the minority win.
Every time a graboid evolves, an elemental gets his wings.
:gravity Guild (old), War 9 & 13 (gen) / :time Brawl 2 & 3, War 7 & 14 / :death War 8 & 12 / :fire Brawl 4 / :entropy Brawl 5 / :darkness War 10

Offline CuCN

  • Hero Member
  • *****
  • Posts: 1756
  • Reputation Power: 25
  • CuCN is a proud Wyrm taking wing for the first time.CuCN is a proud Wyrm taking wing for the first time.CuCN is a proud Wyrm taking wing for the first time.CuCN is a proud Wyrm taking wing for the first time.CuCN is a proud Wyrm taking wing for the first time.
  • Toxic
  • Awards: Slice of Elements 5th Birthday CakeSlice of Elements 4th Birthday Cake
Re: The Perfect Chess Game https://elementscommunity.org/forum/index.php?topic=54643.msg1138853#msg1138853
« Reply #11 on: June 03, 2014, 06:18:43 am »
Food for thought: what's the perfect game in Rock, Paper, Scissors?
For there to be a "perfect move" in any instance of the game, all other moves must undeniably lead to a loss.
There is a perfect strategy for RPS: play randomly (1/3 chance of each move). The perfect game would be both players choosing moves at random.

 

anything
blarg: