Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!lll-crg!rutgers!clyde!watmath!jsgray
From: jsgray@watmath.UUCP (Jan Gray)
Newsgroups: net.sources.games
Subject: Re: Othello Game in C with Lookahead
Message-ID: <3829@watmath.UUCP>
Date: Sun, 7-Dec-86 08:57:19 EST
Article-I.D.: watmath.3829
Posted: Sun Dec  7 08:57:19 1986
Date-Received: Sun, 7-Dec-86 21:08:57 EST
References: <1105@zen.BERKELEY.EDU>
Reply-To: jsgray@watmath.UUCP (Jan Gray)
Organization: U. of Waterloo, Ontario
Lines: 46
Keywords: othello, reversi, **edge tables**

If you guys want to write truly good Othello programs, you should use a
score function which includes a mobility component and **edge
tables**.  The idea is to precompute a score for each edge
configuration (3^8 of them) and then you can score the edge perfectly
with just a table lookup.

Now, how do you build an edge table, you ask?  One simple approach, which
makes an acceptable table, uses a variant of dynamic programming.  You
first score all the full edge configurations in some straightforward way
(say 1000 for each white piece, -1000 for each black piece).  Then you
score all the edge configurations with one empty square by placing
a black piece in the empty square, flipping pieces if possible, and
looking up the resulting score in the table (remember, you've already
scored the full edge configurations), and averaging that score with the
score for a similiar move for white into the empty square.  Continue,
scoring all the configurations with two, three, ... all empty squares.

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

There are variations, including iterative improvements, but even this
simple algorithm gives an edge table which plays very well; i.e. it knows
that BWWWWWW- is not a very good position for white.  Once you put the edge
table into your score function you will *never* beat your program again.

There is an excellent CMU tech report by Paul Rosenblum on his Iago program
(around 82 or 83 I think).  Check your library...

See you all at the 4th Annual University of Waterloo Computer Science Club
Open Computer Othello Tournament (UWCSCOCOT4 :-) (Nov. 1987).

Jan Gray   jsgray@watmath   University of Waterloo   519-885-5921

[USA NSA food: terrorist, cryptography, DES, drugs, CIA, secret, decode, foo]