home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #20 / NN_1992_20.iso / spool / sci / math / 11454 < prev    next >
Encoding:
Internet Message Format  |  1992-09-14  |  2.7 KB
  1. Path: sparky!uunet!sun-barr!ames!agate!stanford.edu!rutgers!micro-heart-of-gold.mit.edu!xn.ll.mit.edu!ll.mit.edu!shoham
  2. From: shoham@ll.mit.edu (Daniel Shoham)
  3. Newsgroups: sci.math
  4. Subject: Re: Chess Problem
  5. Message-ID: <1992Sep15.032439.19637@ll.mit.edu>
  6. Date: 15 Sep 92 03:24:39 GMT
  7. References: <BuFpLp.9nI@ecf.toronto.edu> <1992Sep12.174545.23214@ima.isc.com> <1992Sep13.003856.13264@infodev.cam.ac.uk>
  8. Sender: news@ll.mit.edu
  9. Organization: MIT Lincoln Laboratory
  10. Lines: 58
  11.  
  12. >In article <1992Sep12.174545.23214@ima.isc.com>, karl@ima.isc.com (Karl Heuer) writes:
  13. >
  14. >> Here's a more advanced chessboard question.
  15. >> 
  16. >> A white king, a black king, and a white pawn are randomly placed on an NxN
  17. >> chessboard.  (Independent, uniform distributions.)  What is the limit, as
  18. >> N -> infinity, of the probability that the position is a win for white?
  19. >> 
  20. >> (Note that it doesn't matter what you do about collisions or illegal
  21. >> positions, since they occur with probability zero in the limit.)
  22. >
  23. We will assume optimal players on both sides (otherwise the question is
  24. meaningless).
  25.  
  26. As stated, the probability is zero. A chess game is declared a draw
  27. after 50 moves without an irreversible one. Even if white manages to get a
  28. queen, the probability of finding the black king within 50 squares of an edge
  29. is -> 0.
  30.  
  31. Suppose the 50-moves rule has been removed, and all that is needed is to queen
  32. the pawn.
  33.  
  34. In a very large board, the likelihood of any of the three pieces starting
  35. anywhere near any of the edges or each other is -> 0 so we will ignore it.
  36.  
  37. As I see it, white has a choice of two stratgies:
  38. 1. Run the pawn down and queen it without a king defense.
  39. 2. Move the king toward the pawn and defend it. Then advance the two in tandem.
  40.  
  41. (strategies where the king and pawn move toward each other may save time, but
  42. they work just as well as strategy 2).
  43.  
  44. We will use an x-y system to describe the position of each square. The last
  45. (queening) row is defined as y=0, whereas the first row is y=1. x, is similarly
  46. ranged between 0 and 1.
  47. (px,py) = pawn's starting position
  48. (bx,by) = black (king) starting position
  49. (wx,wy) = white (king) starting position
  50.  
  51. px, py, bx, by, wx, wy are iidrv with uniform (0,1) distribution.
  52.  
  53. Strategy 1 works if:
  54. py < by  or  py < |px-bx|
  55.  
  56. Strategy 2 works if:
  57. d(p,w) < d(p,b)      where d(i,j)=max(|ix-jx| , |iy-jy|)  (i.e. chess-distance)
  58.  
  59. We could now use brute force to integrate over all cases, or (if your religion
  60. permits it) do a Monte Carlo simulation.
  61.  
  62. As my religion does not forbid me from doing a Monte Carlo after I have found
  63. an analytic algorithm (that I am too lazy to integrate), I did it:
  64.  
  65. P(Draw) =~ 12.5%  (40,000 runs, i.e. +/- .5%)
  66.  
  67.  
  68. Dan Shoham
  69. shoham@ll.mit.edu
  70.