#### 4 Aug 2004 Bram»(Master)

Hex

Based on the hex board evaluation ideas I gave earlier, I've written a hex playing program. I found giving it a two-ply look-ahead got rid of the tendency to play new moves right next to old moves.

This program plays position surprisingly well, but still has some very obvious weaknesses. For example, it doesn't realize that bridges are fully connected.

Clearly some sort of hexy/six-style feedback from tactical calculations into positional evaluation is necessary to make this program play better. I think my approach is quite a bit more inherently flexible about ways of doing that than the circuit resistance approach which hexy and six use.

To use this code, create a hex board of the size you want, then use x() and o() to place pieces, and to have the computer place a piece use moveo(). The computer only plays O, which is trying to connect the top and bottom. Runs of length 1000 work reasonably well.

Note that although a two-ply look-ahead is substantially better than a one-ply look-ahead, a chess-style three-ply look-ahead would be of dubious value. A better approach would be to make the results of the move/counter-move pairs influence which positions are generated in the fill-in process.

```from random import randrange
from copy import deepcopy
def hexprint(myarray):
for i in xrange(len(myarray)):
print (' ' * (len(myarray) - 1 - i)) + ' '.join([str(myarray[x][i]) for x in xrange(len(myarray))])
print
class hexplayer:
def __init__(self, size):
self.size = size
self.states = [['.' for i in xrange(self.size)] for j in xrange(self.size)]
def o(self, x, y):
assert self.states[x-1][y-1] == '.'
self.states[x-1][y-1] = 'O'
hexprint(self.states)
def x(self, x, y):
assert self.states[x-1][y-1] == '.'
self.states[x-1][y-1] = 'X'
hexprint(self.states)
def findbest(self, values):
best = -1
bestx = None
besty = None
for i in xrange(self.size):
for j in xrange(self.size):
if values[i][j] > best and (self.states[i][j] == '.'):
best = values[i][j]
bestx = i
besty = j
return (bestx, besty)
def moveo(self, runs):
values2 = [[-1 for i in xrange(self.size)] for j in xrange(self.size)]
responses = [[None for i in xrange(self.size)] for j in xrange(self.size)]
for i in xrange(self.size):
for j in xrange(self.size):
if self.states[i][j] == '.':
self.states[i][j] = 'O'
values, wonx = self.evaluate(runs)
bestx, besty = self.findbest(values)
assert self.states[bestx][besty] == '.'
responses[i][j] = (bestx, besty)
values2[i][j] = runs - wonx - values[bestx][besty]
self.states[i][j] = '.'
bestx, besty = self.findbest(values2)
self.states[bestx][besty] = 'O'
hexprint(values2)
print float(values2[bestx][besty]) / runs
r1, r2 = responses[bestx][besty]
print r1+1, r2+1
hexprint(self.states)
def evaluate(self, runs):
wonx = 0
top = self.size - 1
values = [[0 for i in xrange(self.size)] for j in xrange(self.size)]
for run in xrange(runs):
myvalues = deepcopy(self.states)
for i in xrange(self.size):
for j in xrange(self.size):
if myvalues[i][j] == '.':
myvalues[i][j] = ('X', 'O')[randrange(2)]
visited = [[0 for i in xrange(self.size)] for j in xrange(self.size)]
def neigbors(x, y):
r = []
if y > 0:
r.append((x, y-1))
if x > 0:
r.append((x-1,y-1))
if x > 0:
r.append((x-1, y))
if x < top:
r.append((x+1, y))
if y < top:
r.append((x, y+1))
if x < top:
r.append((x+1, y+1))
return r
remaining = [(0, i) for i in xrange(self.size)]
while remaining:
x, y = remaining.pop()
if visited[x][y] != 0:
continue
if myvalues[x][y] != 'X':
continue
if x == top:
wonx += 1
break
visited[x][y] = 1
remaining.extend(neigbors(x, y))
else:
remaining = [(top, i) for i in xrange(self.size)]
while remaining:
x, y = remaining.pop()
if visited[x][y] != 0:
continue
if myvalues[x][y] != 'X':
continue
visited[x][y] = 2
remaining.extend(neigbors(x, y))
for i in xrange(self.size):
for j in xrange(self.size):
m = neigbors(i, j)
n = [visited[x][y] for (x, y) in m]
if (1 in n or i == 0) and (2 in n or i == top) and self.states[i][j] == '.':
values[i][j] += 1
return values, wonx
```