Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP Path: utzoo!utgpu!water!watmath!clyde!rutgers!mcnc!ece-csc!ncrcae!ncr-sd!hp-sdd!hplabs!ucbvax!ICST-CMR.ARPA!rbj From: rbj@ICST-CMR.ARPA.UUCP Newsgroups: comp.emacs Subject: Gomoku: a strategic board game for GNU Emacs. Message-ID: <8710011906.AA20385@icst-cmr.arpa.ARPA> Date: Thu, 1-Oct-87 15:06:51 EDT Article-I.D.: icst-cmr.8710011906.AA20385 Posted: Thu Oct 1 15:06:51 1987 Date-Received: Sat, 3-Oct-87 09:08:27 EDT Sender: daemon@ucbvax.BERKELEY.EDU Distribution: world Organization: The ARPA Internet Lines: 35 From: Dale Worley From what I've heard, the number of potential moves from any position in Go is so large that tree searching doesn't work. To be precise, the maximum search tree is bounded by the number 381! The board is 19 square, giving 381 choices for the first move, 380 for the second, ... and the last move is forced. I say bounded, because I have not accounted for illegal moves or ko's. Assuming a game is `pretty much over' after half of the stones have been played, leaves 200 or so moves per half move level search. In chess, there are rarely even 100 moves (altho that's still pretty hefty) available. At the beginning, there are 20. Even so, all possible moves are not usually generated; they usually prune off the useless or bad ones at higher levels. Oddly enough, good computer chess programs all use tree searching, but good human chess players don't. I wouldn't say that. We all think to ourselves, "I take, he takes, I take, he takes, I guess I've got to protect it again". It has also been said that experts think about the same number of moves ahead that average players do, they just don't see the bad moves. What is really needed is a way to prune the tree of bad or meaningless moves and focus the search on a particularly interesting section. Dale (Root Boy) Jim Cottrell National Bureau of Standards Flamer's Hotline: (301) 975-5688 Jesus is my POSTMASTER GENERAL..