#!/usr/bin/python
# Forum Romanum with simple computer players
import random,psyco,sys
psyco.full()

class forum_obj:
 """Forum Romanum settings and data"""
 size=7 # size of board
 players=4 # number of players
 stones=7 # number of stones per player
 think_depth=2
 def __init__(self):
  self.board=[] # stones on the board
  self.areas=[] # areas on the board
  self.scores={}
  for p in range(1,self.players+1): self.scores[p]=0
  self.done={'x' : [], 'y' : [], 'a' : []} # line that have already been filled
  for i in range(self.size): self.board.append([0]*self.size)
  for i in range(self.size): self.areas.append([0]*self.size)
  self.areas,self.max_area=fill_areas(self.areas,self.size)

def fill_areas(areas,size):
 m=size/2 # middle of board
 for i in range(m-1,m+2):
  for j in range(m-1,m+2): areas[i][j]=1
 for i in range(0,4):
  for j in range(0,2): areas[i][j]=2
 for i in range(size-4,size):
  for j in range(size-2,size): areas[i][j]=3
 a=4
 for i in range(size):
  for j in range(size):
   if areas[i][j]: continue
   c1=c2=0
   for x in range(3):
    for y in range(2):
     if i+x>=size or j+y>=size: c1+=1
     elif areas[i+x][j+y]: c1+=1
   for x in range(3):
    for y in range(2):
     if i+y>=size or j+x>=size: c2+=1
     elif areas[i+y][j+x]: c2+=1
   if c1 and c2: continue
   for x in range(3):
    for y in range(2): 
     if c1:
      if i+y>=size or j+x>=size: continue
      areas[i+y][j+x]=a
     else:
      if i+x>=size or j+y>=size: continue
      areas[i+x][j+y]=a
   a+=1
 return areas,a-1
  
def show(li):
 for l in li: 
  for i in l: print '%01d' % i,
  print

def ValueSort(d,rev=True):
 items = d.items()
 items = [(v, k) for (k, v) in items]
 items.sort()
 if rev: items.reverse() # so largest is first
 return [(k, v) for (v, k) in items]

def judge(cd,ps,win):
 if not cd: return ps,False # next line of not finished line
 cds=ValueSort(cd) # sort by number of stones
 wp=cds[0][0] # winning player
 wp_scr=cds[0][1] # winning player score
 wpl=map(lambda x: x[0],filter(lambda x : x[1]==wp_scr,cds)) # winning player list
 if len(wpl)>1: return ps,False
 ps[wp]=ps.get(wp,0)+win # add score for winning player
 lp=cds[-1][0] # losing player
 lp_scr=cds[-1][1] # losing player score
 lpl=map(lambda x: x[0],filter(lambda x : x[1]==lp_scr,cds)) # losing player list
 for p in lpl: # for all loosing players
  if len(lpl)==1: ps[p]=ps.get(p,0)-4 # -4 if just one losing player
  else: ps[p]=ps.get(p,0)-2 # -2 for all if more that one losing player
 return ps,True

def score_line(access_function,key,forum,commit):
 ps={}
 for i in range(forum.size): # for all x or y lines
  if i in forum.done[key]: continue # skip if already done
  cd={}	# player-stone counter
  for p in range(1,forum.players+1): cd[p]=0 # all players start at zero
  for j in range(forum.size): # for all stones of that line
   p=access_function(forum.board,i,j) # get the stone on x or y line
   if not p: # no stone anywhere -> line not finished -> no score yet
    cd={} # no counts -> skips to next line
    break # leave stone loop
   cd[p]+=1 # add that stone to the player-stone counter
  ps,ok=judge(cd,ps,forum.size)
  if ok and commit: forum.done[key].append(i) # mark that line as done
 return ps

def area_positions(areas,a):
 apl=[]
 for x in range(len(areas)):
  for y in range(len(areas)):
   if areas[x][y]==a: apl.append((x,y))
 return apl

def score_areas(forum,commit):
 ps={}
 for a in range(1,forum.max_area+1): # for all areas
  if a in forum.done['a']: continue # skip if already done
  cd={}	# player-stone counter
  for p in range(1,forum.players+1): cd[p]=0 # all players start at zero
  apl=area_positions(forum.areas,a)
  for i,j in apl: # for all stones of that area
   p=forum.board[i][j] # get the stone on x or y line
   if not p: # no stone anywhere -> line not finished -> no score yet
    cd={} # no counts -> skips to next area
    break # leave stone loop
   cd[p]+=1 # add that stone to the player-stone counter
  ps,ok=judge(cd,ps,len(apl))
  if ok and commit: forum.done['a'].append(a) # mark that line as done
 return ps

def score(forum,commit=True):
 ps={}
 ps1=score_line(lambda b,x,y : b[x][y],'x',forum,commit)
 ps2=score_line(lambda b,x,y : b[y][x],'y',forum,commit)
 ps3=score_areas(forum,commit)
 for p in range(1,forum.players+1): 
  ps[p]=0
  if ps1.has_key(p): ps[p]+=ps1[p]
  if ps2.has_key(p): ps[p]+=ps2[p]
  if ps3.has_key(p): ps[p]+=ps3[p]
 return ps

def get_stone(forum,p,i):
 n=0
 for x in range(forum.size):
  for y in range(forum.size):
   if forum.board[x][y]==p:
    if n==i: return x,y
    n+=1

def personal_gain(ps,p):
 my=ps.pop(p)
 psv=ps.values()
 avg=float(sum(psv))/float(len(psv))
 return float(my)-avg

def random_move(forum):
 x=int(random.random()*forum.size)
 y=int(random.random()*forum.size)
 while forum.board[x][y]: 
  x=int(random.random()*forum.size)
  y=int(random.random()*forum.size)
 return x,y

def possiblity_list(forum,p,prev=[]):
 rl=[]
 if len(prev)>=forum.think_depth: return []
 for s in range(forum.stones):
  sx,sy=get_stone(forum,p,s)
  for x in range(forum.size):
   for y in range(forum.size):
    if not forum.board[x][y]: 
     move=(sx,sy,x,y)
     if move in prev: continue
     rl.append(prev+[move])
     rl+=possiblity_list(forum,p,prev=prev+[move])
 return rl

def finished(forum):
 lx=len(forum.done['x'])
 ly=len(forum.done['y'])
 la=len(forum.done['a'])
 return lx+ly+la==2*forum.size+forum.max_area

def check_possiblities(forum,poss,p):
 max_pg=max_nb=0
 for n,koords in enumerate(poss):
  f=forum_obj()
  f.board = [list(row) for row in forum.board]
  f.done = dict( [(key,list(value)) for key,value in forum.done.items()] )
  sum_pg=0
  for sx,sy,px,py in koords:
   f.board[sx][sy]=0
   f.board[px][py]=p
   sum_pg+=personal_gain(score(f),p)
  if sum_pg>max_pg:
   max_pg=sum_pg
   max_nb=n
 return max_pg,max_nb

def create_png(forum,turn,player):
 import Image,ImageDraw,ImageFont,ImageColor
 size=320
 bgcol=(0,0,0)
 if sys.version.find('Gentoo')>-1: mainFont='/usr/share/fonts/corefonts/arial.ttf'
 else: mainFont='/usr/share/fonts/truetype/msttcorefonts/Arial_Bold.ttf'
 arial=ImageFont.truetype(mainFont,14)
 colours=['black','red','blue','green','magenta'] + ImageColor.colormap.keys()
 im=Image.new('RGB',(size+150,size+20),bgcol)
 draw = ImageDraw.Draw(im)
 tick=size/forum.size
 for i in range(0,size,tick):
  draw.line((0,i,size,i),fill='lightgray')
  draw.line((i,0,i,size),fill='lightgray')
 for p in forum.done['x']:
  draw.ellipse((p*tick+17,size-2,p*tick+27,size+8),fill='gold')
 for p in forum.done['y']:
  draw.ellipse((size-2,p*tick+17,size+8,p*tick+27),fill='gold')
 for x in range(forum.size):
  for y in range(forum.size):
   col='rgb(%d,211,211)' % (forum.areas[x][y]*20+100)
   draw.rectangle((x*tick-1,y*tick+1,x*tick+tick-1,y*tick+tick-1),fill=col)
   if not forum.board[x][y]: continue
   col=colours[forum.board[x][y]]
   draw.ellipse((x*tick+3,y*tick+3,x*tick+tick-2,y*tick+tick-2),fill=col)
 for a in forum.done['a']:
  for x in range(forum.size):
   for y in range(forum.size):
    if forum.areas[x][y]==a:
     draw.ellipse((x*tick,y*tick,x*tick+10,y*tick+10),fill='gold')
 tx='Turn %d, Player %d' % (turn,player)
 draw.text((size+10,10),tx,fill='white',font=arial)
 for p in range(1,forum.players+1):
  draw.text((size+10,10+20*p),'Player %d: %d' % (p,forum.scores[p]),fill=colours[p],font=arial)
 if turn<8: draw.text((size+10,size-20),'Random Placement',font=arial,fill='white')
 im.save('turn%04d_player%d.png' % (turn,player))

forum=forum_obj() # create instance of the forum object
turn=1
for s in range(forum.stones):
 for p in range(1,forum.players+1):
  x,y=random_move(forum)
  forum.board[x][y]=p
  show(forum.board)
  print
  create_png(forum,turn,p)
 turn+=1
while True:
 for p in range(1,forum.players+1):
  print 'turn',turn,'player',p,forum.done
  poss=possiblity_list(forum,p)
  pg,nb=check_possiblities(forum,poss,p)
  x1,y1,x2,y2=poss[nb][0]
  print '%d/%d -> %d/%d' % (x1,y1,x2,y2)
  forum.board[x1][y1]=0
  forum.board[x2][y2]=p
  ps=score(forum)
  for i in range(1,forum.players+1): forum.scores[i]+=ps[i]
  show(forum.board)
  create_png(forum,turn,p)
  print ', '.join(map(lambda x : 'Player %d: %d' % x,forum.scores.items()))
  if finished(forum): break 
 if finished(forum): break
 turn+=1