#!/usr/bin/python
# Forum Romanum with simple computer players, AI version 3
# Written in 2009 by Nick Fankhauser

class forum_obj:
 """Forum Romanum settings and data"""
 def init(self):
  self.board=[] # stones on the board
  self.areas=[] # areas on the board
  self.scores={}
  self.turn=1
  self.ties={'x' : [], 'y' : [], 'a' : [], 'd1' : [], 'd2' : []} # line that have ties
  for p in range(1,self.players+1): self.scores[p]=0
  self.done={'x' : [], 'y' : [], 'a' : [], 'd1' : [], 'd2' : []} # 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,2):
  for j in range(0,4): areas[i][j]=2
 for i in range(size-2,size):
  for j in range(size-4,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 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(forum,cd,ps,win):
 if not cd: return ps,False,False # next line, if 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,True
 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,False

def score_line(access_function,key,forum,sp=False):
 ps={}
 spr=False 
 for i in range(forum.size): # for all x or y lines
  if i in forum.done[key] and not sp: 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 and not sp: # no stone anywhere -> line not finished -> no score yet
    cd={} # no counts -> skips to next line
    break # leave stone loop
   if p: cd[p]+=1 # add that stone to the player-stone counter
   if sp:
    if access_function( {1: {2 : (i,j)}, 2: {1 : (j,i)} }, 1, 2)==sp: spr=True
  if spr: 
   if i in forum.done[key]: return False
   return cd
  ps,ok,tie=judge(forum,cd,ps,forum.size)
  if tie and not sp: forum.ties[key].append(i) # mark that line as tie
  if ok and not sp: forum.done[key].append(i) # mark that line as done
 if sp: return False
 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,sp=False):
 ps={}
 spr=False
 for a in range(1,forum.max_area+1): # for all areas
  if a in forum.done['a'] and not sp: 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 and not sp: # no stone anywhere -> line not finished -> no score yet
    cd={} # no counts -> skips to next area
    break # leave stone loop
   if p: cd[p]+=1 # add that stone to the player-stone counter
   if sp:
    if (i,j)==sp: spr=True
  if spr: 
   if a in forum.done['a']: return False,0
   return cd,a
  ps,ok,tie=judge(forum,cd,ps,len(apl))
  if tie and not sp: forum.ties['a'].append(a) # mark that area as tie
  if ok and not sp: forum.done['a'].append(a) # mark that area as done
 if sp: return False,0
 return ps

def score_diagonal(access_function,key,forum,sp=False):
 ps={}
 spr=False
 if 1 in forum.done[key] and not sp: return {}
 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,j) # get the stone on x or y line
  if not p and not sp: # no stone anywhere -> line not finished -> no score yet
   cd={} # no counts -> skip  for x in range(forum.size):
   break # leave stone loop
  if p: cd[p]+=1 # add that stone to the player-stone counter
  if sp:
   if key=='d1': 
    if (j,j)==sp: spr=True
   if key=='d2': 
    if (forum.size-j-1,j)==sp: spr=True
 if spr: 
  if 1 in forum.done[key]: return False
  return cd
 if sp: return False
 ps,ok,tie=judge(forum,cd,ps,forum.size)
 if tie and not sp: forum.ties[key].append(1) # mark that area as tie
 if ok: forum.done[key].append(1) # mark that line as done
 return ps

def score(forum):
 ps={}
 forum.ties={'x' : [], 'y' : [], 'a' : [], 'd1' : [], 'd2' : []} # line that have ties
 ps1=score_line(lambda b,x,y : b[x][y],'x',forum)
 ps2=score_line(lambda b,x,y : b[y][x],'y',forum)
 ps3=score_areas(forum)
 ps4=score_diagonal(lambda b,x : b[x][x],'d1',forum)
 ps5=score_diagonal(lambda b,x : b[forum.size-x-1][x],'d2',forum)
 for p in range(1,forum.players+1): 
  ps[p]=0
  for pi in [ps1,ps2,ps3,ps4,ps5]:
   if pi.has_key(p): ps[p]+=pi[p]
 for i in range(1,forum.players+1): forum.scores[i]+=ps[i]

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 finished(forum):
 lx=len(forum.done['x']) + len(forum.ties['x'])
 ly=len(forum.done['y']) + len(forum.ties['y'])
 la=len(forum.done['a']) + len(forum.ties['a'])
 ld1=len(forum.done['d1']) + len(forum.ties['d1'])
 ld2=len(forum.done['d2']) + len(forum.ties['d2'])
 return lx+ly+la+ld1+ld2 == 2*forum.size + forum.max_area + 2

def gradient_rect(sxy,color_name):
 import Image,ImageColor,math
 col_hex=ImageColor.colormap[color_name]
 if isinstance(col_hex,tuple): fill=col_hex
 else: fill=ImageColor.getrgb(col_hex)
 im1=Image.new('RGB',sxy,(255,255,255))
 for x in range(sxy[0]):
  for y in range(sxy[1]):
   rpos=math.sqrt((sxy[0]/2-x)**2+(sxy[1]/2-y)**2)
   r=(sxy[0]/2+sxy[1]/2)/2
   faktor=(r-rpos)/r/2+0.5
   color=fill[0]*faktor,fill[1]*faktor,fill[2]*faktor
   im1.putpixel((x,y),color)
 return im1

def create_png(forum,turn,player,winner=False,no_save=False):
 import Image,ImageDraw,ImageFont,ImageColor,sys
 size=forum.size*60
 bgcol=(0,0,0)
 if sys.version.find('Gentoo')>-1: mainFont='/usr/share/fonts/corefonts/arialbd.ttf'
 else: mainFont='/usr/share/fonts/truetype/msttcorefonts/Arial_Bold.ttf'
 fontsize=size/25
 arial=ImageFont.truetype(mainFont,fontsize)
 colours=['black','red','blue','green','magenta'] + ImageColor.colormap.keys()
 im=Image.new('RGB',(size+size/2,size+25),bgcol)
 draw = ImageDraw.Draw(im)
 tick=size/forum.size
 stone_size=tick/2,tick/2
 stones={}
 for i in range(1,forum.players+1): 
  stones[i]=gradient_rect(stone_size,colours[i])
 for i in range(0,size,tick):
  draw.line((0,i,size,i),fill='lightgray')
  draw.line((i,0,i,size),fill='lightgray')
 for x in range(forum.size):
  for y in range(forum.size):
   col=colours[forum.areas[x][y]+25]
   if forum.areas[x][y] in forum.done['a']: col='black'
   pos1=x*tick+1, y*tick+1, x*tick+tick-1, y*tick+tick-1
   draw.rectangle(pos1,fill=col)
   if not forum.board[x][y]: continue
   pos2=x*tick+tick/4, y*tick+tick/4+1
   im.paste(stones[forum.board[x][y]],pos2)
 for p in forum.done['x']:
  draw.text((p*tick+tick/2-fontsize/3,size-2),'^',font=arial,fill='gold')
 for p in forum.done['y']:
  draw.text((size,p*tick+tick/2-fontsize/2,),'<',font=arial,fill='gold')
 tx='Turn %d, Player %d' % (turn,player)
 draw.text((size+25,10),tx,fill='white',font=arial)
 for p in range(1,forum.players+1):
  draw.text((size+25,size/10+size/15*p),'Player %d: %d' % (p,forum.scores[p]),fill=colours[p],font=arial)
 if turn<8: draw.text((size+10,size-20),'Placement Phase',font=arial,fill='white')
 if 1 in forum.done['d1']: draw.text((size,size-4),'X',font=arial,fill='gold')
 if 1 in forum.done['d2']: draw.text((size,0),'X',font=arial,fill='gold')
 if winner: draw.text((size+25,size-50),'Winner: Player %d' % winner,fill=colours[winner],font=arial)
 if no_save:
  import StringIO
  out=StringIO.StringIO()
  im.save(out,"PNG")
  return out.getvalue()
 im.save('turn%04d_player%d.png' % (turn,player))

def weight(cd,p,mx,players):
 if not cd: return 0 # area already scored (done)
 vals=cd.values() # all count for that area
 empty=mx-sum(vals) # empty fields in that area
 if empty==mx: return mx/2.0 # empty area is better than nothing
 if cd[p]>=empty: return mx-1 # already majority!
 if cd[p]==max(vals) and sum(vals) and empty==1: return mx # chance to win! 
 if empty<max(vals)-cd[p]+1: return 0 # no chance to win
 if cd[p]==max(vals) and sum(vals) and empty>players: return mx/2.0 # chance to win next turn maybe
 return float(mx)/float(mx-empty) # some chance to win later

def area_size(forum,a):
 cnt=0
 for x in range(forum.size):
  for y in range(forum.size):
   if forum.areas[x][y]==a: cnt+=1
 return cnt

def pos_val(forum,p,xy):
 pv=0
 cd1=score_line(lambda b,x,y : b[x][y],'x',forum,sp=xy)
 pv+=weight(cd1,p,forum.size,forum.players)
 cd2=score_line(lambda b,x,y : b[y][x],'y',forum,sp=xy)
 pv+=weight(cd2,p,forum.size,forum.players)
 cd3,a=score_areas(forum,sp=xy)
 pv+=weight(cd3,p,area_size(forum,a),forum.players)
 cd4=score_diagonal(lambda b,x : b[x][x],'d1',forum,sp=xy)
 pv+=weight(cd4,p,forum.size,forum.players)
 cd5=score_diagonal(lambda b,x : b[forum.size-x-1][x],'d2',forum,sp=xy)
 pv+=weight(cd5,p,forum.size,forum.players)
 return pv

def place(forum,p):
 opt1=[]
 for x in range(forum.size):
  for y in range(forum.size):
   if forum.board[x][y]: continue
   pv=pos_val(forum,p,(x,y))
   opt1.append((pv,(x,y)))
 opt1.sort()
 return list(opt1[-1][1])

def randpop(seq):
 import random
 return seq.pop(random.randrange(len(seq)))

def think(forum,p):
 opt1=[]
 opt2=[]
 for s in range(forum.stones):
  sxy=get_stone(forum,p,s)
  pv=pos_val(forum,p,sxy)
  opt1.append((pv,sxy))
 opt1.sort()
 mn=opt1[0][0]
 opt1m=map(lambda x:x[1],filter(lambda y:y[0]==mn,opt1))
 rt=list(randpop(opt1m))
 for x in range(forum.size):
  for y in range(forum.size):
   if forum.board[x][y]: continue
   if (x,y)==tuple(rt): continue
   pv=pos_val(forum,p,(x,y))
   opt2.append((pv,(x,y)))
 opt2.sort()
 mx=opt2[-1][0]
 opt2m=map(lambda x:x[1],filter(lambda y:y[0]==mx,opt2))
 rt+=list(randpop(opt2m))
 return rt

def random_move(forum,p,place=False):
 import random
 rl=[]
 if not place:
  x1=int(random.random()*forum.size)
  y1=int(random.random()*forum.size)
  while forum.board[x1][y1]!=p: 
   x1=int(random.random()*forum.size)
   y1=int(random.random()*forum.size)
  rl+=[x1,y1]
 x2=int(random.random()*forum.size)
 y2=int(random.random()*forum.size)
 while forum.board[x2][y2]: 
  x2=int(random.random()*forum.size)
  y2=int(random.random()*forum.size)
 rl+=[x2,y2]
 return rl

def autoplay_loop():
 forum=forum_obj() # create instance of the forum object
 forum.size=7
 forum.stones=7
 forum.players=4
 forum.init()
 # Placement Phase
 for s in range(forum.stones):
  for p in range(1,forum.players+1):
   print 'Turn %d, Player %d: %s' % (forum.turn,p,forum.done)
   x,y=place(forum,p)
   forum.board[x][y]=p
   score(forum)
   create_png(forum,forum.turn,p)
  forum.turn+=1
 # Movement Phase
 running=True
 while running:
  for p in range(1,forum.players+1):
   print 'Turn %d, Player %d: %s' % (forum.turn,p,forum.done)
   x1,y1,x2,y2=think(forum,p)
   forum.board[x1][y1]=0
   forum.board[x2][y2]=p
   score(forum)
   create_png(forum,forum.turn,p)
   if finished(forum):
    running=False
    break
  forum.turn+=1
 winner=ValueSort(forum.scores,rev=True)[0][0]
 create_png(forum,forum.turn,p,winner=winner)
 return 'Player %d wins!' % winner

if __name__=="__main__": print autoplay_loop()