home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #20 / NN_1992_20.iso / spool / sci / math / 11335 < prev    next >
Encoding:
Internet Message Format  |  1992-09-12  |  2.7 KB
  1. Path: sparky!uunet!mcsun!uknet!pavo.csi.cam.ac.uk!camcus!gjm11
  2. From: gjm11@cus.cam.ac.uk (G.J. McCaughan)
  3. Newsgroups: sci.math
  4. Subject: Re: Chess Problem
  5. Message-ID: <1992Sep13.003856.13264@infodev.cam.ac.uk>
  6. Date: 13 Sep 92 00:38:56 GMT
  7. References: <BuFpLp.9nI@ecf.toronto.edu> <1992Sep12.174545.23214@ima.isc.com>
  8. Sender: news@infodev.cam.ac.uk (USENET news)
  9. Organization: U of Cambridge, England
  10. Lines: 45
  11. Nntp-Posting-Host: apus.cus.cam.ac.uk
  12.  
  13. In article <1992Sep12.174545.23214@ima.isc.com>, karl@ima.isc.com (Karl Heuer) writes:
  14.  
  15. > Here's a more advanced chessboard question.
  16. > 
  17. > A white king, a black king, and a white pawn are randomly placed on an NxN
  18. > chessboard.  (Independent, uniform distributions.)  What is the limit, as
  19. > N -> infinity, of the probability that the position is a win for white?
  20. > 
  21. > (Note that it doesn't matter what you do about collisions or illegal
  22. > positions, since they occur with probability zero in the limit.)
  23.  
  24. Eek. Let's think... (This is much better than the last one, to which the
  25. answer is of course 8!/(64 choose 8) = 560/61474519, or about 9.109e-6)
  26.  
  27. If the pawn is a "rook's pawn", funny things happen; but that's only
  28. probability 2/N, so we can forget that.
  29. If the black king is behind the white pawn [but not next to it, but
  30. that's only 8/N^2] then White wins, always.
  31. If the black king is in front of the white pawn, but "too far from" it
  32. (i.e. can't reach the promoting square before the pawn does) then White
  33. wins by rushing the pawn forwards.
  34. If the black king is in front of the pawn, and in range, then it all depends
  35. on how the two kings are placed. If the white king is further away from the
  36. pawn than the black one, then Black clearly draws. If the white king is closer
  37. to the pawn, then White wins (except in O(1/N) of the cases, where it depends
  38. on parity considerations) by getting in front of the pawn and keeping the
  39. opposition.
  40.  
  41. [thinks: if I haven't made a mistake, all the interesting chess is in O(1/N)
  42. of the cases...]
  43.  
  44. Right. So we want the probability that the black king is (i) within the pawn's
  45. "light cone" and (ii) closer to the pawn than the white king. A moment ago I
  46. thought this was really easy, but it's not quite as nice as I thought...
  47. I think it might be preferable to place the kings first, so to speak,
  48. and then we want the probability that the pawn is within the "reverse light
  49. cone" of the black king and closer to it than to the white king. Ugh.
  50.  
  51. I don't think I have the patience for this right now, at least not without
  52. pencil and paper to hand. Still, I've reduced the problem to the point at
  53. which it's just a matter of summing some fairly easy (ha!) series. 
  54.  
  55. -- 
  56. Gareth McCaughan     Dept. of Pure Mathematics & Mathematical Statistics,
  57. gjm11@cus.cam.ac.uk  Cambridge University, England.    [Research student]
  58.