wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> easy >> Forced Mate from Start?
        
(Message started by: Benoit_Mandelbrot on May 17^th, 2004, 6:00am)

Title: Forced Mate from Start?
Post by Benoit_Mandelbrot on May 17^th, 2004, 6:00am

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.

Title: Re: Forced Mate from Start?
Post by Three Hands on May 17^th, 2004, 6:09am

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...

Title: Re: Forced Mate from Start?
Post by towr on May 17^th, 2004, 7:10am

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)

Title: Re: Forced Mate from Start?
Post by Three Hands on May 17^th, 2004, 9:19am

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 :)

Title: Re: Forced Mate from Start?
Post by Barukh on May 17^th, 2004, 9:34am

on 05/17/04 at 09:19:00, Three Hands wrote:

I don't believe Deeper Blue (I think that's what it was called)

It was called "Deep Blue".

Title: Re: Forced Mate from Start?
Post by towr on May 17^th, 2004, 9:36am

on 05/17/04 at 09:19:00, Three Hands wrote:

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 36¹⁰⁰/ 3*10⁹ / 3600/24/365.25 ~= 4.5 * 10¹⁵⁶ 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*10³¹ years
So even if the branching factor is much smaller than 36 or 37, it's still a ridiculously large number)

Title: Re: Forced Mate from Start?
Post by THUDandBLUNDER on May 17^th, 2004, 1:04pm

I know the answer...but it's too Easy!

Title: Re: Forced Mate from Start?
Post by towr on May 17^th, 2004, 1:06pm

put a gun at your opponents head?

Title: Re: Forced Mate from Start?
Post by THUDandBLUNDER on May 17^th, 2004, 1:39pm

on 05/17/04 at 06:00:01, Benoit_Mandelbrot wrote:

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.

Title: Re: Forced Mate from Start?
Post by THUDandBLUNDER on May 17^th, 2004, 3:26pm

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!

Title: Re: Forced Mate from Start?
Post by chubby checker on May 17^th, 2004, 4:50pm

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.

Title: Re: Forced Mate from Start?
Post by towr on May 18^th, 2004, 12:05am

on 05/17/04 at 15:26:17, THUDandBLUNDER wrote:

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 05/17/04 at 16:50:11, chubby checker wrote:

That's a good argument. It's certainly true that winning most often seems to come down to the opponent screwing up.

Title: Re: Forced Mate from Start?
Post by rmsgrey on May 18^th, 2004, 2:58am

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...

Title: Re: Forced Mate from Start?
Post by towr on May 18^th, 2004, 4:12am

on 05/18/04 at 02:58:02, 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.

Title: Re: Forced Mate from Start?
Post by Benoit_Mandelbrot on May 18^th, 2004, 9:51am

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.

Title: Re: Forced Mate from Start?
Post by BNC on May 18^th, 2004, 2:45pm

on 05/18/04 at 09:51:25, 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.

Title: Re: Forced Mate from Start?
Post by THUDandBLUNDER on May 18^th, 2004, 3:25pm

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.

Title: Re: Forced Mate from Start?
Post by grimbal on May 18^th, 2004, 7:18pm

on 05/17/04 at 07:10:22, 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.

Title: Re: Forced Mate from Start?
Post by THUDandBLUNDER on May 19^th, 2004, 5:19am

Quote:

Plus pawn promotion and game state, minus all impossible positions.

...plus pawn captures.

Quote:

Still too complex

Then divide by (2!)⁶

;)

Title: Re: Forced Mate from Start?
Post by grimbal on May 19^th, 2004, 5:40pm

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.