dim@whuxlm.UUCP (McCooey David I) (03/20/86)
> IN fact this brings an interesting point... > For the above scoring method to be valid the game tree MUST be FINITE > (taken from the first move) > Ie from an move 1 tere MUST be a forced win for white or a forced > draw for black. > The question : IS THERE ? > If there is not I think that chess might be considered non-deterministic > in the sense that the only analysis possible is heuristic. It is still possible, although highly unlikely, that BLACK has a forced win in chess. This would be the case if every move that WHITE could make from the opening position left BLACK with a won game. Two interesting questions arise from this: 1. Since there is no way we will ever be able to fully analyze chess, is it possible nonetheless to determine the PROBABILITY of BLACK having a forced win from the opening position? (The same goes for a forced DRAW or for a forced WHITE win.) 2. Can anyone find a symmetric position (like the opening position) where it is WHITE to move but BLACK has a forced win? In other words, are there any symmetric zugzwangs for WHITE? (I'm sure there must be some real simple position...) I would like to hear what other people on the net think of this. Dave McCooey AT&T Bell Labs, Whippany ihnp4!whuxlk!dim
ark@alice.UucP (Andrew Koenig) (03/21/86)
> 1. Since there is no way we will ever be able to fully analyze > chess, is it possible nonetheless to determine the PROBABILITY > of BLACK having a forced win from the opening position? > (The same goes for a forced DRAW or for a forced WHITE win.) I don't know what this question means. Either black has a forced win or black doesn't. The probability is either 1 or 0.
anw@nott-cs.UUCP (03/26/86)
In article <912@whuxlm.UUCP> dim@whuxlm.UUCP writes: > 1. Since there is no way we will ever be able to fully analyze > chess, is it possible nonetheless to determine the PROBABILITY > of BLACK having a forced win from the opening position? > (The same goes for a forced DRAW or for a forced WHITE win.) ... If your move evaluation routine returned whatever it felt was some measure of this probability for leaf nodes, then of course these values could be backed up the tree. It's doubtful whether the result would have any practical value, however. I don't altogether share your pessimism about "no way ever ..."; there is no extant satisfactory calculation of how many positions we NEED to analyse-- pruning can be very drastic once a position is a clear win, which soon happens if one side strays too far from the best moves. Eg, if White is winning, only ONE move needs to be considered in each "White to move" position, and most games will be very short. Some will be very long, but good use of transposition tables could make a huge improvement in the analysis. The problem is a few orders of magnitude beyond present-day calculation, but "never" is rather a long time. > 2. Can anyone find a symmetric position (like the opening position) > where it is WHITE to move but BLACK has a forced win? In > other words, are there any symmetric zugzwangs for WHITE? > (I'm sure there must be some real simple position...) ... The simplest mutual zugzwang is typified by W: Kf5,Pe4; B: Kd4,Pe5, which has a pleasing symmetry, but not the one you ask for. The simplest such position is typified by W: Kg1,Pf6,Ph6; B: similar. > Dave McCooey > AT&T Bell Labs, Whippany > ihnp4!whuxlk!dim -- Andy Walker, Maths Dept, Nottingham Univ.
dim@whuxlm.UUCP (McCooey David I) (03/26/86)
> > 1. Since there is no way we will ever be able to fully analyze > > chess, is it possible nonetheless to determine the PROBABILITY > > of BLACK having a forced win from the opening position? > > (The same goes for a forced DRAW or for a forced WHITE win.) > > I don't know what this question means. Either black has a forced > win or black doesn't. The probability is either 1 or 0. I agree, but we will (probably) never know which it is. I am interested in the following issue: Say we restrict ourselves to the class of chess positions where: 1. All 32 pieces are on the board 2. The position is symmetric 3. Each side is 'set up' on its own first two ranks 4. It is WHITE's move or some similar class of positions. The point is that we want the opening position to be a member of this class. Now, if we had some oracle which would tell us who had a forced win (or draw) in each position in this class, we could calculate a PROBABILITY of BLACK having a forced win for a RANDOMLY chosen position from this class. (i.e. before we choose the position, what the probability is of it being a BLACK win.) This would give us grounds to make a guess at the probability of BLACK having a forced win in the opening position. This is an attempt to clarify the problem and not an attempt at a solution because clearly the probability mentioned above depends on the class we choose, and, moreover, we do not have an oracle. Another way to look at it is this: Say we had an oracle that knew the right answer (yes or no). What would be "fair odds" for it to give someone who did not know the answer?
kwh@bentley.UUCP (03/28/86)
In article <915@whuxlm.UUCP> whuxlm!dim (McCooey David I) writes: >> > 1. Since there is no way we will ever be able to fully analyze >> > chess, is it possible nonetheless to determine the PROBABILITY >> > of BLACK having a forced win from the opening position? >> > (The same goes for a forced DRAW or for a forced WHITE win.) > Another way to look at it is this: Say we had an oracle that knew > the right answer (yes or no). What would be "fair odds" for it > to give someone who did not know the answer? I consider it virtually certain that chess is a draw under rational play: Just look at the Karpov-Kasparov games! (You want figures? OK, I'd place the probability of a win for White at about 1.0E-5, and for Black around 1.0E-9.) I think this is a serious problem with the game. Two extremely good players will tend to have a string of drawn games until exhaustion takes over to determine a winner. A player who is leading in the last round of a tournament can "play for a draw" to try to retain the lead. This is not an unavoidable problem. There are other games (I'm talking two-player with perfect information) in which it is NOT POSSIBLE to have a draw, e.g. the game of hex. I think chess would be more interesting if it were in this category. Here's my question for the net. How could chess be modified to reduce or eliminate the drawn games, without presenting an unfair advantage to one player? (Thus no fair saying "draws are a win for black", etc.) Karl W. Z. Heuer (ihnp4!bentley!kwh), The Walking Lint