home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #20 / NN_1992_20.iso / spool / sci / math / 11487 < prev    next >
Encoding:
Internet Message Format  |  1992-09-15  |  2.3 KB
  1. Path: sparky!uunet!spool.mu.edu!sdd.hp.com!swrinde!zaphod.mps.ohio-state.edu!news.acns.nwu.edu!network.ucsd.edu!news.service.uci.edu!beckman.com!dn66!a_rubin
  2. From: a_rubin@dsg4.dse.beckman.com (Arthur Rubin)
  3. Newsgroups: sci.math
  4. Subject: Re: Chess Problem
  5. Message-ID: <a_rubin.716570815@dn66>
  6. Date: 15 Sep 92 15:26:55 GMT
  7. References: <BuFpLp.9nI@ecf.toronto.edu> <1992Sep12.174545.23214@ima.isc.com> 
  8.  <1992Sep13.003856.13264@infodev.cam.ac.uk> <1992Sep15.032439.19637@ll.mit.edu>
  9. Lines: 47
  10. Nntp-Posting-Host: dn66.dse.beckman.com
  11.  
  12. In <1992Sep15.032439.19637@ll.mit.edu> shoham@ll.mit.edu (Daniel Shoham) writes:
  13.  
  14. >>In article <1992Sep12.174545.23214@ima.isc.com>, karl@ima.isc.com (Karl Heuer) writes:
  15. >>
  16. >>> Here's a more advanced chessboard question.
  17. >>> 
  18. >>> A white king, a black king, and a white pawn are randomly placed on an NxN
  19. >>> chessboard.  (Independent, uniform distributions.)  What is the limit, as
  20. >>> N -> infinity, of the probability that the position is a win for white?
  21. >>> 
  22. >>> (Note that it doesn't matter what you do about collisions or illegal
  23. >>> positions, since they occur with probability zero in the limit.)
  24. >>
  25.  
  26. >We will use an x-y system to describe the position of each square. The last
  27. >(queening) row is defined as y=0, whereas the first row is y=1. x, is similarly
  28. >ranged between 0 and 1.
  29. >(px,py) = pawn's starting position
  30. >(bx,by) = black (king) starting position
  31. >(wx,wy) = white (king) starting position
  32.  
  33. >px, py, bx, by, wx, wy are iidrv with uniform (0,1) distribution.
  34.  
  35. >Strategy 1 works if:
  36. >py < by  or  py < |px-bx|
  37.  
  38. >Strategy 2 works if:
  39. >d(p,w) < d(p,b)      where d(i,j)=max(|ix-jx| , |iy-jy|)  (i.e. chess-distance)
  40.  
  41. >We could now use brute force to integrate over all cases, or (if your religion
  42. >permits it) do a Monte Carlo simulation.
  43.  
  44. >As my religion does not forbid me from doing a Monte Carlo after I have found
  45. >an analytic algorithm (that I am too lazy to integrate), I did it:
  46.  
  47. >P(Draw) =~ 12.5%  (40,000 runs, i.e. +/- .5%)
  48.  
  49. Funny, I get 43/192 for the analytic answer, which is 22.4%.
  50.  
  51.  
  52. >Dan Shoham
  53. >shoham@ll.mit.edu
  54. --
  55. Arthur L. Rubin: a_rubin@dsg4.dse.beckman.com (work) Beckman Instruments/Brea
  56. 216-5888@mcimail.com 70707.453@compuserve.com arthur@pnet01.cts.com (personal)
  57. My opinions are my own, and do not represent those of my employer.
  58. My interaction with our news system is unstable; please mail anything important.
  59.