pmm@acsu.buffalo.edu (patrick m mullhaupt) (03/05/91)
Recently a friend of mine claimed that it had been *proven* through game theory that chess was a win for white. I find this very hard to believe and would appreciate any references or comments on the topic. - Patrick Mullhaupt pmm@acsu.buffalo.edu
jgk@osc.COM (Joe Keane) (03/07/91)
In article <63149@eerie.acsu.Buffalo.EDU> pmm@acsu.buffalo.edu (patrick m mullhaupt) writes: > Recently a friend of mine claimed that it had been *proven* >through game theory that chess was a win for white. I find this very >hard to believe and would appreciate any references or comments on the >topic. Your friend is confused. It's been proven for games like Hex, where making a move can't hurt you. Clearly this does not apply to chess. It's close to feasible to determine who wins in Othello by exhaustive search, if you're smart about it. The same for chess is way out of reach.
fawcett@unix1.cs.umass.edu (Tom Fawcett) (03/07/91)
In article <4657@osc.COM> jgk@osc.COM (Joe Keane) writes: > >It's close to >feasible to determine who wins in Othello by exhaustive search, if you're >smart about it. That's news to me. Do you have a reference, or an explanation? The search space of Othello contains approximately 10^50 nodes. The programs I've seen do endgame search 16 moves from the end; I'd be willing to believe that that could be pushed back to 20 or 25. Since there are ~60 moves, that still leaves a sizeable beginning- and middle-game, much as in chess. And isn't the phrase "exhaustive search, if you're smart about it" a bit of a contradiction? -Tom Fawcett UMass/Amherst
graham@maths.su.oz.au (Graham Matthews) (03/08/91)
patrick m mullhaupt) writes: > Recently a friend of mine claimed that it had been *proven* >through game theory that chess was a win for white. I find this very >hard to believe and would appreciate any references or comments on the >topic. Joe Keane in reply: >Your friend is confused. It's been proven for games like Hex, where making a >move can't hurt you. Clearly this does not apply to chess. It's close to >feasible to determine who wins in Othello by exhaustive search, if you're >smart about it. The same for chess is way out of reach. But perhaps the point is that you do not need to search to find out whether the game of chess is always a win for white. For example an endgame position such as king and knight against king - you do not search this all the way to the draw, you recognise this without searching as a draw. Perhaps there are other more encompassing rules like this that reduce or eliminate the search required. graham -- Graham Matthews Pure Mathematics, University of Sydney Internet: graham@maths.su.oz.au
zane@ddsw1.MCS.COM (Sameer Parekh) (03/14/91)
>In article <63149@eerie.acsu.Buffalo.EDU> pmm@acsu.buffalo.edu (patrick m >mullhaupt) writes: >> Recently a friend of mine claimed that it had been *proven* >>through game theory that chess was a win for white. I find this very >>hard to believe and would appreciate any references or comments on the >>topic. I think it would be possible to prove given a massive computer using a recursive search, but I don't think such a computer exists. (BTW: Did the name for Deep Thought come from the Douglas Adams book?) -- zane@ddsw1.MCS.COM
velasco@beowulf.ucsd.edu (Gabriel Velasco) (03/14/91)
zane@ddsw1.MCS.COM (Sameer Parekh) writes: >>In article <63149@eerie.acsu.Buffalo.EDU> pmm@acsu.buffalo.edu (patrick m >>mullhaupt) writes: >>> Recently a friend of mine claimed that it had been *proven* >>>through game theory that chess was a win for white. I find this very >>>hard to believe and would appreciate any references or comments on the >>>topic. > I think it would be possible to prove given a massive >computer using a recursive search, but I don't think such a computer >exists. It may be provable using game theory, but to prove it by using a computer would require an exhaustive state-space search. I can't remember where I heard this, but someone came up with a theoretical limit to the number of computations per second possible per gram of matter. They showed that if the entire mass of the Earth were converted into computing material that could compute at this theoretical limit it would take several hundreds of thousands of years to do an exhaustive state-space search of a chess game. My mind may have exaggerated this memory, but I think it correct. Maybe someone out there knows what I'm refering to. -- ________________________________________________ <>___, / / | ... and he called out and said, "Gabriel, give | /___/ __ / _ __ ' _ / | this man an understanding of the vision." | /\__/\(_/\/__)\/ (_/_(/_/|_ |_______________________________________Dan_8:16_|
cs225ju@ux1.cso.uiuc.edu) (Matt Pavlik ;) (03/18/91)
The possible combinations are something like 10 ^ 120 for chess. Matt
forbis@milton.u.washington.edu (Gary Forbis) (03/18/91)
In article <1991Mar18.045610.2977@ux1.cso.uiuc.edu> cs225ju@ux1.cso.uiuc.edu) (Matt Pavlik ;) writes: >The possible combinations are something like 10 ^ 120 for chess. I wonder if a better figure could be obtained by looking at average number of moves from usual positions within a game raised to the average number of moves in a game. It seem to me that by eliminating duplicate positions and symetrical position the number of moves tested could be substantially reduced. In fact, not every game must be considered but merely the ones whose positions are forced mate for one side or the other or are unavoidably a draw. Would every position be encountered in the course of playing what were considered optimal games using a database of positions encountered within such games which are forced mate? --gary forbis@u.washington.edu
cs225ju@ux1.cso.uiuc.edu) (Matt Pavlik ;) (03/19/91)
In article <18585@milton.u.washington.edu> forbis@milton.u.washington.edu (Gary Forbis) writes: >In fact, not every game must be considered but merely the ones whose positions >are forced mate for one side or the other or are unavoidably a draw. Would >every position be encountered in the course of playing what were considered >optimal games using a database of positions encountered within such games >which are forced mate? I got that number from a AI book and a few other books also had that number, Im certainly no expert, as I havent even had an AI course yet and I agree with what you say, but I think the problem is: In any game it's always possible to end up in any given "legal" board position. In order to make sure this position doesn't lead to some other outcome, all possibilities must be checked. ( I think the original question asked if white should always be able to win. ) How does the computer know what positions are going to lead to forced mate if it hasnt already checked all the posibilities? Does this make any sense? Matt
minsky@media-lab.MEDIA.MIT.EDU (Marvin Minsky) (03/19/91)
I dimly recall that the 10 ^ 120 number of chess game estimate was in Claude Shannon's original chess paper, and that it was based on estimate about 30 possible moves per position and some average length of game. I can't find the paper now. Wasn't there something about that in "Automata Studies" (ed. McCarthy and Shannon)?
epstein@sunc4.cs.uiuc.edu (Milt Epstein) (03/19/91)
In <1991Mar18.184332.12001@ux1.cso.uiuc.edu> cs225ju@ux1.cso.uiuc.edu (Matt Pavlik ;)) writes: >In article <18585@milton.u.washington.edu> forbis@milton.u.washington.edu (Gary Forbis) writes: > >>In fact, not every game must be considered but merely the ones whose positions >>are forced mate for one side or the other or are unavoidably a draw. Would >>every position be encountered in the course of playing what were considered >>optimal games using a database of positions encountered within such games >>which are forced mate? > >I got that number from a AI book and a few other books also had that number, >Im certainly no expert, as I havent even had an AI course yet and I agree >with what you say, but I think the problem is: > >In any game it's always possible to end up in any given "legal" board >position. In order to make sure this position doesn't lead to some other >outcome, all possibilities must be checked. ( I think the original question >asked if white should always be able to win. ) >How does the computer know what positions are going to lead to forced >mate if it hasnt already checked all the posibilities? > >Does this make any sense? I would say yes and no. However, it isn't necessarily the case that all possibilities must be checked in order to (in a game-theoretic sense) say that "chess is a win for white". Let's use tic-tac-toe as an example. Say I start to analyze the game, and I notice that if the first person goes in the middle, the worst he can ever to is draw. Then I can say, in a game-theoretic sense, that the person going first can't lose. However, I didn't have to look at all possible moves. (This example would be more convincing if I could think of a game that was guaranteed a win for the player that moved first -- PROVIDED THEY MAKE THE RIGHT MOVE(S)). The difference is -- in order to make a theoretical claim like "chess is a win for white", if you happen to know (or luck onto) the right moves, you may be able to prove it without looking at all possibilities. Beyond this theoretical distinction, chess is still a very complex game and just because you may not need to explore all possibilities doesn't mean you don't have to explore a hell-of-a-lot-of possibilities, and I have no idea if this has been done. -- Milt Epstein Department of Computer Science University of Illinois epstein@cs.uiuc.edu
jadam@cs.tamu.edu (James P Adam) (03/20/91)
>In any game it's always possible to end up in any given "legal" board >position. In order to make sure this position doesn't lead to some other >outcome, all possibilities must be checked. ( I think the original question >asked if white should always be able to win. ) >How does the computer know what positions are going to lead to forced >mate if it hasnt already checked all the posibilities? There is a method known as Minimax, which is used to build a tree of possible moves, given a "starting state." A move is made, and the resulting situation is weighted based on its advantages for "our" side. If we are looking at a move that "we" will make, we always try to go for the move that results in the highest value (max) next state. If we are looking at a move that "they" will make, we always pick the best move for them (i.e., assume they know what they are doing), thus producing the "min"). Looking ahead a certain number of moves (a.k.a. "plies"), we can choose the best move for us to make now based on the best value state that we have located later in the tree. Still, even looking ahead 2-3 plies in chess--if done exhaustively-- would be a monumental task. (Figure a couple of hours of processing time, minimum, on a pretty quick piece of gear.) So it is necessary to have some means of culling out moves. How? That's the trick, but it really means building your weighting system well. It needs to know the difference (in chess) between a lost-piece-gambit that results in superior positional power && simply a lost piece. (Etc., etc., etc.) Pruning the tree of possible decisions IS necessary, however, and it is done even in the "world-champion" computers that have specialized hardware used only for playing chess. This method of pruning, by the way, is referred to as "alpha-beta" pruning. It's an algorithmic approach that certainly has plenty of specific applications in chess programming. Jim
jlg@cochiti.lanl.gov (Jim Giles) (03/20/91)
In article <13478@helios.TAMU.EDU>, jadam@cs.tamu.edu (James P Adam) writes: |> [...] It needs to know |> the difference (in chess) between a lost-piece-gambit that results in |> superior positional power && simply a lost piece. (Etc., etc., etc.) |> [...] |> This method of pruning, by the way, is referred to as "alpha-beta" |> pruning. It's an algorithmic approach that certainly has plenty of |> specific applications in chess programming. This description is not true. Alpha-beta uses the same evaluation function as the ordinary minimax search. Furthermore, it gets the _same_ result as the corresponding minimax search would. To see how, consider a game where each player always has three options and you're going to search three plies deep: p1: p11: p111: p112: p113: p12: p121: p122: p123: p13: p131: p132: p133: ... Here the numbers after the colons are the value assigned to the position by the evaluation function. Note, I haven't filled in these values - that's the job of the search! At each step, player one would pick the best (max) of the pn or pnnn positions and player two would pick the worst (min - all numbers from player one's point of view). The search goes as follows: traverse the tree depth first and evaluate the leaf p111. Say that this value is zero. Continue depth first evaluating p112 and p113: with values (say) of -10 and +10 respectively. Now back up the max of these to p11 - player one clearly prefers +10 and the third ply is his turn. So p11 is +10. Now, continue the search down the p12 arm. Say the value of p121 is +20! This means that p12 will be at least +20 since no matter what p122 and p123 are, unless they are eve larger than +20, player one will always select p121. _BUT_ since ply two is the second player's turn, and he wants the minimum score, you _already_know_ that player two will _not_ pick p12. So, you don't have to evaluate p122 and p123 at all. This is the gist of alpha-beta pruning. The final table(with * for branches not evaluated) may look like this: p1: +10 p11: +10 p111: 0 p112: -10 p113: +10 p12: +20 (or more) alpha is +10 p121: +20 p122: * p123: * p13: +12 (or more) alpha is still +10 p131: +3 p132: +12 p133: * p2: -2 (or less) beta is +10 p21: -2 p211: -5 p212: -20 p213: -2 p22: * p221: * p222: * p223: * p23: * p231: * p232: * p233: * p3: -10 (or less) beta is still +10 p31: -10 p311: -10 p312: -12 p313: -15 p32: * p321: * p322: * p323: * p33: * p331: * p332: * p333: * Note that at p2 and p3, pruning was applied higher up than the bottom level. The term alpha-beta refers to the fact that you keep track of the highest score that's plausible to be backed up to the next level (the alpha) as well as the lowest plausible score (the beta). Any even ply node which has a descendent higher than the current alpha is not worth pursuing further. Any odd ply node with a descendent less than the current beta is also not worth further study. I have noted the alphas and betas on the right in the table. I apologise for the length of this post, but I wanted to post the whole table so that people could verify for themselves that the backed up values are valid no matter what the * positions evaluate to. Obviously, in this game, player one will pick move p1, then player two will pick p11 and player one will then pick p113. This is no accident - alpha-beta produces more cutoffs if the most viable moves at each level are examined first. J. Giles
zane@ddsw1.MCS.COM (Sameer Parekh) (03/23/91)
In article <18585@milton.u.washington.edu> forbis@milton.u.washington.edu (Gary Forbis) writes: >In article <1991Mar18.045610.2977@ux1.cso.uiuc.edu> cs225ju@ux1.cso.uiuc.edu) (Matt Pavlik ;) writes: >>The possible combinations are something like 10 ^ 120 for chess. > >I wonder if a better figure could be obtained by looking at average number >of moves from usual positions within a game raised to the average number of >moves in a game. It seem to me that by eliminating duplicate positions and >symetrical position the number of moves tested could be substantially reduced. >In fact, not every game must be considered but merely the ones whose positions >are forced mate for one side or the other or are unavoidably a draw. Would >every position be encountered in the course of playing what were considered >optimal games using a database of positions encountered within such games >which are forced mate? > >--gary forbis@u.washington.edu Interesting idea. . .would it be possible to have all the forced mate results computed and then to work backwards? (Even if processing power isn't within our current abilities.) -- The Ravings of the Insane Maniac Sameer Parekh -- zane@ddsw1.MCS.COM