kfl@speech2.cs.cmu.edu (Fu Lee) (12/08/86)
In article <3829@watmath.UUCP>, jsgray@watmath.UUCP (Jan Gray) writes: > If you guys want to write truly good Othello programs, you should use a > score function which includes a mobility component and **edge tables**. I agree. These are both very important. > > Now, how do you build an edge table, you ask? > .... > Here it is in pseudocode: > > for i = 0 to 3^8-1 > if #pieces[i] = 8 { Is this edge full? } > et[i] = 1000 * (#whites[i] - #blacks[i]) > for pieces = 7 to 0 > for i = 0 to 3^8-1 > if #pieces[i] = pieces > for each empty square on i > place black there, flip along edge if > possible and look up score in et[] > placw white there, flip along edge if > possible and look up score in et[] > et[i] = average of the above scores > The basic approach (taken from Rosenbloom's report) is very good, but the author omitted two important details, without which the edge table will be poor: (1) Averaging all possible moves is incorrect. Clearly, the probability of making any edge moves is not the same. For example, B B B W . . . . = Black can definitely move to 1, possibly to 2 1 2 3 4 and 3, and almost never to 4 (because it would mean that White is presenting Black a corner). It is necessary to consider the likelihood of moving to each empty square. (2) It is necessary to know whose move it is. For example, . B B B W W W . is extremely good for the side to move. > Once you put the edge > table into your score function you will *never* beat your program again. While it is true that the best Othello programs are probably better than the best humans, the above statement should not be taken seriously because: (1) Understanding of the edge is important to NOT LOSING the game, but it is mobility that makes an Othello program (or human player) good. Simply adding an edge table, no matter how good, will not make the program invincible. (2) I know many Othello players who are extremely good, and I know they can beat all but the best 3 or 4 programs in the world. Even I have beaten several programs that have good edge tables and understanding of mobility, and I am not even close to the average Othello-tournament-player. > There is an excellent CMU tech report by Paul Rosenblum on his Iago program > (around 82 or 83 I think). Check your library... Rosenbloom's article can be found in "A World-Championship-Level Othello Program", Artificial Intelligence, Vol. 19, No. 3, Nov. 1982. pp 279-319. It is a very good reference. A more recent reference on Othello is Lee and Mahajan, "BILL: A Table-Based, Knowledge-Intensive Othello Program", CMU tech report CMU-CS-86-141. It can be obtained by writing to the CMU CS Dept. I am sorry if this article is not entirely approapriate for the newsgroup, but I felt that I had to clarify some things. Kai-Fu Lee ARPANET: kfl@speech2.cs.cmu.edu