Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!swrinde!cs.utexas.edu!uwm.edu!linac,att!emory!wuarchive!m.cs.uiuc.edu!ibma0.cs.uiuc.edu!sunc4.cs.uiuc.edu!epstein From: epstein@sunc4.cs.uiuc.edu (Milt Epstein) Newsgroups: comp.ai Subject: Re: Chess question Message-ID: <27E55C52.404C@ibma0.cs.uiuc.edu> Date: 19 Mar 91 00:33:22 GMT References: <1991Mar18.045610.2977@ux1.cso.uiuc.edu> <18585@milton.u.washington.edu> <1991Mar18.184332.12001@ux1.cso.uiuc.edu> Sender: news@ibma0.cs.uiuc.edu Organization: University of Illinois at Urbana-Champaign Lines: 50 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