/*
* kolko i krzyzyk
*
* @see	ox.java desk.java hqueue.java
* @version    3.1, 16.06.2003
* @autor	Zbigniew Lisiecki, zbyszek@evot.org
*		GNU Public Licence
*
*/
/******************************************************************
				the game playing kernel
*******************************************************************/

import java.lang.*;
import java.util.*;

public class desk {			// game position
	public static final byte empty		= 0,
							 white		= 1,	// kolko
							 black 		= 2,	// krzyzyk
							 lyellow	= 3,
							 dyellow	= 4,
							 red		= 5,
							 lila		= 6,
							 rwhite		= 7,	// white in red
							 rblack 	= 8;	// black in red
	public	static	final int	matval = 1024;	// value of mat
	public	static	boolean ttabon  = true;
	public	static	boolean presort = true;
	public	static	boolean showpresorted = false;
	public	static	boolean gpshowdepth   = false;
	public	static	boolean newmovesdebug = false;
	public	static	boolean must4debug    = false;
	public	static	boolean must3debug    = false;
	public	static	boolean computedebug  = false;
	public	static	int	xsize, ysize;		// copy from gpanel
	public	static	int	debugdepth = 2;
	public	static	int	maxwidth   = 128;	// maximal # moves in one ply
	public	static	int	maxdepth   = 3;		// in plys
	public	static	int	mmaxdepth  = 7;
	public	static	int	showndepth = 2;
	public	static	int	add3       = 24;
	public	static	int	stored, recalled;	// in/from TTable
	public	static	byte	answx, answy;
			static	byte	mbuf[][] = new byte[8 * maxwidth][2]; 
			static	byte	b[][] = new byte[64][2];
			static	int	depthv[] = new int[32];
			static	hqueue hq;
					int			eval = 0;
	public			byte		piece;
					byte		board[][];
					byte		newx, newy;
					byte fork3 = empty;
					byte free3 = empty; //used when forgotten where it is

	public desk() {
		board = new byte[xsize][ysize];
		for (byte i = 0; i < xsize; i++)
		for (byte j = 0; j < ysize; j++)
			board[i][j] = empty;
	}
	public desk(int xs, int ys) {
		xsize = xs;
		ysize = ys;
		board = new byte[xsize][ysize];
		for (byte i = 0; i < xsize; i++)
		for (byte j = 0; j < ysize; j++)
			board[i][j] = empty;
	}
	public desk(byte brd[][]) {
		board = new byte[xsize][ysize];
		for (byte i = 0; i < xsize; i++)
		for (byte j = 0; j < ysize; j++)
			if (brd[i][j] == white || brd[i][j] == black) {
				board[i][j] = brd[i][j];
			}
	}
	public desk(desk src) {
		board = new byte[xsize][ysize];
		for (byte i = 0; i < xsize; i++)
		for (byte j = 0; j < ysize; j++)
			if (src.board[i][j] == white || src.board[i][j] == black) {
				board[i][j] = src.board[i][j];
			}
		piece = src.piece;
	}

	/*
	* recursively compute the answere move - main computing routine
	* put the answere in answx/y
	* method: Alpha-Beta-Search, see http://www.xs4all.nl/verhelst
	* (alpha,beta) is a window in which the best value is searched for
	* (x,y) is a last oponent's move, (x1,y1) is my last move
	*/
	public int compute (int depth, int alpha, int beta,
		byte x, byte y, byte x1, byte y1)
	{
		if (depth == 0) {		// intialising
			stored = 0;
			recalled = 0;
			for (int i = 0; i < depthv.length; i++)
				depthv[i] = 0;
			/*
			* start new TTab for each new move, or for a newgame() ?
			*/
			System.gc();	// garbage collection
			hq = new hqueue (true);
		}
		int	k = 0;						// w with maximal value
		int	l = 0;
		byte	moves[][] = null;		// possible moves
		int	value, best = -Integer.MAX_VALUE;
		int depthadd = 0;
		int depthx = maxdepth;			// maxdepth copy

		if (computedebug && depth <= debugdepth) {
			System.out.print ("compute");
			for (int i = 0; i < depth; i++)
				System.out.print ("  ");
			System.out.print ("{ depth="  + depth +
                              " alpha=" + alpha +
                              " beta="  + beta +
                              " fork3="  + fork3);
			if (board[x][y] == white)
				System.out.println (" O(" + x+","+y+")");
			if (board[x][y] == black)
				System.out.println (" X(" + x+","+y+")");
		}
		if (gpshowdepth) {
			depthv[depth]++;
			String s = "";
			for (int i = 1; i < 8; i++)
				s = s + depthv[i] + "/";
            ox.tf[1].setText (s);
		}
		/*
		* check if there are already 5 in line
		*/
		if (inline (5, x, y) == true) {
			if (computedebug && depth <= debugdepth) {
				System.out.print ("compute");
				for (int i = 0; i < depth; i++)
					System.out.print ("  ");
				System.out.println ("5inline at "+ x+","+y);
			}
			return (-matval);
		} 

		/*
		* check for free four from my last move
		*/
		if (x1 >= 0 && (moves = must4 (x1, y1)) != null) {
			answx = moves[0][0];	// put fifth !
			answy = moves[0][1];
			if (depth <= showndepth)
				ox.gp.putapiece (answx, answy, lila);
			if (computedebug && depth <= debugdepth) {
				System.out.print ("compute");
				for (int i = 0; i < depth; i++)
					System.out.print ("  ");
				System.out.println("my must4 at " +
				x1+","+y1+" answ: "+answx+","+answy);
			}
			return (matval);
		} 
		/*
		* try to get the value from former computations
		*/
		if (ttabon) {
			if ((value = hq.get (this)) != hqueue.errval) {
				recalled++;
				if (computedebug && depth <= debugdepth) {
					System.out.print ("compute");
					for (int i = 0; i < depth; i++)
						System.out.print ("  ");
					System.out.println ("ttab val="+value);
				}
				return (value);
			}
		}
		/*
		* must delimit four set by the oposer
		* he could have another 4, but it doesn't matter !
		*/
		if ((moves = must4 (x, y)) != null) {
			/*
			* increase maxdepth in this branch of a tree
			*/
			if (maxdepth < depth+2 && maxdepth < mmaxdepth) {
				depthadd = depth+2 - maxdepth;
				maxdepth += depthadd;
			}
			if (computedebug && depth <= debugdepth) {
				System.out.print ("compute");
				for (int i = 0; i < depth; i++)
					System.out.print ("  ");
				System.out.println ("your must4 from "+ x+","+y);
			}
		}

		/*
		* check if I still have free 3
		* i must set 4 than alas i have another 3 (fork3),
		* or after beeing forced by oposers 4 (free3)
		*/
		if (moves == null) {
			if (fork3 == empty) {
				if (x1 >= 0 && (moves = must3 (x1, y1)) != null) {
					if (maxdepth < depth+2 && maxdepth < mmaxdepth) {
						depthadd = depth+2 - maxdepth;
						maxdepth += depthadd;
					}
					if (computedebug && depth <= debugdepth) {
						System.out.print ("compute");
						for (int i = 0; i < depth; i++)
							System.out.print ("  ");
						System.out.println ("my must3 from "+
						x1+","+y1+ " depth=" + depth + "/" + maxdepth);
					}
				} 
			} else if (fork3 == piece || free3 == piece) {
				moves = search3s (piece);
			}
			if (fork3 == empty)
				free3 = empty;	// free3 will be answered if not fork3
			fork3 = empty;		// fork3 will be answered and vanishes
								// for sure
		} 

		/*
		* must delimit 3 from the oposer - yes
		* i cannot have own 3, nor 4 at this stage (see up)
		*/
		if (moves == null) {
			if ((moves = must3 (x, y)) != null) {
				if (maxdepth < depth+2 && maxdepth < mmaxdepth) {
					depthadd = depth+2 - maxdepth;
					maxdepth += depthadd;
				}
				if (computedebug && depth <= debugdepth) {
					System.out.print ("compute");
					for (int i = 0; i < depth; i++)
						System.out.print ("  ");
					System.out.println (" your must3 from "+
					x+","+y+ " depth=" + depth + "/" + maxdepth);
				}

			}
		}
		/*
		* this is the leaf-node in a game-tree
		* compute statical value only
		*/
		if (depth >= maxdepth ||
			(gpanel.movnr < 3 && depth >= 2)) {	// depth of first move
			int e = evaluate ();
			if (computedebug && depth <= debugdepth) {
				System.out.print ("compute");
				for (int i = 0; i < depth; i++)
					System.out.print ("  ");
				System.out.println ("eval= " + e);
			}
			if (ttabon) {
				if (hq.insert (this, e))
					stored++;
			}
			return (e);
		}
		if (newmovesdebug && depth <= debugdepth && moves != null) {
			System.out.print ("newmov0");
			for (int i = 0; i < depth; i++)
				System.out.print ("  ");
			System.out.print ("len=" + moves.length + " ");
			for (int i = 0; i < moves.length; i++)
				System.out.print ("(" + moves[i][0] + "," +
										moves[i][1] + ") ");
			System.out.println ();
		}

		/*
		* propose other new moves
		*/
		if (moves == null)
			moves = newmoves (1, depth);
		if (moves.length == 0) {
			System.out.println ("compute: no moves to account for");
			return (0);		// this is a program error !
		}
		desk deskv[] = new desk[moves.length];

		/*
		* presort desk vector with decreasing eval values
		* this might help to limit recursiv call to those > beta
		*/
		byte ppiece	= swabpiece (piece);
		for (int w = 0; w < moves.length; w++) {
			deskv[w] = new desk(board);
			deskv[w].newx = moves[w][0];
			deskv[w].newy = moves[w][1];
			deskv[w].board[deskv[w].newx][deskv[w].newy] = piece;
			deskv[w].piece = ppiece;
			deskv[w].fork3 = fork3;
			deskv[w].free3 = free3;
			if (presort) {
				deskv[w].eval = -deskv[w].evaluate ();
			}
		}
		if (presort) {
			Arrays.sort (deskv, new deskcomparator());
		}

		/*
		* main recursive call
		*/
		for (int w = 0; w < moves.length && best < beta; w++) {
			byte nx = deskv[w].newx;
			byte ny = deskv[w].newy;
			if (board[nx][ny] == white || board[nx][ny] == black ) {
				System.out.println ("compute: field " + nx + "," +
					 ny +" already occupied " + board[nx][ny]);
				System.exit (1);
			}
			if (depth <= showndepth) {
				ox.gp.putapiece (nx, ny, (byte)(deskv[w].piece+black));
			}
			if (best > alpha) alpha = best;
			/*
			* the window for the opponent's reply is (-beta,-alpha)
			* his value is minus my value
			*/
			value = -deskv[w].compute (depth+1,
					-beta, -alpha, nx, ny, x, y);
			if (depth <= showndepth)
				ox.gp.putapiece (nx, ny, lila);
			if (value > best) {
				best = value;
				k = w;
			}
		}

		/*
		* shows % of all possible moves, which are taken into account
		* the less the better; this is mainly due to pre sorting
		*/
		if (showpresorted) {
			float f = (float)k/(float)moves.length;
            ox.tf[1].setText ("p.sort=" + String.valueOf(f));
		}

		/* transport unsharp from one ply to another -
		*  won't give up even if the solution path is already found !
		*/
		if (best > 0) best--;
		if (best < 0) best++;
		maxdepth = depthx;			// restore previous state
		answx = deskv[k].newx;
		answy = deskv[k].newy;

		if (ttabon) {
			if (hq.insert (this, best))
				stored++;
		}
		if (computedebug && depth <= debugdepth) {
			System.out.print ("compute");
			for (int i = 0; i < depth; i++)
				System.out.print ("  ");
			System.out.print ("} depth=" + depth +
			" alpha=" + alpha +
			" beta=" + beta +
			" move=" + k + "/" + moves.length);
			if (piece == white)
				System.out.print (" O(");
			if (piece == black)
				System.out.print (" X(");
			System.out.println (answx + "," + answy + ") val=" + best);
		}
		return (best);
	}

	public static byte swabpiece (byte p) {
		if      (p == white)	return (black);
		else if (p == black)	return (white);
		else if (p == lyellow)	return (dyellow);
		else if (p == dyellow)	return (lyellow);
		else if (p == lila)		return (red);
		else if (p == red)		return (lila);
		else {
			System.out.println ("swabpiece: wrong piece "+p);
			System.exit (1);
		}
		return (empty);	// my compiler needs this !
	}

	/*
	* returns a vector with countur of board[][] shape
	* dist fields thick
	*/
	public byte[][] newmoves (int dist, int depth) {
		byte 	x, y;
		int 	r = 0;
		if (board == null) {
			System.out.println ("newmoves: board empty");
			return (null);
		}
		for (byte i = 0; i < xsize; i++)
		for (byte j = 0; j < ysize; j++) {
			if (board[i][j] == white ||
				board[i][j] == black) {
				for (int k = -1*dist; k <= dist; k++)
				for (int l = -1*dist; l <= dist; l++) {
					x = (byte)(i + k);
					y = (byte)(j + l);
					if (x >= 0 && x < xsize && y >= 0 && y < ysize)
						if (board[x][y] != white &&
							board[x][y] != black) {
							mbuf[r][0] = x;
							mbuf[r][1] = y;
							r++;
					}
				}
			}
		}
		if (r > maxwidth) {
			System.out.println ("newmoves: maxwidth exceeded " + r);
			r = maxwidth;
		}
		byte	m[][] = rmdouble (mbuf, r);		// remove doubles
		if (r == 0 || m.length == 0) {
			System.out.println ("newmoves: error mbuf_len="+
				r + " len=" + m.length);
			for (int i = 0; i < r; i++)
				System.out.print ("("+mbuf[i][0]+","+mbuf[i][1]+") ");
			System.out.println ();
			out(0);
		}
		if (newmovesdebug && depth <= debugdepth) {
			System.out.print ("newmoves: len=" + m.length + ": ");
			for (int i = 0; i < m.length; i++)
				System.out.print (m[i][0]+","+m[i][1]+" ");
			System.out.println ();
		}
		return (m);
	}

	/*
	* print the current desk on stdout
	*/
	public void out (int mode) {
		if (mode == 0) {
			for (byte j = 0; j < ysize; j++) {
				for (byte i = 0; i < xsize; i++) {
					if (board[i][j] == white)
						System.out.print ("O");
					else if (board[i][j] == black)
						System.out.print ("X");
					else
						System.out.print (" ");
				}
				System.out.println ();
			}
		}
		if (mode == 1) {
			for (byte j = 0; j < ysize; j++) {
				for (byte i = 0; i < xsize; i++) {
					if (board[i][j] == white)
						System.out.print ("O("+i+","+j+") ");
					else if (board[i][j] == black)
						System.out.print ("X("+i+","+j+") ");
				}
			}
		}
		System.out.println ();
	}

	static final byte dv[][] = {		// shift directions
	{ 1,-1},	// north east
	{ 1, 0},	// east
	{ 1, 1},	// south east
	{ 0, 1},	// south
	{-1, 1},	// south west
	{-1, 0},	// west
	{-1,-1},	// north west
	{ 0,-1}};	// north

	/*
	* test if there are n pieces in line, (n = 5, 4, 3)
	* created by the last move (mx,my) 
	*/
	public boolean inline (int cnt, byte mx, byte my) {
		byte	p = board[mx][my];	// pieces
		if (p != white && p != black) {
			System.out.println ("inline: wrong piece arg " +
				p + " at " + mx + "," + my);
			out(0);
			System.exit (1);
		}
		for (int i = 0; i < 4; i++) {	// eight with shift back
			byte	x = mx, y = my;
			while ( x >= 0    && y >= 0 &&
					x < xsize && y < ysize &&
					board[x][y] == p) { // shift with dv
				x += dv[i][0];
				y += dv[i][1];
			}
			x -= dv[i][0];
			y -= dv[i][1];
			byte k = 0;			// start cnt counter
			while ( x >= 0 && x < xsize &&
					y >= 0 && y < ysize &&
					board[x][y] == p) { // shift back
				x -= dv[i][0];
				y -= dv[i][1];
				k++;
			}
			if (k >= cnt) {
				return (true);
			}
		}
		return (false);
	}

	/*
	* This checks for a must-move depending on four in line and
	* one empty for fifth. All must-move(s) are returned.
	* These many if-conditions are the most efficient method.
	* One must check all directions for possible double fours
	*/
 	public byte[][] must4 (byte mx, byte my) {
		byte	p = board[mx][my];
		byte	pp = swabpiece (p);
		byte	x1, x2, x3, x4, x5, y1, y2, y3, y4, y5;
		int		k = 0, n = 0;
		if (p != white && p!= black) {
			return (null);
		}
		for (int i = 0; i < 8; i++) {	// eight shift directions
			x1 = mx; y1 = my;
			while ( x1 >= 0    && y1 >= 0 &&
				    x1 < xsize && y1 < ysize &&
					board[x1][y1] == p) { // shift with dv
				x1 -= dv[i][0];
				y1 -= dv[i][1];
			}
			x2 = (byte)(x1 + dv[i][0]);
			y2 = (byte)(y1 + dv[i][1]);
			k = 0;
			while ( x2 >= 0 && y2 >= 0 &&
				    x2 < xsize && y2 < ysize &&
				    board[x2][y2] == p) { // shift back
				x2 += dv[i][0];
				y2 += dv[i][1];
				k++;
			}
			/*		    <-   k  ->
			*	_____________________	4
			*	     |  X  X  X  X  |
			*	    x1             x2
			*/
			if (k == 4 &&			// four
				x1 >= 0 && x1 <xsize &&
				y1 >= 0 && y1 <ysize &&
				board[x1][y1] != pp) {
				b[n][0] = x1;
				b[n][1] = y1;
				n++;
				/* x2 empty if for i = i + 4	*/
				//System.out.print (" four: "+bx+","+by);
			}
			x3 = (byte)(x2 + dv[i][0]);
			y3 = (byte)(y2 + dv[i][1]);
			/*		    <- k ->
			*	________________________	3 + 1 with hole
			*	     |  X  X  X     X
			*	    x1          x2 x3
			*/
			if (k == 3 &&			// 3 + 1 with whole
				x2 >= 0 && x2 < xsize &&
				y2 >= 0 && y2 < ysize && board[x2][y2] != pp &&
				x3 >= 0 && x3 < xsize &&
				y3 >= 0 && y3 < ysize && board[x3][y3] == p) {
				b[n][0] = x2;
				b[n][1] = y2;
				n++;
				//System.out.print (" 3+1: "+x2+","+y2);
			}
			x4 = (byte)(x3 + dv[i][0]);
			y4 = (byte)(y3 + dv[i][1]);
			/*		    <k->
			*	________________________	 2 + 2 with hole
			*	     |  X  X     X  X
			*	    x1       x2 x3 x4
			*/
			if (k == 2 &&
				x2 >= 0 && x2 < xsize &&
				y2 >= 0 && y2 < ysize && board[x2][y2] != pp &&
				x3 >= 0 && x3 < xsize &&
				y3 >= 0 && y3 < ysize && board[x3][y3] == p &&
				x4 >= 0 && x4 < xsize &&
				y4 >= 0 && y4 < ysize && board[x4][y4] == p) {
				b[n][0] = x2;
				b[n][1] = y2;
				n++;
				//System.out.print (" 2+2: "+x2+","+y2);
			}
			x5 = (byte)(x4 + dv[i][0]);
			y5 = (byte)(y4 + dv[i][1]);
			/*		   <k>
			*	________________________	1 + 3 with hole
			*	     |  X     X  X  X
			*	    x1    x2 x3 x4 x5
			*/
			if (k == 1 &&
				x2 >= 0 && x2 < xsize &&
				y2 >= 0 && y2 < ysize && board[x2][y2] != pp &&
				x3 >= 0 && x3 < xsize &&
				y3 >= 0 && y3 < ysize && board[x3][y3] == p &&
				x4 >= 0 && x4 < xsize &&
				y4 >= 0 && y4 < ysize && board[x4][y4] == p &&
				x5 >= 0 && x5 < xsize &&
				y5 >= 0 && y5 < ysize && board[x5][y5] == p) {
				b[n][0] = x2;
				b[n][1] = y2;
				n++;
				//System.out.print (" 1+3: "+x2+","+y2);
			}
		}
		if (n == 0)
			return (null);
		byte	m[][] = rmdouble (b, n);		// remove doubles
		if (must4debug) {
			System.out.print ("must4 n="+n+" k="+k+" piece="+p);
			for (int i = 0; i < n; i++)
				System.out.print (" "+m[i][0]+","+m[i][1]);
			System.out.println ();
		}
		return (m);
	}

	/*
	* This returns all delimiters for three in line.
	* Up to three possible moves are returned.
	*/
	public byte[][] must3 (byte mx, byte my) {
		byte	p = board[mx][my];	// pieces
		byte	pp = swabpiece (p);
		byte	n = 0;				// number of delimiters
		byte	x1, x2, x3, x4, x5, y1, y2, y3, y4, y5;
		int		k = 0;
		if (p != white && p != black) { return (null); }
		for (int i = 0; i < 8; i++) { // eight directions
			/*
			* go left with same p as far as possible
			*/
			x1 = mx; y1 = my;
			while ( x1 >= 0    && y1 >= 0    &&
					x1 < xsize && y1 < ysize &&
					board[x1][y1] == p) {	// if same p
				x1 -= dv[i][0];				// shift with dv
				y1 -= dv[i][1];
			}
			/*
			* turn back with same p
			*/
			k = 0;
			x2 = (byte)(x1 + dv[i][0]);
			y2 = (byte)(y1 + dv[i][1]);
			while ( x2 >= 0    && y2 >= 0    &&
					x2 < xsize && y2 < ysize &&
					board[x2][y2] == p) {
				x2 += dv[i][0];				// right border
				y2 += dv[i][1];
				k++;
			}
			/*	    <-k->
			*	_______________			3 in line
			*	  | X X X | 
			*	 x1      x2
			*/
			if (k  == 3 &&
				x1 >= 0 && x1 < xsize &&
				y1 >= 0 && y1 < ysize && board[x1][y1] != pp &&
				x2 >= 0 && x2 < xsize &&
				y2 >= 0 && y2 < ysize && board[x2][y2] != pp) {
					b[n][0] = x2;
					b[n][1] = y2;
					n++;
					b[n][0] = x1;
					b[n][1] = y1;
					n++;
			}
			/*		    < k >
			*	_____________________	2 + 1 with hole
			*	     |  X  X  |  X  |
			*	    x1       x2 x3 x4
			*/
			x3 = (byte)(x2 + dv[i][0]);
			y3 = (byte)(y2 + dv[i][1]);
			x4 = (byte)(x3 + dv[i][0]);
			y4 = (byte)(y3 + dv[i][1]);
			if ( k == 2 &&
				x1 >= 0 && x1 < xsize &&
				y1 >= 0 && y1 < ysize && board[x1][y1] != pp &&
				x2 >= 0 && x2 < xsize &&
				y2 >= 0 && y2 < ysize && board[x2][y2] != pp &&
				x3 >= 0 && x3 < xsize &&
				y3 >= 0 && y3 < ysize && board[x3][y3] == p &&
				x4 >= 0 && x4 < xsize &&
				y4 >= 0 && y4 < ysize && board[x4][y4] != pp) {
					b[n][0] = x1;
					b[n][1] = y1;
					n++;
					b[n][0] = x2;
					b[n][1] = y2;
					n++;
					b[n][0] = x4;
					b[n][1] = y4;
					n++;
			}
			/*		   <k>
			*	_____________________	1 + 2 with hole
			*	     |  X  |  X  X  |
			*	    x1    x2 x3 x4 x5
			*/
			x5 = (byte)(x4 + dv[i][0]);
			y5 = (byte)(y4 + dv[i][1]);
			if ( k == 1 &&
				x1 >= 0 && x1 < xsize &&
				y1 >= 0 && y1 < ysize && board[x1][y1] != pp &&
				x2 >= 0 && x2 < xsize &&
				y2 >= 0 && y2 < ysize && board[x2][y2] != pp &&
				x3 >= 0 && x3 < xsize &&
				y3 >= 0 && y3 < ysize && board[x3][y3] == p &&
				x4 >= 0 && x4 < xsize &&
				y4 >= 0 && y4 < ysize && board[x4][y4] == p &&
				x5 >= 0 && x5 < xsize &&
				y5 >= 0 && y5 < ysize && board[x5][y5] != pp) {
					b[n][0] = x1;
					b[n][1] = y1;
					n++;
					b[n][0] = x2;
					b[n][1] = y2;
					n++;
					b[n][0] = x5;
					b[n][1] = y5;
					n++;
			}
		}
		if (n == 0) return (null);
		free3 = p;
		byte	m[][] = rmdouble (b, n);		// remove doubles
		if (m.length > 3)
			fork3 = p;			// fork3 means second free3
		if (must3debug) {
			System.out.print ("must3 n="+n+" fork3="+fork3+" k="+k+" piece="+p);
			for (int i = 0; i < m.length; i++)
				System.out.print (" "+m[i][0]+","+m[i][1]);
			System.out.println ();
		}
		return (m);
	}

	/*
	*	search for all must3 on the whole board
	*/
	public byte[][] search3s (byte p) {
		byte n = 0;
		for (byte i = 0; i < xsize; i++)
		for (byte j = 0; j < ysize; j++) {
			if (board[i][j] == p) {
				byte buf[][] = must3 (i, j);
				if (buf != null) {
					for (byte k = 0; k < buf.length; k++) {
						mbuf[n][0] = buf[k][0];
						mbuf[n][1] = buf[k][1];
						n++;
					}
				}
			}
		}
		return (rmdouble (mbuf, n));
	}

	/*
	*	remove double elements from a 2d vector
	*/
	public byte[][] rmdouble (byte[][] buf, int n) {
		if (n == 0)	return (null);
		for (int i = 0; i < n; i++)
		for (int j = i + 1; j < n; j++) {
			if (buf[j][0] == buf[i][0] && buf[j][1] == buf[i][1]) {
				// shift left
				for (int l = j; l < n - 1; l++) {
					buf[l][0] = buf[l+1][0];
					buf[l][1] = buf[l+1][1];
				}
				n--;
				j--;	// first try at the same position
			}
		}
		byte	m[][] = new byte[n][2]; 
		for (int i = 0; i < n; i++) {
			m[i][0] = buf[i][0];
			m[i][1] = buf[i][1];
		}
		return (m);
	}

	/*
	* calculate statical value of a board position
	* This routine returns a number of possible fives
	* (with at least two pieces already set)
	* minus the number of enemys possible fives.
	*/
	public int evaluate () {
		byte p1 = piece;
		if (p1 != white && p1 != black) {
			System.out.println ("evaluate: wrong piece "+p1);
			return (0);
		}
		int	sum = 0;
		int three1 = 0;
		int	f;				// factor for piece type
		byte p2 = swabpiece (p1);
		for (int i = 0; i < xsize; i++)		// for the whole board
		for (int j = 0; j < ysize; j++) {
			byte p  = board[i][j];
			if      (p == p1)	f = 1;
			else if (p == p2)	f = -1;
			else continue;
			int three = 0;
		for (int l = 0; l < 4; l++) {		// for all directions
			int 	bx, by;
			int	x = i, y = j;
			int	k = 0;
			while ( x >= 0    && y >= 0 &&	// shift with dv
					x < xsize && y < ysize && k < 5 &&
					(board[x][y] == p ||
						(board[x][y] != white &&
						 board[x][y] != black)
					)
				  ) {
					x -= dv[l][0];
					y -= dv[l][1];
					k++;
			}
			x += dv[l][0];
			y += dv[l][1];
			bx = x;
			by = y;
			three1 = 0;
			for (int d = 0; d < k; d++) { // for every start shift
				x = bx + d * dv[l][0];
				y = by + d * dv[l][1];
				int m = 0;		// maximal shift
				int s = 1;		// partial sum
				int three0  = 0;
				while ( x >= 0 && x < xsize &&
						y >= 0 && y < ysize && m < 5) {
					if (board[x][y] == p) {
						s *= 2;
						three0++;
					}
					else if (board[x][y] != white &&
							 board[x][y] != black)	;
					else				break;
					x += dv[l][0];
					y += dv[l][1];
					m++;
				}
				if (m == 5) {		// found 5 places
					sum += f*s;
					if (three0 >= 3)	three1++;
				}
			}
			if (three1 > 0)	three++;
		}
		if (three > 1) sum += add3;
		}
		if (sum > matval)
			System.out.println ("evaluate: sum=" +sum + " > matval");
		return (sum);
	}
}

/*
* used in sort() in decreasing order
*/
class deskcomparator implements Comparator {
	public int compare (Object d1, Object d2) {
		return (((desk)d2).eval - ((desk)d1).eval);
	}
}