Author |
Topic: Forced Mate from Start? (Read 784 times) |
|
Benoit_Mandelbrot
Junior Member
Almost doesn't count.
Gender: 
Posts: 133
|
 |
Forced Mate from Start?
« on: May 17th, 2004, 6:00am » |
 Quote  Modify
|
Lets say that we use the starting position of a normal game of chess. If white goes first, can there be a forced mate within 100 plies for white? Can there be a sure way for white to win, no matter how black plays? Black cannot help you achieve the checkmate.
|
| « Last Edit: May 17th, 2004, 9:12am by Benoit_Mandelbrot » |
 IP Logged |
Because of modulo, different bases, and significant digits, all numbers equal each other!
|
|
|
Three Hands
Uberpuzzler
Gender:
Posts: 715
|
|
Re: Forced Mate from Start?
« Reply #1 on: May 17th, 2004, 6:09am » |
Quote Modify
|
I would imagine that, if there was some way of white forcing mate that people knew of regardless of how black played, then chess grandmasters are either involved in some gigantic cover-up, or are not playing to win half the time.
Hence, I would imagine that it is not possible to force mate when starting - although you do seem to get an advantage when playing first in chess...
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Forced Mate from Start?
« Reply #2 on: May 17th, 2004, 7:10am » |
Quote Modify
|
I'd go with 'there is no known way', however there may still be a way (which is simply unknown)
If we ever get a working quantumcomputer we may find out. But for now ~37^100 is still a bit too complex.
Also, even if there is a way, and we know it, it's still doubtfull anyone without a computer at hand can use it. Because they would have to remember what move to do at any of their adversaries moves at any stage in the game.
(There are much simpler games for which a guaranteed-win strategy is known, but which can't be used by human players for the same reason)
|
| « Last Edit: May 17th, 2004, 7:14am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Three Hands
Uberpuzzler
Gender:
Posts: 715
|
|
Re: Forced Mate from Start?
« Reply #3 on: May 17th, 2004, 9:19am » |
Quote Modify
|
I think it would probably have to be the "there is no known way" answer, since computers have been programmed to play chess, and I don't believe Deeper Blue (I think that's what it was called) was guaranteed to win when playing white, even if it managed to beat Kasparov 
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Forced Mate from Start?
« Reply #4 on: May 17th, 2004, 9:34am » |
Quote Modify
|
on May 17th, 2004, 9:19am, Three Hands wrote:| I don't believe Deeper Blue (I think that's what it was called) |
|
It was called "Deep Blue".
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Forced Mate from Start?
« Reply #5 on: May 17th, 2004, 9:36am » |
Quote Modify
|
on May 17th, 2004, 9:19am, Three Hands wrote:| I think it would probably have to be the "there is no known way" answer, since computers have been programmed to play chess, and I don't believe Deeper Blue (I think that's what it was called) was guaranteed to win when playing white, even if it managed to beat Kasparov |
|
Yes, but that is only because it was too slow and had too little memory to see that far ahead..
To get the answer you need the full brute force tree of moves, and not just clever guesses at good moves (which is what most computers use to get any decent depth)
the branching factor for chess is about 36 in a random board, I think..
A standard computer would take 36100/ 3*109 / 3600/24/365.25 ~= 4.5 * 10156 years to calculate to a depth of 100 plies. The best supercomputer has something in the range of 64k parallel vector processors, nothing close to making a dent in that time.
(Note, even if there were just two moves for each board, it would still take 1.3*1031 years
So even if the branching factor is much smaller than 36 or 37, it's still a ridiculously large number)
|
| « Last Edit: May 17th, 2004, 9:43am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Forced Mate from Start?
« Reply #6 on: May 17th, 2004, 1:04pm » |
Quote Modify
|
I know the answer...but it's too Easy!
|
|
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Forced Mate from Start?
« Reply #8 on: May 17th, 2004, 1:39pm » |
Quote Modify
|
on May 17th, 2004, 6:00am, Benoit_Mandelbrot wrote:| Lets say that we use the starting position of a normal game of chess. If white goes first, can there be a forced mate within 100 plies for white? Can there be a sure way for white to win, no matter how black plays? Black cannot help you achieve the checkmate. |
|
It is very, very unlikely that either side has a forced mate within 50 moves.
On the other hand, it is merely very unlikely that White (or Black) has a forced win at all.
It is even theoretically possible for White to lose if he can be forced into a zugzwang position.
|
| « Last Edit: May 18th, 2004, 3:42am by ThudnBlunder » |
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Forced Mate from Start?
« Reply #9 on: May 17th, 2004, 3:26pm » |
Quote Modify
|
Quote:the branching factor for chess is about 36 in a random board, I think..
A standard computer would take 36100/ 3*109 / 3600/24/365.25 ~= 4.5 * 10156 years to calculate to a depth of 100 plies. |
|
But a branching factor of n can be reduced to one of roughly [smiley=surd.gif]n by using mini-max techniques alone.
These days, 'intelligent' selective search algorithms can have branching factors as low as 3!
|
|
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
chubby checker
Guest
|
|
Re: Forced Mate from Start?
« Reply #10 on: May 17th, 2004, 4:50pm » |
Quote Modify
 Remove
|
I don't believe white can force a win in any number of moves. Assuming that with two inifinitely fast computers with infinite memory it would be impossible for black to force a win, then black will be playing from the very start of the game for what would be the best possible outcome for him, that is, a draw. And a draw is much easier to achieve than a win, certainly enough so to overcome the small advantage white has by playing first.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Forced Mate from Start?
« Reply #11 on: May 18th, 2004, 12:05am » |
Quote Modify
|
on May 17th, 2004, 3:26pm, THUDandBLUNDER wrote:But a branching factor of n can be reduced to one of roughly [smiley=surd.gif]n by using mini-max techniques alone.
These days, 'intelligent' selective search algorithms can have branching factors as low as 3!
|
|
I don't see how you can use mini-max without having the whole searchtree beforehand, and once you do it's hardly an issue anymore.
And 'intelligent' selective search allways puts you at risk for overlooking certain solutions. You may have to play something that seems very suboptimal but pays off 73 plies later.
on May 17th, 2004, 4:50pm, chubby checker wrote:| I don't believe white can force a win in any number of moves. Assuming that with two inifinitely fast computers with infinite memory it would be impossible for black to force a win, then black will be playing from the very start of the game for what would be the best possible outcome for him, that is, a draw. And a draw is much easier to achieve than a win, certainly enough so to overcome the small advantage white has by playing first. |
|
That's a good argument. It's certainly true that winning most often seems to come down to the opponent screwing up.
|
| « Last Edit: May 18th, 2004, 12:09am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
rmsgrey
Uberpuzzler
   
Gender:
Posts: 2874
|
|
Re: Forced Mate from Start?
« Reply #12 on: May 18th, 2004, 2:58am » |
Quote Modify
|
As I recall, Deep Blue lost to Kasparov, but an improved version, Deeper Blue, beat him. There was also some fuss made about the technicians cheating somehow (something about tweaking the program between games?)
As far as which player wins, as far as I know, no-one's even proved that black can't force a win from the start position. The smart money is on either stalemate or a white win, but it's possible black may be lucky...
|
| « Last Edit: May 18th, 2004, 3:17am by rmsgrey » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Forced Mate from Start?
« Reply #13 on: May 18th, 2004, 4:12am » |
Quote Modify
|
on May 18th, 2004, 2:58am, rmsgrey wrote:| There was also some fuss made about the technicians cheating somehow (something about tweaking the program between games?) |
|
It wasn't really cheating, they just tuned the program to Kasparovs style of playing chess. It's a perfectly valid strategy, and I'm sure most chess players would study their opponents games if they had the time to prepare.
The only problem is that the program/computer becomes to specialized at beating on man, and so may do poorly (relatively) against other opponents. It might well have had a much more difficult time playing against the top ten from chess.
|
| « Last Edit: May 18th, 2004, 4:18am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Benoit_Mandelbrot
Junior Member
Almost doesn't count.
Gender:
Posts: 133
|
|
Re: Forced Mate from Start?
« Reply #14 on: May 18th, 2004, 9:51am » |
Quote Modify
|
Kasparov has one of the highest ratings ever, if not the best, over 2800 I believe. Fischer was less than that I also believe. I believe, I believe, I believe!
I believe believe has lost it's meaning to me. Am I even spelling it right anymore? It seems wrong now.
I have Chessmaster 7000, and Chessmaster's rating is 2671. Besides versing Deep Blue, Kasparov may be close to invincible. The problem with the personality is that the real Kasparov is more powerful than the best of Chessmaster, so the computer personality of Kasparov is dummed down. I still lose to it, but Chessmaster beats Kasparov each time. I can beat ratings of 1300 though. I haven't tried about 1500 yet. Maybe I should.
|
|
IP Logged |
Because of modulo, different bases, and significant digits, all numbers equal each other!
|
|
|
BNC
Uberpuzzler
Gender:
Posts: 1732
|
|
Re: Forced Mate from Start?
« Reply #15 on: May 18th, 2004, 2:45pm » |
Quote Modify
|
on May 18th, 2004, 9:51am, Benoit_Mandelbrot wrote:Kasparov has one of the highest ratings ever, if not the best, over 2800 I believe.
|
|
Yes, the highest ever (FIDE 2851).
Quote:
Fischer was less than that I also believe.
|
|
True, but he was the first ever to pass 2700.
|
|
IP Logged |
How about supercalifragilisticexpialidociouspuzzler [Towr, 2007]
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Forced Mate from Start?
« Reply #16 on: May 18th, 2004, 3:25pm » |
Quote Modify
|
Quote:| Kasparov has one of the highest ratings ever, if not the best, over 2800 I believe. Fischer was less than that |
|
An Elo of 2851 was, and probably will remain, the highest that Kasparov achieved.
Currently he is on 2817, still 43 points ahead of Anand on 2774.
Fischer's highest Elo was 2780 (or 2785 if your source happens to be American),
which would be even higher today because of 'inflation'.
Unlike Kasparov, Fischer never maintained such a high Elo for any length of time,
as he effectively retired after the Spassky match.
|
| « Last Edit: May 19th, 2004, 6:55am by ThudnBlunder » |
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Forced Mate from Start?
« Reply #17 on: May 18th, 2004, 7:18pm » |
Quote Modify
|
on May 17th, 2004, 7:10am, towr wrote:If we ever get a working quantumcomputer we may find out. But for now ~37^100 is still a bit too complex.
|
|
If you just consider all possible positions, you are down to something in the order of 3e44 (64!/32!/8!/8!).
Plus pawn promotion and game state, minus all impossible positions.
Still too complex.
|
|
IP Logged |
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Forced Mate from Start?
« Reply #18 on: May 19th, 2004, 5:19am » |
Quote Modify
|
Quote:| Plus pawn promotion and game state, minus all impossible positions. |
|
...plus pawn captures.
Quote:
Then divide by (2!)6
|
| « Last Edit: May 19th, 2004, 5:57am by ThudnBlunder » |
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Forced Mate from Start?
« Reply #19 on: May 19th, 2004, 5:40pm » |
Quote Modify
|
Indeed!  All captures should be considered. Except two of them.
And there are the bishops that cannot go everywhere. I just wanted to show that if you are going to evaluate all games, it is much much faster to enumerate positions than the tree of all possible games.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print