//TicTacToe 1.0 Copyright (c) 1999 Michael Niedermayer

/**
 * @author Michael Niedermayer
 */
class State
	{
	private static final int [] POW3= {1, 3, 9, 27, 81, 243, 729, 2187, 6561};
	private static final boolean DO_RANDOMIZE= true;
	private static final double EPSILON= 1E-10;
	private boolean [][] linePosArray= new boolean[3][];
	protected static final int COMP= TicTacToe.COMP;
	protected static final int USER= TicTacToe.USER;
	protected static final int STATES= 19683;
	protected int current=0;
	protected int firstPlayer=-1;

	private class Score
		{
		int nTies[]= {0,0};
		int [][] nWins= {{0,0}, {0,0}};

		Score(int iState)
			{

			if( !isLegal(iState) )
				{
				return;
				}

			int w= getWinner(iState);
			if( w != -1 )
				{
				nWins[w^1][w]= 1;
				return;
				}
			if( isFull(iState) )
				{
				nTies[0]= 1;
				nTies[1]= 1;
				return;
				}

			for(int x=0; x<3; x++)
				{
				for(int y=0; y<3; y++)
					{
					if( get(x, y, iState) != -1) continue;
					try
						{
						int [] m= new int[2];
						m[0]= set(x, y, iState, 0);
						m[1]= set(x, y, iState, 1);
//						System.out.print( m[0] + " " + m[1] + " ");
						if(score[ m[0] ]==null) score[ m[0] ]= new Score( m[0] );
						if(score[ m[1] ]==null) score[ m[1] ]= new Score( m[1] );
//						System.out.print( "n ");

						nTies[USER]   += score[ m[USER] ].nTies[COMP];
						nWins[USER][0]+= score[ m[USER] ].nWins[COMP][0];
						nWins[USER][1]+= score[ m[USER] ].nWins[COMP][1];
						}
					catch( IllegalMoveException e )
						{
						throw new IllegalStateException();
						}
					}
				}

//			System.out.print("is"+iState+ " ");
			int bestMove= findBestMove(iState);
			int m;
			try
				{
				m= set(bestMove%3, bestMove/3, iState, COMP);
				}
			catch(IllegalMoveException e)
				{
				throw new IllegalStateException();
				}
				

			nTies[COMP]   += score[ m ].nTies[USER];
			nWins[COMP][0]+= score[ m ].nWins[USER][0];
			nWins[COMP][1]+= score[ m ].nWins[USER][1];


			}

		}
	private Score [] score= new Score[STATES];

	State(int firstPlayer)
		{
		for(int i=0; i<3; i++)
			{
	 		linePosArray[i]= new boolean[3];
			}

		setFirstPlayer(firstPlayer);
		score[0]= new Score(0);
		}

	private boolean isFull(int iState)
		{
		boolean b=true;

		for(int x=0; x<3; x++)
			{
			for(int y=0; y<3; y++)
				{
				if( get(x, y, iState)==-1 ) b= false;
				}
			}

		return b;
		}

	/**
	 * returns the player+1, who has all three fields on the line (x, y) - (x + dx*2, y + dy*2) 
	 * and sets the <code>linePosArray</code> to the line, or returns 0.
	 */
	private int getWinnerAt(int x, int y, int dx, int dy, int iState)
		{
		int winner= 
			  ( get(x,      y     , iState) + 1 )
			& ( get(x+dx  , y+dy  , iState) + 1 )
			& ( get(x+dx*2, y+dy*2, iState) + 1 );

		if(winner!=0 && winner!=3)
			{
			linePosArray[x     ][y     ]=
			linePosArray[x+dx  ][y+dy  ]=
			linePosArray[x+dx*2][y+dy*2]= true;
			}
		return winner;
		}

	/**
	 * Gets the player, who has 3 in a line and sets the <code>linePosArray</code> to it.
	 * @return The winner or -1 if no winner.
	 * @throws IllegalStateException if multiple winners
	 */
	private int getWinner(int iState)
		{
		for(int x=0; x<3; x++)
			{
			for(int y=0; y<3; y++)
				{
				linePosArray[x][y]= false;
				}
			}

		int r=
			( 
			  getWinnerAt(0, 0, 1, 0, iState)
			| getWinnerAt(0, 1, 1, 0, iState)
			| getWinnerAt(0, 2, 1, 0, iState)
			| getWinnerAt(0, 0, 0, 1, iState)
			| getWinnerAt(1, 0, 0, 1, iState)
			| getWinnerAt(2, 0, 0, 1, iState)
			| getWinnerAt(0, 0, 1, 1, iState)
			| getWinnerAt(2, 0,-1, 1, iState)
			) - 1;

		if(r==2) throw( new IllegalStateException() );

		return r;
		}

	private boolean isLegal(int iState)
		{
		int [] n= {0,0};

		for(int x=0; x<3; x++)
			{
			for(int y=0; y<3; y++)
				{
				int p=get(x, y, iState);
				if(p != -1) n[p]++;
				}
			}

		int diff= n[0] - n[1];
		if( diff<-1 || diff>1 ) return false;
		else 					return true;
		}

	/**
	 * Gets the player, who is on the Field (x, y), or -1 if the field is empty.
	 */
	private int get(int x, int y, int iState)
		{
		if(x<0 || x>2) throw new IllegalArgumentException();
		if(y<0 || y>2) throw new IllegalArgumentException();
		if(iState<0 || iState>=STATES) throw new IllegalArgumentException();
		return (iState / POW3[x+y*3] ) % 3 - 1; 
		}

	/**
	 * Sets the player for the Field (x, y).
	 * @throws IllegalMoveException if the field is not empty.
	 */
	private int set(int x, int y, int iState, int v)  throws IllegalMoveException
		{
		v++;
		if(x<0 || x>2) throw new IllegalArgumentException();
		if(y<0 || y>2) throw new IllegalArgumentException();
		if(v<1 || v>2) throw new IllegalArgumentException();
		if(iState<0 || iState>=STATES) throw new IllegalArgumentException();

		if( get(x, y, iState)!=-1 ) throw new IllegalMoveException();
		
		int p= POW3[x+y*3];
		return iState - (get(x, y, iState) + 1) * p + v*p;
		}

	/**
	 * Finds the Best Move for the Computer.
	 * @return x + y*3
	 * @throws IllegalArgumentException if no empty field left.
	 */
	private int findBestMove(int iState)
		{
		double bestQ= Double.NEGATIVE_INFINITY;
		int bestX=-1, bestY=-1;

		for(int x=0; x<3; x++)
			{
			for(int y=0; y<3; y++)
				{
				if( get(x,y, iState)!=-1 ) continue;
				int m=0;
				try
					{
					m=set(x, y, iState, COMP);
					}
				catch(IllegalMoveException e)
					{
					throw new IllegalStateException();
					}

				double q;

				if(score[m].nWins[ USER ][ USER ] > 0)	
					{
					q=    (double)( -score[m].nWins[ USER ][ USER ] )
						/ (double)(	  score[m].nTies[ USER ] 
									+ score[m].nWins[ USER ][ COMP ] + EPSILON);
					}
				else 
					{
					q=    (double)(score[m].nWins[ USER ][ COMP ])
						/ (double)(score[m].nTies[ USER ] + EPSILON);
					}

				if(DO_RANDOMIZE)
					{
						 if(q <= -0.9/EPSILON) q= -1.0/EPSILON;
					else if(q <   0.0        ) q= -1.0;
					else if(q <   0.9/EPSILON) q=  1.0;
					else 					   q=  1.0/EPSILON;

					q*= 1 + Math.random();
					}

				if(q>=bestQ)
					{
					bestQ= q;
					bestX= x;
					bestY= y;
					}
				}
			}

		if(bestX<0) throw new IllegalArgumentException( "No empty field left" );
		return bestX + bestY*3;
		}

	/**
	 * Gets the line on which one player has all three fields.
	 */
	public boolean [][] getLine()
		{
		getWinner(current);
		return linePosArray;
		}

	public void makeEmpty()
		{
		current=0;
		}

	public boolean isEnd() 
		{
		if( !isLegal(current) ) throw new IllegalStateException();

		if( isFull(current) ) return true;
		if( getWinner(current) != -1 ) return true;

		return false;
		}

	/**
	 * Gets the player, who is currently on the Field (x, y), or -1 if the field is empty.
	 */
	public int get(int x, int y)
		{
		return get(x, y, current);
		}

	/**
	 * Sets the player for the Field (x, y).
	 * @throws IllegalMoveException if the field is not empty.
	 */
	public void set(int x, int y, int v) throws IllegalMoveException
		{
		current= set(x, y, current, v);
		}

	public int getNTie(int nextPlayer)
		{
		return score[current].nTies[ nextPlayer ];
		}

	public int getNCOMPWin(int nextPlayer)
		{
		return score[current].nWins[ nextPlayer ][COMP];
		}

	public void makeMove()
		{
		int best= findBestMove(current);
		try
			{
			set(best%3, best/3, COMP);
			}
		catch(IllegalMoveException e)
			{
			throw new IllegalStateException();
			}
/*
		System.out.print(	  score[current].nTies[USER]+ " "
							+ score[current].nWins[USER][USER]+ " "
							+ score[current].nWins[USER][COMP]+ "\n");
*/
		}

	public void setFirstPlayer(int firstPlayer)
		{
		this.firstPlayer= firstPlayer;
		}

	}