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