/**
 * class Board
 *
 * Represents a position on the board and also contains methods for making
 * and unmaking a move, as well as generating all possible (legal) moves on
 * the board.
 *
 * @author Jonatan Pettersson (mediocrechess@gmail.com)
 * Date: 2006-12-14
 * Last update: 2006-12-25
 */

public class Board implements Definitions
{
	// ***
	// Variables used to describe the position
	// ***
	
	private int[] boardArray; 		// Represents the 0x88 board

	public int toMove; 			// Side to move on the board

	public int enPassant;  		// Index on boardArray where en passant is
						// available, -1 if none

	public int white_castle;		// White's ability to castle
	public int black_castle; 		// Black's ability to castle

	public int movesFifty;			// Keeps track of half-moves since last capture
						// or pawn move
						
	public int movesFull; 			// Keeps track of total full moves in the game
	public int[] history;			// Keeps track of previous positions for unmake move
	public int[] captureHistory;
	public long[] zobristHistory;	// Same as history but keeps tracks of passed zobrist keys
	
	public int historyIndex;		// Keeps track of number of takebacks in the history arrays
	
	
	public long zobristKey;			// The zobrist key for the position

	//public int wking_index;
	//public int bking_index;
	
	public int[] pieces;
	public static final int PIECE_UNIQUE_SHIFT = 4;
	public static final int PIECE_TYPE_MASK = 15;
	
	//END Variables

	/**
	 *  Creates an empty board
	 *
	 *  @return An empty Board
	 */
	public Board()
	{
		this.boardArray = new int[128];
		this.toMove = 1; // White to move
		this.enPassant = -1; // No en passants available
		this.white_castle = CASTLE_NONE;
		this.black_castle = CASTLE_NONE;
		this.pieces = new int[32];
		this.history = new int[4096];
		this.captureHistory = new int[4096];
		this.zobristHistory = new long[4096];
		zobristKey = 0;
	}
	// END Board()

	/**
	 *  Makes a Move on the board and updates the zobrist key accordingly
	 *
	 *  @param Move move
	 */
	public void makeMove(int move)
	{
	
		// Backup information about the position for use in unmake
		history[historyIndex] = 0;
		if(enPassant != -1)
		{
			history[historyIndex] =
				enPassant;
		}		
		
		history[historyIndex] = history[historyIndex] |
			  (white_castle << 7)
			| (black_castle << 9)
			| (movesFifty << 16);
		
		captureHistory[historyIndex] = boardArray[Move.toIndex(move)]; // If the move is an en passant this will be 0 here, but changed when we catch en passant below
		
		zobristHistory[historyIndex] = zobristKey;
		
		
		// Done with backing up, continue
		
		if(enPassant != -1) zobristKey ^= Zobrist.EN_PASSANT[enPassant]; // Unmake the enpassant square that is on the board now, and replace it below when it is set again

		zobristKey ^= Zobrist.SIDE; // Toggles the side to move
		
		// Remove the castling rights now on the board, and replace them below when they are set again
		zobristKey ^= Zobrist.W_CASTLING_RIGHTS[white_castle];
		zobristKey ^= Zobrist.B_CASTLING_RIGHTS[black_castle];

							
		enPassant = -1; // Set the en passant square to none, will be reset below if it becomes available

		toMove *= -1; // Switch side to move (multiply toMove by -1 simply switches from negative to positive
				// and vice versa)
		
		// Update the king index
	//	if(Move.pieceMoving(move) == W_KING) wking_index = Move.toIndex(move);
		//if(Move.pieceMoving(move) == B_KING) bking_index = Move.toIndex(move);
		
		
		// Set the piece list index of the piece that is moving
		pieces[pieceUniqueOnIndex(Move.fromIndex(move))] = Move.toIndex(move);
		
		
		
		if(Move.pieceMoving(move) != W_PAWN && Move.pieceMoving(move) != B_PAWN && Move.capture(move) == 0)
			movesFifty++; // Increment the moves fifty if not a pawn moving or a capture
		else
			movesFifty = 0; // If a pawned moved or it was a capture, reset the movesFifty count

		if(Move.pieceMoving(move) < 0)
			movesFull++; // Increment the total of full moves if the moving piece is black

		// Now find out what kind of move it is and act accordingly
		switch(Move.moveType(move))
		{
			case ORDINARY_MOVE:
			{
				// Remove and replace the piece in the zobrist key
				if(toMove == -1) // We have switched side so black means a white piece is moving
				{
					zobristKey ^= Zobrist.PIECES[Math.abs(Move.pieceMoving(move))-1][0][Move.fromIndex(move)];
					zobristKey ^= Zobrist.PIECES[Math.abs(Move.pieceMoving(move))-1][0][Move.toIndex(move)];
				}
				else
				{
					zobristKey ^= Zobrist.PIECES[Math.abs(Move.pieceMoving(move))-1][1][Move.fromIndex(move)];
					zobristKey ^= Zobrist.PIECES[Math.abs(Move.pieceMoving(move))-1][1][Move.toIndex(move)];
				}	

				boardArray[Move.toIndex(move)] = boardArray[Move.fromIndex(move)]; // Set target square
				boardArray[Move.fromIndex(move)] = EMPTY_SQUARE; // Clear the original square

				// Check for en passant
				// If the piece moving is a white or black pawn, and it has moved
				// 2 squares (the Math.abs line checks that)
				// set the en passant square to the right index and exit the move
				if((Move.pieceMoving(move) == W_PAWN || Move.pieceMoving(move) == B_PAWN)
						&& Math.abs(Move.toIndex(move) - Move.fromIndex(move)) == 32)
				{
					enPassant = Move.fromIndex(move) + (Move.toIndex(move) - Move.fromIndex(move))/2;
					break;
				}
				break;
			}

			case SHORT_CASTLE:
			{
				if (Move.pieceMoving(move) == W_KING) // White king castles short
				{
					zobristKey ^= Zobrist.PIECES[Math.abs(Move.pieceMoving(move))-1][0][Move.fromIndex(move)];
					zobristKey ^= Zobrist.PIECES[Math.abs(Move.pieceMoving(move))-1][0][Move.toIndex(move)];
					
					// And the rook
					zobristKey ^= Zobrist.PIECES[W_ROOK-1][0][7];
					zobristKey ^= Zobrist.PIECES[W_ROOK-1][0][5];	
					
					// Change the place of the rook in the piece list as well
					pieces[pieceUniqueOnIndex(7)] = 5;
					
					boardArray[6] = boardArray[4]; // Put white king
					boardArray[5] = boardArray[7]; // Put white rook
					boardArray[7] = EMPTY_SQUARE; // Empty the rook square
					boardArray[4] = EMPTY_SQUARE; // Empty the king square
					
					white_castle = CASTLE_NONE; // Make further castling impossible for white
				}
				else // Black king castles short
				{
					zobristKey ^= Zobrist.PIECES[Math.abs(Move.pieceMoving(move))-1][1][Move.fromIndex(move)];
					zobristKey ^= Zobrist.PIECES[Math.abs(Move.pieceMoving(move))-1][1][Move.toIndex(move)];

					// And the rook, stils W_ROOK since '1' takes care of color
					zobristKey ^= Zobrist.PIECES[W_ROOK-1][1][119];
					zobristKey ^= Zobrist.PIECES[W_ROOK-1][1][117];
					
					// Change the place of the rook in the piece list as well
					pieces[pieceUniqueOnIndex(119)] = 117;

					boardArray[118] = boardArray[116]; // Put black king
					boardArray[117] = boardArray[119]; // Put black rook
					boardArray[119] = EMPTY_SQUARE; // Empty the rook square
					boardArray[116] = EMPTY_SQUARE; // Empty the king square
					
					black_castle = CASTLE_NONE; // Make further castling impossible for black
				}				
				break;
			}

			case LONG_CASTLE:
			{
				if (Move.pieceMoving(move) == W_KING) // White king castles long
				{
					zobristKey ^= Zobrist.PIECES[Math.abs(Move.pieceMoving(move))-1][0][Move.fromIndex(move)];
					zobristKey ^= Zobrist.PIECES[Math.abs(Move.pieceMoving(move))-1][0][Move.toIndex(move)];
					
					// And the rook
					zobristKey ^= Zobrist.PIECES[W_ROOK-1][0][0];
					zobristKey ^= Zobrist.PIECES[W_ROOK-1][0][3];
					
					// Change the place of the rook in the piece list as well
					pieces[pieceUniqueOnIndex(0)] = 3;

					boardArray[2] = boardArray[4]; // Put white king
					boardArray[3] = boardArray[0]; // Put white rook
					boardArray[0] = EMPTY_SQUARE; // Empty the rook square
					boardArray[4] = EMPTY_SQUARE; // Empty the king square
					
					white_castle = CASTLE_NONE; // Make further castling impossible for white
				}
				else // Black king castles long
				{
					zobristKey ^= Zobrist.PIECES[Math.abs(Move.pieceMoving(move))-1][1][Move.fromIndex(move)];
					zobristKey ^= Zobrist.PIECES[Math.abs(Move.pieceMoving(move))-1][1][Move.toIndex(move)];

					// And the rook, still W_ROOK since '1' takes care of color
					zobristKey ^= Zobrist.PIECES[W_ROOK-1][1][112];
					zobristKey ^= Zobrist.PIECES[W_ROOK-1][1][115];
					
					// Change the place of the rook in the piece list as well
					pieces[pieceUniqueOnIndex(112)] = 115;

					boardArray[114] = boardArray[116]; // Put black king
					boardArray[115] = boardArray[112]; // Put black rook
					boardArray[112] = EMPTY_SQUARE; // Empty the rook square
					boardArray[116] = EMPTY_SQUARE; // Empty the king square
					
					black_castle = CASTLE_NONE; // Make further castling impossible for black
				}		
				break;
			}

			case EN_PASSANT:
			{
				// Remove and replace the piece in the zobrist key
				if(toMove == -1) // We have switched side so this means white is moving
				{
					zobristKey ^= Zobrist.PIECES[Math.abs(Move.pieceMoving(move))-1][0][Move.fromIndex(move)];
					zobristKey ^= Zobrist.PIECES[Math.abs(Move.pieceMoving(move))-1][0][Move.toIndex(move)];

					
					// Remove the pawn from the piece list as well
					pieces[pieceUniqueOnIndex(Move.toIndex(move) - 16)] = -1;
					
					captureHistory[historyIndex] = boardArray[Move.toIndex(move) - 16];
					
					// Since it's an en passant capture we also need to remove the captured pawn
					// which resides one square up/down from the target square
					// If it's a white pawn capturing, clear the square below it
					boardArray[Move.toIndex(move) - 16] = EMPTY_SQUARE;
					
					

					// Black pawn is to be removed
					zobristKey ^= Zobrist.PIECES[W_PAWN-1][1][Move.toIndex(move) - 16];

				}
				else
				{
					zobristKey ^= Zobrist.PIECES[Math.abs(Move.pieceMoving(move))-1][1][Move.fromIndex(move)];
					zobristKey ^= Zobrist.PIECES[Math.abs(Move.pieceMoving(move))-1][1][Move.toIndex(move)];

					// Remove the pawn from the piece list as well
					pieces[pieceUniqueOnIndex(Move.toIndex(move) + 16)] = -1;
					
					captureHistory[historyIndex] = boardArray[Move.toIndex(move) + 16];
					
					boardArray[Move.toIndex(move) + 16] = EMPTY_SQUARE;	

					// White pawn is to be removed
					zobristKey ^= Zobrist.PIECES[W_PAWN-1][0][Move.toIndex(move) + 16];
				}				
				boardArray[Move.toIndex(move)] = boardArray[Move.fromIndex(move)]; // Set target square
				boardArray[Move.fromIndex(move)] = EMPTY_SQUARE; // Clear the original square	
				break;
			}

			default: // Catches promotions since that's the only type of move left
			{
				// Check for queen, rook, bishop and knight promotions
				switch(Move.moveType(move))
				{
					// Put a promoted piece of the right color on the target square
					// We use the toMove property to get the right color but since
					// we already changed side to move we need the opposite color
					// 
					// E.g. promotion to queen and white to move would result in
					// 2*(-(-1)) = 2 and for black 2*(-(1)) = -2
					case PROMOTION_QUEEN:
					{
						boardArray[Move.toIndex(move)] = boardArray[Move.fromIndex(move)];
						setPieceTypeOnIndex(Move.toIndex(move), W_QUEEN*(-toMove));

						if(toMove == -1)
						{
							zobristKey ^= Zobrist.PIECES[W_QUEEN-1][0][Move.toIndex(move)];
							zobristKey ^= Zobrist.PIECES[W_PAWN-1][0][Move.fromIndex(move)];
						}
						else
						{
							zobristKey ^= Zobrist.PIECES[W_QUEEN-1][1][Move.toIndex(move)];
							zobristKey ^= Zobrist.PIECES[W_PAWN-1][1][Move.fromIndex(move)];
						}
						
						break;
					}
					case PROMOTION_ROOK:
					{
						boardArray[Move.toIndex(move)] = boardArray[Move.fromIndex(move)];
						setPieceTypeOnIndex(Move.toIndex(move), W_ROOK*(-toMove));
						
						if(toMove == -1)
						{
							zobristKey ^= Zobrist.PIECES[W_ROOK-1][0][Move.toIndex(move)];
							zobristKey ^= Zobrist.PIECES[W_PAWN-1][0][Move.fromIndex(move)];
						}
						else
						{
							zobristKey ^= Zobrist.PIECES[W_ROOK-1][1][Move.toIndex(move)];
							zobristKey ^= Zobrist.PIECES[W_PAWN-1][1][Move.fromIndex(move)];
						}
						break;
					}
					case PROMOTION_BISHOP:
					{
						boardArray[Move.toIndex(move)] = boardArray[Move.fromIndex(move)];
						setPieceTypeOnIndex(Move.toIndex(move), W_BISHOP*(-toMove));
						
						if(toMove == -1)
						{
							zobristKey ^= Zobrist.PIECES[W_BISHOP-1][0][Move.toIndex(move)];
							zobristKey ^= Zobrist.PIECES[W_PAWN-1][0][Move.fromIndex(move)];
						}
						else
						{
							zobristKey ^= Zobrist.PIECES[W_BISHOP-1][1][Move.toIndex(move)];
							zobristKey ^= Zobrist.PIECES[W_PAWN-1][1][Move.fromIndex(move)];
						}
						break;
					}
					case PROMOTION_KNIGHT:
					{
						boardArray[Move.toIndex(move)] = boardArray[Move.fromIndex(move)];
						setPieceTypeOnIndex(Move.toIndex(move), W_KNIGHT*(-toMove));
						
						if(toMove == -1)
						{
							zobristKey ^= Zobrist.PIECES[W_KNIGHT-1][0][Move.toIndex(move)];
							zobristKey ^= Zobrist.PIECES[W_PAWN-1][0][Move.fromIndex(move)];
						}
						else
						{
							zobristKey ^= Zobrist.PIECES[W_KNIGHT-1][1][Move.toIndex(move)];
							zobristKey ^= Zobrist.PIECES[W_PAWN-1][1][Move.fromIndex(move)];
						}
						break;
					}
				}
				boardArray[Move.fromIndex(move)] = EMPTY_SQUARE; // Empty the square it moved from				
			}
		}
		
		// We now check for castling right changes, some of them are handles above, but
		// we need to catch them for both pawn promotions and ordinary moves, so we
		// have it outside the switch.

		// If neither white nor black can castle, we don't need to check for castling changes
		// and can skip the checks
		if(white_castle != CASTLE_NONE || black_castle != CASTLE_NONE)
		{
			// Now check the corners and king squares, if a piece (rook or king) is 'missing'
			// on one of those squares, we can remove the castling rights accordingly.
			//		
			// If the move is Ra2-a1 for black, in the check below it will look like
			// all is in order for castling, so the castling right won't be removed, BUT that
			// castling right should already have been removed when the rook moved to a2 in the
			// first place so we don't need to worry about that.

			if(pieceTypeOnIndex(4) != W_KING) // White king missing from 'e1'
			{
				white_castle = CASTLE_NONE; // Remove all castling rights for white
			}
			if(pieceTypeOnIndex(116) != B_KING)// Black king missing from 'e8'
			{
				black_castle = CASTLE_NONE; // Remove all castling rights for black
			}
			

			if(pieceTypeOnIndex(0) != W_ROOK) // White rook missing from 'a1'
			{
				if(white_castle == CASTLE_BOTH) // Remove the ability to castle long
				{
					white_castle = CASTLE_SHORT;
				}
				else if(white_castle == CASTLE_LONG)
				{
					white_castle = CASTLE_NONE;
				}
			}

			if(pieceTypeOnIndex(7) != W_ROOK) // White rook missing from 'h1'
			{
				if(white_castle == CASTLE_BOTH) // Remove the ability to castle short
				{
					white_castle = CASTLE_LONG;
				}
				else if(white_castle == CASTLE_SHORT)
				{
					white_castle = CASTLE_NONE;
				}
			}

			if(pieceTypeOnIndex(112) != B_ROOK) // Black rook missing from 'a8'
			{
				if(black_castle == CASTLE_BOTH) // Remove the ability to castle long
				{
					black_castle = CASTLE_SHORT;
				}
				else if(black_castle == CASTLE_LONG) 
				{
					black_castle = CASTLE_NONE;
				}
			}

			if(pieceTypeOnIndex(119) != B_ROOK) // White rook missing from 'h1'
			{
				if(black_castle == CASTLE_BOTH) // Remove the ability to castle short
				{
					black_castle = CASTLE_LONG;
				}
				else if(black_castle == CASTLE_SHORT)
				{
					black_castle = CASTLE_NONE;
				}
			}
		}		
		
		// If the move is a capture, remove the captured piece from zobrist as well
		if(toMove == -1) // We have switched side so black means a white piece is moving
		{
			if(Move.capture(move) != 0 && Move.moveType(move) != EN_PASSANT)
			{
				zobristKey ^= Zobrist.PIECES[Math.abs(Move.capture(move))-1][1][Move.toIndex(move)];
				
				// And from the piece list
				// If there was a capture it will be recorded in the captureHistory so we can
				// retrieve its position from there
				pieces[pieceUnique(captureHistory[historyIndex])] = -1;
			}
				
		}
		else
		{
			if(Move.capture(move) != 0 && Move.moveType(move) != EN_PASSANT)
			{
				zobristKey ^= Zobrist.PIECES[Math.abs(Move.capture(move))-1][0][Move.toIndex(move)];
				
				// And from the piece list
				pieces[pieceUnique(captureHistory[historyIndex])] = -1;
			}
		}	

		// Apply the now changed castling rights to zobrist key
		zobristKey ^= Zobrist.W_CASTLING_RIGHTS[white_castle];
		zobristKey ^= Zobrist.B_CASTLING_RIGHTS[black_castle];

		// Apply the now changed en passant square to zobrist key
		if(enPassant != -1) zobristKey ^= Zobrist.EN_PASSANT[enPassant];
		
		historyIndex++;
		
	}
	// END makeMove()
	
	/**
	 *  Just like switching side, but toggles the zobrist as well
	 */
	public void nullmoveToggle()
	{
		toMove *= -1;
		zobristKey ^= Zobrist.SIDE;
	}
	// END makeNullmove()

	/**
	 *  Unmakes a Move on the board
	 *
	 *  @param Move move
	 */
	public void unmakeMove(int move)
	{
		historyIndex--; // Go back one step in the history so we find the right unmake variables

		// Use the history to reset known variables
		if(((history[historyIndex]) & 127) == 0)
		{
			enPassant = -1;
		}
		else
		{
			enPassant = ((history[historyIndex]) & 127);
		}
		white_castle = ((history[historyIndex] >> 7) & 3);
		black_castle = ((history[historyIndex] >> 9) & 3);
		movesFifty = ((history[historyIndex] >> 16) & 127);
		zobristKey = zobristHistory[historyIndex];
		
		// We wait with resetting the capture until we know if it is an en passant or not
		


		toMove *= -1; // Switch side to move

		// Update the king index
		
		//if(Move.pieceMoving(move) == W_KING) wking_index = Move.fromIndex(move);
		//if(Move.pieceMoving(move) == B_KING) bking_index = Move.fromIndex(move);
		
		pieces[pieceUniqueOnIndex(Move.toIndex(move))] = Move.fromIndex(move);
		
		
		// If the move we're taking back was a black piece moving
		// decrement the movesFull.
		if(Move.pieceMoving(move) < 0)
			movesFull--;

		switch(Move.moveType(move))
		{
			case SHORT_CASTLE:
				{
					if (Move.pieceMoving(move) == W_KING) // White king castles short
					{	
						pieces[pieceUniqueOnIndex(5)] = 7; // Put back the rook in the piece list
						
						boardArray[4] = boardArray[6]; // Put back white king
						boardArray[7] = boardArray[5]; // Put back white rook
						boardArray[5] = EMPTY_SQUARE; // Empty castling squares
						boardArray[6] = EMPTY_SQUARE; // .
						
						
						
					}
					else if (Move.pieceMoving(move) == B_KING) // Black king castles short
					{	
						pieces[pieceUniqueOnIndex(117)] = 119; // Put back the rook in the piece list
						
						boardArray[116] = boardArray[118]; // Put back black king
						boardArray[119] = boardArray[117]; // Put back black rook
						boardArray[117] = EMPTY_SQUARE; // Empty castling squares
						boardArray[118] = EMPTY_SQUARE; // .
					
					}				
					break; // Done with unmake
				}

			case LONG_CASTLE:
				{
					if (Move.pieceMoving(move) == W_KING) // White king castles long
					{		
						pieces[pieceUniqueOnIndex(3)] = 0; // Put back the rook in the piece list
						
						boardArray[4] = boardArray[2]; // Put back white king
						boardArray[0] = boardArray[3]; // Put back white rook
						boardArray[2] = EMPTY_SQUARE; // Empty castling squares
						boardArray[3] = EMPTY_SQUARE; // .
						
					}
					else if (Move.pieceMoving(move) == B_KING) // Black king castles lon
					{
						pieces[pieceUniqueOnIndex(115)] = 112; // Put back the rook in the piece list
						
						boardArray[116] = boardArray[114]; // Put back black king
						boardArray[112] = boardArray[115]; // Put back black rook
						boardArray[114] = EMPTY_SQUARE; // Empty castling squares
						boardArray[115] = EMPTY_SQUARE; // .
					
					}		
					break; // Done with unmake
				}
			case EN_PASSANT:
				{
					// Remove and replace the piece in the zobrist key
					if(toMove == 1)
					{
						// Put back the black pawn
						boardArray[Move.toIndex(move) - 16] = captureHistory[historyIndex];
						pieces[pieceUnique(captureHistory[historyIndex])] = Move.toIndex(move) - 16;
					}
					else
					{
						// Put back the white pawn
						boardArray[Move.toIndex(move) + 16] = captureHistory[historyIndex];
						pieces[pieceUnique(captureHistory[historyIndex])] = Move.toIndex(move) + 16;
					}								

					boardArray[Move.fromIndex(move)] = boardArray[Move.toIndex(move)]; // Put back the pawn
					boardArray[Move.toIndex(move)] = EMPTY_SQUARE; // Clear the original square


					break;
				}
			default:
				{					       
					boardArray[Move.fromIndex(move)] = boardArray[Move.toIndex(move)]; // Put back the piece
					setPieceTypeOnIndex(Move.fromIndex(move), Move.pieceMoving(move)); // Make sure we have the right piece, change it back from promotion
					boardArray[Move.toIndex(move)] = captureHistory[historyIndex]; // Put back the captured piece, 0 if it wasn't a capture
					
					// And if it was a capture put it back in the piece list
					if(captureHistory[historyIndex] != 0)
					{
						//System.out.println("Setting pieces[" + pieceUnique(captureHistory[historyIndex]) + "] to " + Move.toIndex(move) + " and piece captured was " + pieceType(captureHistory[historyIndex]));
						pieces[pieceUnique(captureHistory[historyIndex])] = Move.toIndex(move);
					}
								
				}				
		}
	}
	// END unmakeMove()
	
	/**
	 * Returns the place the piece has in the piece list
	 * 
	 * @param piece The piece to check
	 * @return int The place it has in the piece list
	 */
	public int pieceUnique(int piece)
	{
		return (piece >> PIECE_UNIQUE_SHIFT);
	}
	// END pieceUnique()
	
	/**
	 * Returns the type of the piece
	 * 
	 * @param piece The piece to check
	 * @return int The type
	 */
	public int pieceType(int piece)
	{
		return (piece & PIECE_TYPE_MASK)-7;
	}
	// END pieceUnique()
	
	/**
	 * Takes an index and returns the place the piece has in the piece list
	 * 
	 * @param piece The piece to check
	 * @return int The place it has in the piece list
	 */
	public int pieceUniqueOnIndex(int index)
	{
		return (boardArray[index] >> PIECE_UNIQUE_SHIFT);
	}
	// END pieceUnique()
	
	/**
	 * Takes an index and returns the piece type on that index
	 * 
	 * @param piece The piece to check
	 * @return int The piece type (-6 for black pawn, 2 for white queen etc.)
	 */
	public int pieceTypeOnIndex(int index)
	{
		if((boardArray[index] & PIECE_TYPE_MASK) == 0) return 0;
		return (boardArray[index] & PIECE_TYPE_MASK)-7;
	}
	// END pieceType()
	
	/**
	 * Takes an index and sets the piece type on that index
	 * used for pawn promotions
	 * 
	 * @param piece The piece to check
	 * @param newType The type to set it to
	 */
	public void setPieceTypeOnIndex(int index, int newType)
	{
		newType = (newType + 7) | (pieceUniqueOnIndex(index) << PIECE_UNIQUE_SHIFT);
		boardArray[index] = newType;
	}
	// END pieceType()


	/**
	 *  Returns a FEN-string without half-moves and full moves count
	 *
	 *  @return String Shorted FEN
	 */
	/*public String getShortFEN()
	{
	String fen_string = ""; // This holds the FEN-string

		// ***
		// The following lines adds the pieces and empty squares to the FEN
		// ***

		int index = 112; // Keeps track of the index on the board
		int empties = 0; // Number of empty squares in a row

		while (index >= 0) // Run until end of the real board
		{
			if((index & 0x88) != 0) // Reached the end of a rank
			{
				if(empties != 0)
				{
					fen_string += empties; // Add the empties number if it's not 0
					empties = 0;
				}
				index -= 24; // Jump to the next rank
				if(index >= 0) fen_string += "/"; // Add to mark a new rank, if we're not at the end
			}	      
			else // The index is on the real board
			{
				if(boardArray[index] != EMPTY_SQUARE) // If a piece is on the square
					// i.e. the square it not empty
				{
					if(empties != 0) fen_string += empties; // Add the empty square number
					// if it's not 0
					empties = 0; // Reset empties (since we now have a piece coming)
				}

				switch(boardArray[index])
				{
					// Add the piece on the square
					case W_KING: fen_string += "K";	break;
					case W_QUEEN: fen_string += "Q"; break;
					case W_ROOK: fen_string += "R";	break;
					case W_BISHOP: fen_string += "B"; break;
					case W_KNIGHT: fen_string += "N"; break;
					case W_PAWN: fen_string += "P"; break;
					case B_KING: fen_string += "k";	break;
					case B_QUEEN: fen_string += "q"; break;
					case B_ROOK: fen_string += "r"; break;
					case B_BISHOP: fen_string += "b"; break;
					case B_KNIGHT: fen_string += "n"; break;
					case B_PAWN: fen_string += "p";	break;
					default: empties++; // If no piece, increment the empty square count
				}
				index++; // Go to the next square
			}


		}

		// END Adding pieces
		
		fen_string += " "; // Add space for next part

		// Adds side to move (important space before the letter here)
		if(toMove == WHITE_TO_MOVE) fen_string += "w"; // White's move
		else fen_string += "b"; // Black's move

		fen_string += " "; // Add space for next part

		// Castling rights
		if(white_castle == CASTLE_NONE && black_castle == CASTLE_NONE) fen_string += "-"; // Neither
		else // Atleast one side can castle one way
		{
			switch(white_castle) // Check white's castling rights
			{
				case CASTLE_SHORT: fen_string += "K"; break;
				case CASTLE_LONG: fen_string += "Q"; break;
				case CASTLE_BOTH: fen_string += "KQ"; break;
			}

			switch(black_castle) // Check black's castling rights
			{
				case CASTLE_SHORT: fen_string += "k"; break;
				case CASTLE_LONG: fen_string += "q"; break;
				case CASTLE_BOTH: fen_string += "kq"; break;
			}
		}

		fen_string += " "; // Add space for next part

		// En passant square
		
		if(enPassant == -1) fen_string += "-"; // If no en passant is available
		else // An en passant is available
		{
			switch(enPassant%16) // Find the row
			{
				case 0: fen_string += "a"; break;
				case 1: fen_string += "b"; break;
				case 2: fen_string += "c"; break;
				case 3: fen_string += "d"; break;
				case 4: fen_string += "e"; break;
				case 5: fen_string += "f"; break;
				case 6: fen_string += "g"; break;
				case 7: fen_string += "h"; break;
				default: fen_string += "Error in ep square";
			}
			switch((enPassant-(enPassant%16))/16) // Find the rank
			{
				case 2: fen_string += "3"; break;
				case 5: fen_string += "6"; break;
				default: fen_string += "Error in ep square"; // Since en passants only can occur
					 				     // on 3rd and 6th rank, any other
									     // rank is an error
			}
		}

		return fen_string; // Returns the finished FEN-string
	}*/
	// END getShortFEN()


	/**
	 *  Sets the board to the starting position
	 *  rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1
	 */
	public void setupStart()
	{
		inputFEN("rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1");
		Zobrist.getZobristKey(this); // Get the inital zobrist key
	}
	// END setupStart()

	/**
	 *  Returns the current position in FEN-notation
	 *
	 *  @return A string with FEN-notation
	 */
	public String getFEN()
	{
		String fen_string = ""; // This holds the FEN-string

		// ***
		// The following lines adds the pieces and empty squares to the FEN
		// ***

		int index = 112; // Keeps track of the index on the board
		int empties = 0; // Number of empty squares in a row

		while (index >= 0) // Run until end of the real board
		{
			if((index & 0x88) != 0) // Reached the end of a rank
			{
				if(empties != 0)
				{
					fen_string += empties; // Add the empties number if it's not 0
					empties = 0;
				}
				index -= 24; // Jump to the next rank
				if(index >= 0) fen_string += "/"; // Add to mark a new rank, if we're not at the end
			}	      
			else // The index is on the real board
			{
				if(pieceTypeOnIndex(index) != EMPTY_SQUARE) // If a piece is on the square
					// i.e. the square it not empty
				{
					if(empties != 0) fen_string += empties; // Add the empty square number
					// if it's not 0
					empties = 0; // Reset empties (since we now have a piece coming)
				}

				switch(pieceTypeOnIndex(index))
				{
					// Add the piece on the square
					case W_KING: fen_string += "K";	break;
					case W_QUEEN: fen_string += "Q"; break;
					case W_ROOK: fen_string += "R";	break;
					case W_BISHOP: fen_string += "B"; break;
					case W_KNIGHT: fen_string += "N"; break;
					case W_PAWN: fen_string += "P"; break;
					case B_KING: fen_string += "k";	break;
					case B_QUEEN: fen_string += "q"; break;
					case B_ROOK: fen_string += "r"; break;
					case B_BISHOP: fen_string += "b"; break;
					case B_KNIGHT: fen_string += "n"; break;
					case B_PAWN: fen_string += "p";	break;
					default: empties++; // If no piece, increment the empty square count
				}
				index++; // Go to the next square
			}


		}

		// END Adding pieces
		
		fen_string += " "; // Add space for next part

		// Adds side to move (important space before the letter here)
		if(toMove == WHITE_TO_MOVE) fen_string += "w"; // White's move
		else fen_string += "b"; // Black's move

		fen_string += " "; // Add space for next part

		// Castling rights
		if(white_castle == CASTLE_NONE && black_castle == CASTLE_NONE) fen_string += "-"; // Neither
		else // Atleast one side can castle one way
		{
			switch(white_castle) // Check white's castling rights
			{
				case CASTLE_SHORT: fen_string += "K"; break;
				case CASTLE_LONG: fen_string += "Q"; break;
				case CASTLE_BOTH: fen_string += "KQ"; break;
			}

			switch(black_castle) // Check black's castling rights
			{
				case CASTLE_SHORT: fen_string += "k"; break;
				case CASTLE_LONG: fen_string += "q"; break;
				case CASTLE_BOTH: fen_string += "kq"; break;
			}
		}

		fen_string += " "; // Add space for next part

		// En passant square
		
		if(enPassant == -1) fen_string += "-"; // If no en passant is available
		else // An en passant is available
		{
			switch(enPassant%16) // Find the row
			{
				case 0: fen_string += "a"; break;
				case 1: fen_string += "b"; break;
				case 2: fen_string += "c"; break;
				case 3: fen_string += "d"; break;
				case 4: fen_string += "e"; break;
				case 5: fen_string += "f"; break;
				case 6: fen_string += "g"; break;
				case 7: fen_string += "h"; break;
				default: fen_string += "Error in ep square";
			}
			switch((enPassant-(enPassant%16))/16) // Find the rank
			{
				case 2: fen_string += "3"; break;
				case 5: fen_string += "6"; break;
				default: fen_string += "Error in ep square"; // Since en passants only can occur
					 				     // on 3rd and 6th rank, any other
									     // rank is an error
			}
		}

		fen_string += " "; // Add space for next part
		fen_string += movesFifty; // Add half-moves since last capture/pawn move
		fen_string += " ";
		fen_string += movesFull; // Add number of full moves in the game so far

		return fen_string; // Returns the finished FEN-string
	}
	// END getFEN()

	/**
	 *  Takes a FEN-string and sets the board accordingly
	 *
	 * @param String fen
	 */
	public void inputFEN(String fen)
	{
		historyIndex = 0; // Reset to make sure we start from the beginning
		String trimmedFen = fen.trim(); // Removes any white spaces in front or behind the string
		boardArray = new int[128]; // Empties the board from any pieces
		
		for(int i = 0; i <32; i++)
		{
			pieces[i] = -1; // Reset the piece table			
		}
		
		String currentChar; // Holds the current character in the fen

		int i = 0; // Used to go through the fen-string character by character

		int boardIndex = 112; // Keeps track of current index on the board (while adding pieces)
				      // Starts at "a8" (index 112) since the fen string starts on this square

		int currentStep = 0; // This will be incremented when a space is detected in the string
				     // 0 - Pieces
				     // 1 - Side to move
				     // 2 - Castling rights
				     // 3 - En passant square
				     // 4 - Half-moves (for 50 move rule) and full moves

		white_castle = CASTLE_NONE; // Resetting, will be changed below if castling rights are found
		black_castle = CASTLE_NONE;
		boolean fenFinished = false; // Set to true when we're at the end of the fen-string
		while(!fenFinished && i < trimmedFen.length())
		{
			currentChar = trimmedFen.substring(i,i+1); // Gets the current character from the fen-string

			// If a space is detected, get the next character, and move to next step
			if(" ".equals( currentChar )) 
			{
				i++;
				currentChar = trimmedFen.substring(i,i+1);
				currentStep++;
			}


			switch(currentStep) // Determine what step we're on
			{
				case 0: // Pieces
				{
					switch(currentChar.charAt(0)) // See what piece is on the square
					{
						// If character is a '/' move to first row on next rank
						case '/': boardIndex -= 24; break;

						// If the character is a piece, add it and move to next square
						case 'K':
							boardArray[boardIndex] = (W_KING+7) | (31 << PIECE_UNIQUE_SHIFT);
							pieces[31] = boardIndex;
							boardIndex++;
							break;
						case 'Q':
							
							if(pieces[30] == -1)
							{
								boardArray[boardIndex] = (W_QUEEN+7) | (30 << PIECE_UNIQUE_SHIFT);
								pieces[30] = boardIndex;
							}
							else
							{
								// More than one queen on one side so fill one of the pawn places with the index
								for(int q = 16; q < 24; q++)
								{
									if(pieces[q] == -1)
									{
										boardArray[boardIndex] = (W_QUEEN+7) | (q << PIECE_UNIQUE_SHIFT);
										pieces[q] = boardIndex;
										break;
									}									
								}
							}
							boardIndex++;
							break;
						case 'R':
							
							if(pieces[29] == -1)
							{
								boardArray[boardIndex] = (W_ROOK+7) | (29 << PIECE_UNIQUE_SHIFT);
								pieces[29] = boardIndex;
							}
							else if(pieces[28] == -1)
							{
								boardArray[boardIndex] = (W_ROOK+7) | (28 << PIECE_UNIQUE_SHIFT);
								pieces[28] = boardIndex;
							}
							else
							{
								// More than two rooks on one side so fill one of the pawn places with the index
								for(int q = 16; q < 24; q++)
								{
									if(pieces[q] == -1)
									{
										boardArray[boardIndex] = (W_ROOK+7) | (q << PIECE_UNIQUE_SHIFT);
										pieces[q] = boardIndex;
										break;
									}	
								}
							}															
							boardIndex++;
							break;
						case 'B':
							
							if(pieces[27] == -1)
							{
								boardArray[boardIndex] = (W_BISHOP+7) | (27 << PIECE_UNIQUE_SHIFT);
								pieces[27] = boardIndex;
							}
							else if(pieces[26] == -1)
							{
								boardArray[boardIndex] = (W_BISHOP+7) | (26 << PIECE_UNIQUE_SHIFT);
								pieces[26] = boardIndex;
							}
							else
							{
								// More than two bishops on one side so fill one of the pawn places with the index
								for(int q = 16; q < 24; q++)
								{
									if(pieces[q] == -1)
									{
										boardArray[boardIndex] = (W_BISHOP+7) | (q << PIECE_UNIQUE_SHIFT);
										pieces[q] = boardIndex;
										break;
									}	
								}
							}
							boardIndex++;
							break;
						case 'N':
							
							if(pieces[25] == -1)
							{
								boardArray[boardIndex] = (W_KNIGHT+7) | (25 << PIECE_UNIQUE_SHIFT);
								pieces[25] = boardIndex;
							}
							else if(pieces[24] == -1)
							{
								boardArray[boardIndex] = (W_KNIGHT+7) | (24 << PIECE_UNIQUE_SHIFT);
								pieces[24] = boardIndex;
							}
							else
							{
								// More than two knights on one side so fill one of the pawn places with the index
								for(int q = 16; q < 24; q++)
								{
									if(pieces[q] == -1)
									{
										boardArray[boardIndex] = (W_KNIGHT+7) | (q << PIECE_UNIQUE_SHIFT);
										pieces[q] = boardIndex;
										break;
									}	
								}
							}
							boardIndex++;
							break;
						case 'P':
							
							for(int q = 16; q < 24; q++)
							{
								if(pieces[q] == -1)
								{
									boardArray[boardIndex] = (W_PAWN+7) | (q << PIECE_UNIQUE_SHIFT);
									pieces[q] = boardIndex;
									break;
								}	
							}

							boardIndex++;
							break;
						case 'k':
							boardArray[boardIndex] = (B_KING+7) | (15 << PIECE_UNIQUE_SHIFT);
							pieces[15] = boardIndex;
							boardIndex++;
							break;
						case 'q':
							
							if(pieces[14] == -1)
							{
								boardArray[boardIndex] = (B_QUEEN+7) | (14 << PIECE_UNIQUE_SHIFT);
								pieces[14] = boardIndex;
							}
							else
							{
								for(int q = 0; q < 8; q++)
								{
									if(pieces[q] == -1)
									{
										boardArray[boardIndex] = (B_QUEEN+7) | (q << PIECE_UNIQUE_SHIFT);
										pieces[q] = boardIndex;
										break;
									}	
								}
							}
							boardIndex++;
							break;
						case 'r':
							
							if(pieces[13] == -1)
							{
								boardArray[boardIndex] = (B_ROOK+7) | (13 << PIECE_UNIQUE_SHIFT);
								pieces[13] = boardIndex;
							}
							else if(pieces[12] == -1)
							{
								boardArray[boardIndex] = (B_ROOK+7) | (12 << PIECE_UNIQUE_SHIFT);
								pieces[12] = boardIndex;
							}
							else
							{
								for(int q = 0; q < 8; q++)
								{
									if(pieces[q] == -1)
									{
										boardArray[boardIndex] = (B_ROOK+7) | (q << PIECE_UNIQUE_SHIFT);
										pieces[q] = boardIndex;
										break;
									}	
								}
							}
							boardIndex++;
							break;
						case 'b':
							
							if(pieces[11] == -1)
							{
								boardArray[boardIndex] = (B_BISHOP+7) | (11 << PIECE_UNIQUE_SHIFT);
								pieces[11] = boardIndex;
							}
							else if(pieces[10] == -1)
							{
								boardArray[boardIndex] = (B_BISHOP+7) | (10 << PIECE_UNIQUE_SHIFT);
								pieces[10] = boardIndex;
							}
							else
							{
								for(int q = 0; q < 8; q++)
								{
									if(pieces[q] == -1)
									{
										boardArray[boardIndex] = (B_BISHOP+7) | (q << PIECE_UNIQUE_SHIFT);
										pieces[q] = boardIndex;
										break;
									}	
								}
							}
							boardIndex++;
							break;
						case 'n':
							
							if(pieces[9] == -1)
							{
								boardArray[boardIndex] = (B_KNIGHT+7) | (9 << PIECE_UNIQUE_SHIFT);
								pieces[9] = boardIndex;
							}
							else if(pieces[8] == -1)
							{
								boardArray[boardIndex] = (B_KNIGHT+7) | (8 << PIECE_UNIQUE_SHIFT);
								pieces[8] = boardIndex;
							}
							else
							{
								for(int q = 0; q < 8; q++)
								{
									if(pieces[q] == -1)
									{
										boardArray[boardIndex] = (B_KNIGHT+7) | (q << PIECE_UNIQUE_SHIFT);
										pieces[q] = boardIndex;
										break;
									}	
								}
							}
							boardIndex++;
							break;
						case 'p':
							
							for(int q = 0; q < 8; q++)
							{
								if(pieces[q] == -1)
								{
									boardArray[boardIndex] = (B_PAWN+7) | (q << PIECE_UNIQUE_SHIFT);
									pieces[q] = boardIndex;
									break;
								}	
							}
							boardIndex++;
							break;

						// If no piece was found, it has to be a number of empty squares
						// so move to that board index
						default: boardIndex += Integer.parseInt(currentChar);
					}
					break;
				}
				case 1: // Side to move
				{
					if("w".equals( currentChar )) toMove = WHITE_TO_MOVE;
					else toMove = BLACK_TO_MOVE;
					break;
				}
				case 2: // Castling rights
				{
					// '-' states that no castling is available so we simply keep the values
					// we set before the while-loop, and don't need to do anything here.
					switch(currentChar.charAt(0))
					{
						// White can atleast castle short
						case 'K': white_castle = CASTLE_SHORT; break;

						case 'Q': // White can atleast castle long
						{
							// If white already can castle short, do both, else only long
							if(white_castle == CASTLE_SHORT) white_castle = CASTLE_BOTH;
							else white_castle = CASTLE_LONG;
							break;
						}
						// Black can atleast castle short
						case 'k': black_castle = CASTLE_SHORT; break;

						case 'q': // Black can atleast castle long
						{
							// If black already can castle short, do both, else only long
							if(black_castle == CASTLE_SHORT) black_castle = CASTLE_BOTH;
							else black_castle = CASTLE_LONG;
							break;
						}
					}
					break;					
				}
				case 3: // En passant
				{
					if("-".equals( currentChar )) enPassant = -1;
					else
					{
						switch(currentChar.charAt(0)) // Find the row
						{
							case 'a': enPassant = 0; break;
							case 'b': enPassant = 1; break;
							case 'c': enPassant = 2; break;
							case 'd': enPassant = 3; break;
							case 'e': enPassant = 4; break;
							case 'f': enPassant = 5; break;
							case 'g': enPassant = 6; break;
							case 'h': enPassant = 7; break;
						}
						// Get the next character (the rank)
						i++;
						currentChar = trimmedFen.substring(i,i+1);

						// On rank 3 or else rank 6
						if("3".equals( currentChar )) enPassant += 32; // Add 2 ranks to index
						else enPassant += 80; // Add 5 ranks to index
					}
					break;
				}
				case 4: // Half-moves (50 move rule) and full moves
				{
					// If the next character is a space, we're done with half-moves and
					// can insert them
					if(" ".equals( trimmedFen.substring(i + 1,i + 2) ))
					{
						movesFifty = Integer.parseInt(currentChar);
					}
					// If the next character is not a space, we know it's a number
					// and since half-moves can't be higher than 50 (or it can, but the game
					// is drawn so there's not much point to it), we can assume
					// there are two numbers and then we're done with half-moves.
					else
					{
						movesFifty = Integer.parseInt(trimmedFen.substring(i,i+2));
						i++;
					}
					i += 2;
					movesFull = Integer.parseInt(trimmedFen.substring(i));
					fenFinished = true; // We're done with the fen-string and can exit the loop
					break;
				}
			}
			i++; // Move to the next character in the fen-string
		}		
		zobristKey = Zobrist.getZobristKey(this); // The board is now setup so we can get the inital zobrist key
	}
	// END inputFEN()
	
	/**
	 * Takes an integer array and fills it with possible legal moves
	 * starting at the startIndex, if onlyCaptures is true it only
	 * fills the array with captures, else all legal moves
	 * 
	 * @param onlyCaptures Should we only get captures
	 * @param moves The array to fill
	 * @param startIndex The index we start to fill the array from
	 * @return totalMoves The total number of moves that were inserted in the array
	 */
	public int generateMoves(boolean onlyCaptures, int[] moves, int startIndex)
	{
		int totalMoves = generatePseudoMoves(moves, startIndex);
		if(onlyCaptures)
		{
			totalMoves = filterQuis(moves, startIndex, (startIndex + totalMoves));
		}
		else
		{
			totalMoves = filterMoves(moves, startIndex, (startIndex + totalMoves));
		}
		return totalMoves;
	}
	// END getLegalMoves()
	
	/**
	 * Filters out the illegal move (leaving king in check etc), also filters
	 * out non-captures
	 * 
	 * Also puts a preliminary value of the capture (used for MVA/LVV)
	 * 
	 * @param pseudoMoves The array to filter
	 * @param startIndex Index we start filtering from
	 * @param endIndex The index we end filtering at
	 * @return totalMoves The total number of moves left when filtering is done
	 */
	private int filterQuis(int[] pseudoMoves, int startIndex, int endIndex)
	{
		int totalMoves = 0;

		int king_square;		
		if(toMove == WHITE_TO_MOVE) king_square = pieces[31];
		else king_square = pieces[15];

		boolean willBeAdded;
		
		// Now go through every move
		for(int i = startIndex; i < endIndex; i++)
		{
			willBeAdded = false; // Start with assuming the move will not be added
			int currentMove = pseudoMoves[i]; // Get a move from the vector

			if(Move.capture(currentMove) != 0)
			{

				makeMove(currentMove); // Make the move on the board

				// We have already determined the king square, but if the king
				// is moving we need to call isAttacked with its new square
				// and not where it stood before
				if(Move.pieceMoving(currentMove) == W_KING || Move.pieceMoving(currentMove) == B_KING)
				{
					if(!isAttacked(Move.toIndex(currentMove)))
						willBeAdded = true;
				}
				// If it's not the king moving, we use where it's standing as
				// determined before
				else
				{
					// If the king can't be attacked add the move
					if(!isAttacked(king_square))
						willBeAdded = true;
				}

				unmakeMove(currentMove); // Unmake the move to reset the board


				if(willBeAdded) // The move passed the checks and will be added
				{
					// TODO Add non-capture ordering values depending on where the piece moves to
					// use the board in Definitions for this

					// See what type of move it is and give it an orderingValue
					// Give capture points
					if(Move.capture(currentMove) != 0) // If the move is a capture
					{
						switch(Math.abs(Move.capture(currentMove)))
						{
						case W_QUEEN:
						{
							switch(Math.abs(Move.pieceMoving(currentMove)))
							{
							case W_PAWN: currentMove = Move.setOrderingValue(currentMove, 30); break;
							case W_KNIGHT: currentMove = Move.setOrderingValue(currentMove, 29); break;
							case W_BISHOP: currentMove = Move.setOrderingValue(currentMove, 28); break;
							case W_ROOK: currentMove = Move.setOrderingValue(currentMove, 27); break;
							case W_QUEEN: currentMove = Move.setOrderingValue(currentMove, 26); break;
							case W_KING: currentMove = Move.setOrderingValue(currentMove, 25); break;
							}
							break;
						}
						case W_ROOK:
						{
							switch(Math.abs(Move.pieceMoving(currentMove)))
							{
							case W_PAWN: currentMove = Move.setOrderingValue(currentMove, 24); break;
							case W_KNIGHT: currentMove = Move.setOrderingValue(currentMove, 23); break;
							case W_BISHOP: currentMove = Move.setOrderingValue(currentMove, 22); break;
							case W_ROOK: currentMove = Move.setOrderingValue(currentMove, 21); break;
							case W_QUEEN: currentMove = Move.setOrderingValue(currentMove, 20); break;
							case W_KING: currentMove = Move.setOrderingValue(currentMove, 19); break;
							}
							break;
						}
						case W_BISHOP:
						{
							switch(Math.abs(Move.pieceMoving(currentMove)))
							{
							case W_PAWN: currentMove = Move.setOrderingValue(currentMove, 18); break;
							case W_KNIGHT: currentMove = Move.setOrderingValue(currentMove, 17); break;
							case W_BISHOP: currentMove = Move.setOrderingValue(currentMove, 16); break;
							case W_ROOK: currentMove = Move.setOrderingValue(currentMove, 15); break;
							case W_QUEEN: currentMove = Move.setOrderingValue(currentMove, 14); break;
							case W_KING: currentMove = Move.setOrderingValue(currentMove, 13); break;
							}
							break;
						}
						case W_KNIGHT:
						{
							switch(Math.abs(Move.pieceMoving(currentMove)))
							{
							case W_PAWN: currentMove = Move.setOrderingValue(currentMove, 12); break;
							case W_KNIGHT: currentMove = Move.setOrderingValue(currentMove, 11); break;
							case W_BISHOP: currentMove = Move.setOrderingValue(currentMove, 10); break;
							case W_ROOK: currentMove = Move.setOrderingValue(currentMove, 9); break;
							case W_QUEEN: currentMove = Move.setOrderingValue(currentMove, 8); break;
							case W_KING: currentMove = Move.setOrderingValue(currentMove, 7); break;
							}
							break;
						}
						case W_PAWN:
						{
							switch(Math.abs(Move.pieceMoving(currentMove)))
							{
							case W_PAWN: currentMove = Move.setOrderingValue(currentMove, 6); break;
							case W_KNIGHT: currentMove = Move.setOrderingValue(currentMove, 5); break;
							case W_BISHOP: currentMove = Move.setOrderingValue(currentMove, 4); break;
							case W_ROOK: currentMove = Move.setOrderingValue(currentMove, 3); break;
							case W_QUEEN: currentMove = Move.setOrderingValue(currentMove, 2); break;
							case W_KING: currentMove = Move.setOrderingValue(currentMove, 1); break;
							}
							break;
						}					
						}
						
						pseudoMoves[i] = 0; // Empty the spot it had
						pseudoMoves[startIndex + totalMoves] = currentMove; // Move it to its new spot (might be the same)
						totalMoves++;
					}
				}
				else
				{
					pseudoMoves[i] = 0; // Empty the spot since the move is illegal
				}
			}
			else
			{
				pseudoMoves[i] = 0; // Empty the spot since the move is not a capture
			}
			
		}
			

		return totalMoves; // We are now done and can return the filtered moves
	}
	//END filterQuis()
	
	/**
	 * Filters out the illegal move (leaving king in check etc)
	 * 
	 * Also sets a preliminary value if the move is a capture
	 * 
	 * @param pseudoMoves The array to filter
	 * @param startIndex Index we start filtering from
	 * @param endIndex The index we end filtering at
	 * @return totalMoves The total number of moves left when filtering is done
	 */
	private int filterMoves(int[] pseudoMoves, int startIndex, int endIndex)
	{
		
		int totalMoves = 0;

		int king_square;		
		if(toMove == WHITE_TO_MOVE) king_square = pieces[31];
		else king_square = pieces[15];
		
		boolean willBeAdded;
		// Now go through every move
		for(int i = startIndex; i < endIndex; i++)
		{
			willBeAdded = false; // Start with assuming the move will not be added
			int currentMove = pseudoMoves[i]; // Get a move from the vector

			// TODO: Maybe extract all the values from the move and set them to separate integers first instead of calling Move each time, probably little gain though
			
			// If the move is a castle we also need to check for castling in check
			// and over attacked squares, so check the type of move
			switch(Move.moveType(currentMove))
			{
				case SHORT_CASTLE:
				{
					makeMove(currentMove); // Make the move on the board

					// Now check if the king's original square or the two to the right
					// are attacked.
					// This catches all three posibilities; castle in check, castle over
					// attacked square and castle into check.
					//
					// If neither is attacked we can add it to legal moves.
					if(!isAttacked(Move.fromIndex(currentMove))     &&
					   !isAttacked(Move.fromIndex(currentMove) + 1) &&
					   !isAttacked(Move.fromIndex(currentMove) + 2))
						willBeAdded = true;

					unmakeMove(currentMove); // Unmake the move to reset the board
					break;
				}
				case LONG_CASTLE:
				{
					makeMove(currentMove); // Make the move on the board

					// Now check if the king's original square or the two to the left
					// are attacked.
					// This catches all three posibilities; castle in check, castle over
					// attacked square and castle into check.
					//
					// If neither is attacked we can add it to legal moves.
					if(!isAttacked(Move.fromIndex(currentMove))     &&
					   !isAttacked(Move.fromIndex(currentMove) - 1) &&
					   !isAttacked(Move.fromIndex(currentMove) - 2))
						willBeAdded = true;

					unmakeMove(currentMove); // Unmake the move to reset the board
					break;
				}				

				default: // Catches all other types of moves
				{
					makeMove(currentMove); // Make the move on the board

					// We have already determined the king square, but if the king
					// is moving we need to call isAttacked with its new square
					// and not where it stood before
					if(Move.pieceMoving(currentMove) == W_KING || Move.pieceMoving(currentMove) == B_KING)
					{
						if(!isAttacked(Move.toIndex(currentMove)))
							willBeAdded = true;
					}
					// If it's not the king moving, we use where it's standing as
					// determined before
					else
					{
						// If the king can't be attacked add the move
						if(!isAttacked(king_square))
							willBeAdded = true;
					}

					unmakeMove(currentMove); // Unmake the move to reset the board
				}
			}

			if(willBeAdded) // The move passed the checks and will be added
			{
				// TODO Add non-capture ordering values depending on where the piece moves to
				// use the board in Definitions for this


				// Give capture points
				if(Move.capture(currentMove) != 0) // If the move is a capture
				{
					switch(Math.abs(Move.capture(currentMove)))
					{
					case W_QUEEN:
					{
						switch(Math.abs(Move.pieceMoving(currentMove)))
						{
						case W_PAWN: currentMove = Move.setOrderingValue(currentMove, 30); break;
						case W_KNIGHT: currentMove = Move.setOrderingValue(currentMove, 29); break;
						case W_BISHOP: currentMove = Move.setOrderingValue(currentMove, 28); break;
						case W_ROOK: currentMove = Move.setOrderingValue(currentMove, 27); break;
						case W_QUEEN: currentMove = Move.setOrderingValue(currentMove, 26); break;
						case W_KING: currentMove = Move.setOrderingValue(currentMove, 25); break;
						}
						break;
					}
					case W_ROOK:
					{
						switch(Math.abs(Move.pieceMoving(currentMove)))
						{
						case W_PAWN: currentMove = Move.setOrderingValue(currentMove, 24); break;
						case W_KNIGHT: currentMove = Move.setOrderingValue(currentMove, 23); break;
						case W_BISHOP: currentMove = Move.setOrderingValue(currentMove, 22); break;
						case W_ROOK: currentMove = Move.setOrderingValue(currentMove, 21); break;
						case W_QUEEN: currentMove = Move.setOrderingValue(currentMove, 20); break;
						case W_KING: currentMove = Move.setOrderingValue(currentMove, 19); break;
						}
						break;
					}
					case W_BISHOP:
					{
						switch(Math.abs(Move.pieceMoving(currentMove)))
						{
						case W_PAWN: currentMove = Move.setOrderingValue(currentMove, 18); break;
						case W_KNIGHT: currentMove = Move.setOrderingValue(currentMove, 17); break;
						case W_BISHOP: currentMove = Move.setOrderingValue(currentMove, 16); break;
						case W_ROOK: currentMove = Move.setOrderingValue(currentMove, 15); break;
						case W_QUEEN: currentMove = Move.setOrderingValue(currentMove, 14); break;
						case W_KING: currentMove = Move.setOrderingValue(currentMove, 13); break;
						}
						break;
					}
					case W_KNIGHT:
					{
						switch(Math.abs(Move.pieceMoving(currentMove)))
						{
						case W_PAWN: currentMove = Move.setOrderingValue(currentMove, 12); break;
						case W_KNIGHT: currentMove = Move.setOrderingValue(currentMove, 11); break;
						case W_BISHOP: currentMove = Move.setOrderingValue(currentMove, 10); break;
						case W_ROOK: currentMove = Move.setOrderingValue(currentMove, 9); break;
						case W_QUEEN: currentMove = Move.setOrderingValue(currentMove, 8); break;
						case W_KING: currentMove = Move.setOrderingValue(currentMove, 7); break;
						}
						break;
					}
					case W_PAWN:
					{
						switch(Math.abs(Move.pieceMoving(currentMove)))
						{
						case W_PAWN: currentMove = Move.setOrderingValue(currentMove, 6); break;
						case W_KNIGHT: currentMove = Move.setOrderingValue(currentMove, 5); break;
						case W_BISHOP: currentMove = Move.setOrderingValue(currentMove, 4); break;
						case W_ROOK: currentMove = Move.setOrderingValue(currentMove, 3); break;
						case W_QUEEN: currentMove = Move.setOrderingValue(currentMove, 2); break;
						case W_KING: currentMove = Move.setOrderingValue(currentMove, 1); break;
						}
						break;
					}					
					}
				}

				// TODO: See if we can use the sortMoves() from Engine here instead somehow

				pseudoMoves[i] = 0; // Empty the spot it had
				pseudoMoves[startIndex + totalMoves] = currentMove; // Move it to its new spot (might be the same)
				totalMoves++;

			}
			else
			{
				pseudoMoves[i] = 0; // Empty the spot since the move is illegal
			}
		}
			

		return totalMoves; // We are now done and can return the filtered moves
	}
	// END filterMoves()
	
	/**
	 * Fills the array with all pseudo-legal moves from the startIndex
	 *
	 * @param pseudoMoves The array to fill
	 * @param startIndex The index to start filling at
	 * @return totalMoves Number of moves that were added
	 */
	private int generatePseudoMoves(int[] pseudoMoves, int startIndex)
	{
		int totalMoves = 0;
		for(int piecesIndex = 0; piecesIndex < 32; piecesIndex++) // Move through all squares on the board
		{
			int index = pieces[piecesIndex];
			if(index != -1)
			{
				switch(pieceTypeOnIndex(index) * toMove) // Check the square, if black on the move, we check for
							       // negative values (*(-1)) i.e. black pieces
							       // So a -5 (black knight) will be 'transformed' into
							       // a white knight momentarily and be catched below
				{
					case EMPTY_SQUARE: break; // Do nothing on empty squares

					case W_QUEEN: totalMoves += genMoves(index, queen_delta, true, pseudoMoves, (startIndex + totalMoves)); break;
					case W_ROOK: totalMoves += genMoves(index, rook_delta, true, pseudoMoves, (startIndex + totalMoves)); break;
					case W_BISHOP: totalMoves += genMoves(index, bishop_delta, true, pseudoMoves, (startIndex + totalMoves)); break;
					case W_KNIGHT: totalMoves += genMoves(index, knight_delta, false, pseudoMoves, (startIndex + totalMoves)); break;
					case W_KING: 
						       {
						    	   totalMoves += genMoves(index, king_delta, false, pseudoMoves, (startIndex + totalMoves));
						    	   totalMoves += genCastling(pseudoMoves, (startIndex + totalMoves));
							       break; 
						       }
					case W_PAWN: totalMoves += genPawn(index, pseudoMoves, (startIndex + totalMoves)); break;
				}
			}
		}
		
		return totalMoves;
	}
	// END generatePseudoMoves()
	
	/**
	 *  Adds all possible moves for the pawn
	 *
	 *  @param index Index the piece is on 
	 *  @param pseudoMoves The array to add the moves to
	 *  @param startIndex Index to start filling at
	 *  @return totalMovesAdded Number of moves that were added to the array
	 */
	private int genPawn(int index, int[] pseudoMoves, int startIndex)
	{
		int totalMovesAdded = 0;

		if(toMove == WHITE_TO_MOVE)
		{
			if(pieceTypeOnIndex(index + 16) == EMPTY_SQUARE)// If next square is empty we can move there
			{
				if((index-(index%16))/16 != 6) // If the pawn is not on 7th rank
				{
					// Add ordinary pawn move
					pseudoMoves[startIndex + totalMovesAdded] = Move.createMove(W_PAWN, index, (index+16), 0, ORDINARY_MOVE, 0);
					totalMovesAdded++;
				}
				else // Add promotion if on 7th rank
				{
					pseudoMoves[startIndex + totalMovesAdded] = Move.createMove(W_PAWN, index, (index+16), 0, PROMOTION_QUEEN, 0);
					totalMovesAdded++;
					pseudoMoves[startIndex + totalMovesAdded] = Move.createMove(W_PAWN, index, (index+16), 0, PROMOTION_ROOK, 0);
					totalMovesAdded++;
					pseudoMoves[startIndex + totalMovesAdded] = Move.createMove(W_PAWN, index, (index+16), 0, PROMOTION_BISHOP, 0);
					totalMovesAdded++;
					pseudoMoves[startIndex + totalMovesAdded] = Move.createMove(W_PAWN, index, (index+16), 0, PROMOTION_KNIGHT, 0);
					totalMovesAdded++;
				}
			}


			// If next square diagonally left contains a opposite side piece,
			// it's possible to capture
			if(((index + 15) & 0x88) == 0 && pieceTypeOnIndex(index + 15) < 0)
			{
				if((index-(index%16))/16 != 6) // If not on 7th rank
				{	
					// Add ordinary pawn move			
					pseudoMoves[startIndex + totalMovesAdded] = Move.createMove(W_PAWN, index, index+15, pieceTypeOnIndex(index+15), ORDINARY_MOVE, 0);
					totalMovesAdded++;
				}
				else // Add promotion if on 7th rank
				{

					pseudoMoves[startIndex + totalMovesAdded] = Move.createMove(W_PAWN, index, index+15, pieceTypeOnIndex(index+15), PROMOTION_QUEEN, 0);
					totalMovesAdded++;
					pseudoMoves[startIndex + totalMovesAdded] = Move.createMove(W_PAWN, index, index+15, pieceTypeOnIndex(index+15), PROMOTION_ROOK, 0);
					totalMovesAdded++;
					pseudoMoves[startIndex + totalMovesAdded] = Move.createMove(W_PAWN, index, index+15, pieceTypeOnIndex(index+15), PROMOTION_BISHOP, 0);
					totalMovesAdded++;
					pseudoMoves[startIndex + totalMovesAdded] = Move.createMove(W_PAWN, index, index+15, pieceTypeOnIndex(index+15), PROMOTION_KNIGHT, 0);
					totalMovesAdded++;
				}
			}
			// If next square diagonally right contains a opposite side piece,
			// it's possible to capture
			if(((index + 17) & 0x88) == 0 && pieceTypeOnIndex(index + 17) < 0)
			{
				if((index-(index%16))/16 != 6) // If not on 7th rank
				{
					// Add ordinary pawn move			
					pseudoMoves[startIndex + totalMovesAdded] = Move.createMove(W_PAWN, index, index+17, pieceTypeOnIndex(index+17), ORDINARY_MOVE, 0);
					totalMovesAdded++;
				}
				else // Add promotion if on 7th rank
				{

					pseudoMoves[startIndex + totalMovesAdded] = Move.createMove(W_PAWN, index, index+17, pieceTypeOnIndex(index+17), PROMOTION_QUEEN, 0);
					totalMovesAdded++;
					pseudoMoves[startIndex + totalMovesAdded] = Move.createMove(W_PAWN, index, index+17, pieceTypeOnIndex(index+17), PROMOTION_ROOK, 0);
					totalMovesAdded++;
					pseudoMoves[startIndex + totalMovesAdded] = Move.createMove(W_PAWN, index, index+17, pieceTypeOnIndex(index+17), PROMOTION_BISHOP, 0);
					totalMovesAdded++;
					pseudoMoves[startIndex + totalMovesAdded] = Move.createMove(W_PAWN, index, index+17, pieceTypeOnIndex(index+17), PROMOTION_KNIGHT, 0);
					totalMovesAdded++;
				}
			}	
			// If the pawn is standing on its original square (rank 2)
			// it is possible to move two squares if both squares in front of it are empty
			if(((index-(index%16))/16 == 1) && (pieceTypeOnIndex(index + 16) == EMPTY_SQUARE) && (pieceTypeOnIndex(index + 32) == EMPTY_SQUARE))
			{
				pseudoMoves[startIndex + totalMovesAdded] = Move.createMove(W_PAWN, index, index+32, 0, ORDINARY_MOVE, 0);
				totalMovesAdded++;
				
			}

			// If there is an en passant square and the pawn can reach it
			// we can add en passant
			
			if(enPassant != -1 && ((index-(index%16))/16) == 4 && (index+17 == enPassant || index+15 == enPassant))
			{
				pseudoMoves[startIndex + totalMovesAdded] = Move.createMove(W_PAWN, index, enPassant, B_PAWN, EN_PASSANT, 0);
				totalMovesAdded++;
			}



		}

		else // Black's move
		{
			if(pieceTypeOnIndex(index - 16) == EMPTY_SQUARE)// If next square is empty we can move there
			{
				if((index-(index%16))/16 != 1) // If the pawn is not on 2nd rank
				{
					// Add ordinary pawn move
					pseudoMoves[startIndex + totalMovesAdded] = Move.createMove(B_PAWN, index, index-16, 0, ORDINARY_MOVE, 0);
					totalMovesAdded++;
				}
				else // Add promotion if on 7th rank
				{
					pseudoMoves[startIndex + totalMovesAdded] = Move.createMove(B_PAWN, index, index-16, 0, PROMOTION_QUEEN, 0);
					totalMovesAdded++;
					pseudoMoves[startIndex + totalMovesAdded] = Move.createMove(B_PAWN, index, index-16, 0, PROMOTION_ROOK, 0);
					totalMovesAdded++;
					pseudoMoves[startIndex + totalMovesAdded] = Move.createMove(B_PAWN, index, index-16, 0, PROMOTION_BISHOP, 0);
					totalMovesAdded++;
					pseudoMoves[startIndex + totalMovesAdded] = Move.createMove(B_PAWN, index, index-16, 0, PROMOTION_KNIGHT, 0);
					totalMovesAdded++;
				}
			}


			// If next square diagonally left contains a opposite side piece,
			// it's possible to capture
			if(((index - 15) & 0x88) == 0 && pieceTypeOnIndex(index - 15) > 0)
			{
				if((index-(index%16))/16 != 1) // If not on 2nd rank
				{	
					// Add ordinary pawn move
					pseudoMoves[startIndex + totalMovesAdded] = Move.createMove(B_PAWN, index, index-15, pieceTypeOnIndex(index-15), ORDINARY_MOVE, 0);
					totalMovesAdded++;
				}
				else // Add promotion if on 7th rank
				{
					pseudoMoves[startIndex + totalMovesAdded] = Move.createMove(B_PAWN, index, index-15, pieceTypeOnIndex(index-15), PROMOTION_QUEEN, 0);
					totalMovesAdded++;
					pseudoMoves[startIndex + totalMovesAdded] = Move.createMove(B_PAWN, index, index-15, pieceTypeOnIndex(index-15), PROMOTION_ROOK, 0);
					totalMovesAdded++;
					pseudoMoves[startIndex + totalMovesAdded] = Move.createMove(B_PAWN, index, index-15, pieceTypeOnIndex(index-15), PROMOTION_BISHOP, 0);
					totalMovesAdded++;
					pseudoMoves[startIndex + totalMovesAdded] = Move.createMove(B_PAWN, index, index-15, pieceTypeOnIndex(index-15), PROMOTION_KNIGHT, 0);
					totalMovesAdded++;
				}
			}
			// If next square diagonally right contains a opposite side piece,
			// it's possible to capture
			if(((index - 17) & 0x88) == 0 && pieceTypeOnIndex(index - 17) > 0)
			{
				if((index-(index%16))/16 != 1) // If not on 2nd rank
				{
					// Add ordinary pawn move
					pseudoMoves[startIndex + totalMovesAdded] = Move.createMove(B_PAWN, index, index-17, pieceTypeOnIndex(index-17), ORDINARY_MOVE, 0);
					totalMovesAdded++;
				}
				else // Add promotion if on 7th rank
				{
					pseudoMoves[startIndex + totalMovesAdded] = Move.createMove(B_PAWN, index, index-17, pieceTypeOnIndex(index-17), PROMOTION_QUEEN, 0);
					totalMovesAdded++;
					pseudoMoves[startIndex + totalMovesAdded] = Move.createMove(B_PAWN, index, index-17, pieceTypeOnIndex(index-17), PROMOTION_ROOK, 0);
					totalMovesAdded++;
					pseudoMoves[startIndex + totalMovesAdded] = Move.createMove(B_PAWN, index, index-17, pieceTypeOnIndex(index-17), PROMOTION_BISHOP, 0);
					totalMovesAdded++;
					pseudoMoves[startIndex + totalMovesAdded] = Move.createMove(B_PAWN, index, index-17, pieceTypeOnIndex(index-17), PROMOTION_KNIGHT, 0);
					totalMovesAdded++;
				}
			}	
			// If the pawn is standing on its original square (rank 7)
			// it is possible to move two squares if both squares in front of it are empty
			if(((index-(index%16))/16 == 6) && (pieceTypeOnIndex(index - 16) == EMPTY_SQUARE) && (pieceTypeOnIndex(index - 32) == EMPTY_SQUARE))
			{
				pseudoMoves[startIndex + totalMovesAdded] = Move.createMove(B_PAWN, index, index-32, 0, ORDINARY_MOVE, 0);
				totalMovesAdded++;
			}
			

			// If there is an en passant square and the pawn can reach it
			// we can add en passant
			
			if(enPassant != -1 && ((index-(index%16))/16) == 3 && (index-17 == enPassant || index-15 == enPassant))
			{
				pseudoMoves[startIndex + totalMovesAdded] = Move.createMove(B_PAWN, index, enPassant, W_PAWN, EN_PASSANT, 0);
				totalMovesAdded++;
			}
		}
		
		return totalMovesAdded;
	}
	// END genPawn()
	
	
	/**
	 *  Checks if castling is available for the king and adds the move if it is
	 *
	 *  @param pseudoMoves The array to add the moves to
	 *  @param startIndex The index where to start adding moves
	 *  @return totalMovesAdded Number of moves that were added
	 */
	private int genCastling(int[] pseudoMoves, int startIndex)
	{
		int totalMovesAdded = 0;
		if(toMove == WHITE_TO_MOVE) // White king moving
		{
			switch(white_castle)
			{
				case CASTLE_NONE: break; // No castling
				case CASTLE_SHORT:
				{
					// If squares between king and rook are empty, add short castle
					if((pieceTypeOnIndex(5) == EMPTY_SQUARE) && (pieceTypeOnIndex(6) == EMPTY_SQUARE))
					{
						pseudoMoves[startIndex + totalMovesAdded] = Move.createMove(W_KING, 4, 6, 0, SHORT_CASTLE, 0);
						totalMovesAdded++;
					}
					break;
				}
				case CASTLE_LONG:
				{
					// If squares between king and rook are empty, add long castle
					if((pieceTypeOnIndex(1) == EMPTY_SQUARE) && (pieceTypeOnIndex(2) == EMPTY_SQUARE) && (pieceTypeOnIndex(3) == EMPTY_SQUARE))
					{
						pseudoMoves[startIndex + totalMovesAdded] = Move.createMove(W_KING, 4, 2, 0, LONG_CASTLE, 0);
						totalMovesAdded++;
					}
					break;
				}
				default: // Can castle both ways
				{
					// If squares between king and rook are empty, add short castle
					if((pieceTypeOnIndex(5) == EMPTY_SQUARE) && (pieceTypeOnIndex(6) == EMPTY_SQUARE))
					{
						pseudoMoves[startIndex + totalMovesAdded] = Move.createMove(W_KING, 4, 6, 0, SHORT_CASTLE, 0);
						totalMovesAdded++;
					}
					// If squares between king and rook are empty, add long castle
					if((pieceTypeOnIndex(1) == EMPTY_SQUARE) && (pieceTypeOnIndex(2) == EMPTY_SQUARE) && (pieceTypeOnIndex(3) == EMPTY_SQUARE))
					{
						pseudoMoves[startIndex + totalMovesAdded] = Move.createMove(W_KING, 4, 2, 0, LONG_CASTLE, 0);
						totalMovesAdded++;
					}					
				}
			}
		}
		else // Black king moving
		{
			switch(black_castle)
			{
				case CASTLE_NONE: break; // No castling
				case CASTLE_SHORT:
				{
					// If squares between king and rook are empty, add short castle
					if((pieceTypeOnIndex(117) == EMPTY_SQUARE) && (pieceTypeOnIndex(118) == EMPTY_SQUARE))
					{
						pseudoMoves[startIndex + totalMovesAdded] = Move.createMove(B_KING, 116, 118, 0, SHORT_CASTLE, 0);
						totalMovesAdded++;
					}
					break;
				}
				case CASTLE_LONG:
				{
					// If squares between king and rook are empty, add long castle
					if((pieceTypeOnIndex(115) == EMPTY_SQUARE) && (pieceTypeOnIndex(114) == EMPTY_SQUARE) && (pieceTypeOnIndex(113) == EMPTY_SQUARE))
					{
						pseudoMoves[startIndex + totalMovesAdded] = Move.createMove(B_KING, 116, 114, 0, LONG_CASTLE, 0);
						totalMovesAdded++;
					}
					break;
				}
				default: // Can castle both ways
				{
					// If squares between king and rook are empty, add short castle
					if((pieceTypeOnIndex(117) == EMPTY_SQUARE) && (pieceTypeOnIndex(118) == EMPTY_SQUARE))
					{
						pseudoMoves[startIndex + totalMovesAdded] = Move.createMove(B_KING, 116, 118, 0, SHORT_CASTLE, 0);
						totalMovesAdded++;
					}
					// If squares between king and rook are empty, add long castle
					if((pieceTypeOnIndex(115) == EMPTY_SQUARE) && (pieceTypeOnIndex(114) == EMPTY_SQUARE) && (pieceTypeOnIndex(113) == EMPTY_SQUARE))
					{
						pseudoMoves[startIndex + totalMovesAdded] = Move.createMove(B_KING, 116, 114, 0, LONG_CASTLE, 0);
						totalMovesAdded++;
					}				
				}
			}			
		}
		return totalMovesAdded;
	}
	// END genCastling()

	/**
	 *  Takes an index, a delta, sliding/non-sliding boolean and the pseudoMoves-vector
	 *  and fills the array with pseudo-legal moves for the piece
	 *
	 *  @param index The index the piece is on
	 *  @param delta The piece's delta
	 *  @param sliding Sliding/non-sliding piece
	 *  @param pseudoMoves The array to be filled
	 *  @param startIndex The index where to start filling the array
	 *  @return totalMovesAdded The number of moves that were added to the array
	 */
	private int genMoves(int index, int[] delta, boolean sliding, int[] pseudoMoves, int startIndex)
	{
		int totalMovesAdded = 0;
		// Record the board's en passant square, white/black castling rights and half-moves
		for(int i = 0; i < 8; i++) // Loop through the 8 possible deltas
		{
			// Get the index of a square one step away from the orignal square by using the current delta
			int deltaIndex = index;
			deltaIndex += delta[i];
			while(delta[i] != 0) // Run the loop if we have a valid delta
			{
				if((deltaIndex & 0x88) == 0) // Target square is on the board
				{
					if(pieceTypeOnIndex(deltaIndex) == EMPTY_SQUARE) // The target square is empty
					{
						// Add the move to pseudoMoves
						pseudoMoves[startIndex + totalMovesAdded] = Move.createMove(pieceTypeOnIndex(index), index, deltaIndex, 0, ORDINARY_MOVE, 0);
						totalMovesAdded++;

						if(sliding) deltaIndex += delta[i]; // If the moving piece is sliding, add the next square
						else break; // If not sliding, stop calculating this delta
					}
					else // The target square is not empty
					{
						if((pieceTypeOnIndex(index) * pieceTypeOnIndex(deltaIndex)) < 0) // If the moving piece times the
												     // target piece is < 0. We know the
                                             							     // target piece is of opposite color
						{
							// Add the move as capture to pseudoMoves (i.e. send the piece int as capture)
							pseudoMoves[startIndex + totalMovesAdded] = Move.createMove(pieceTypeOnIndex(index), index, deltaIndex, pieceTypeOnIndex(deltaIndex), ORDINARY_MOVE, 0);
							totalMovesAdded++;
							break; // We can't go further in this direction
						}
						else break; // The target square contains a piece of the same color so no move here or further
					}
				}
				else break; // We've moved off the board, so stop checking this direction
			}
		}
		return totalMovesAdded;		
	}
	// END genMoves()
	
	/**
	 *  Takes an index and checks if the index can be attacked by
	 *  any piece of the side moving.
	 *
	 *  @param attacked The attacked index
	 *  @return boolean True it can be attacked, false it can't
	 */
	public boolean isAttacked(int attacked)
	{
		for(int piecesIndex = 0; piecesIndex < 32; piecesIndex++)
		{
			int attacker = pieces[piecesIndex];
			if(attacker != -1)
			{
				// Switch the color of the piece on the square and hold it in the variable,
				// this is done for clearer code below.
				//
				// So if black is moving and we find a black queen (-2) we make it a white
				// queen (2) by multiplying by toMove = -1 (black's move). Now we only have to
				// check for 'white' pieces below.
				int pieceOnSquare = pieceTypeOnIndex(attacker) * toMove;
				
				if(pieceOnSquare <= 0) continue;
				switch(ATTACK_ARRAY[attacked-attacker+128])
				{
					case ATTACK_NONE: break; // No piece can attack from here
					case ATTACK_KQR:
					{
						// If the checked square contains any of the pieces that
						// are able to get to the attacked square.
						//
						// Since this is only one square away from the attacked square
						// we can safely conclude that the square is attacked.
						if(pieceOnSquare == W_KING  ||
						   pieceOnSquare == W_QUEEN ||
						   pieceOnSquare == W_ROOK)
							return true;
						break;
					}
					case ATTACK_QR:
					{
						if(pieceOnSquare == W_QUEEN || pieceOnSquare == W_ROOK)
						{
							// If the traverse hits the attacked square
							// the piece can attack it.
							if(traverseDelta(attacker, attacked))
									return true;
						}
						break;						
					}
					case ATTACK_KQBwP:
					{
						if(pieceOnSquare == W_KING  ||
						   pieceOnSquare == W_QUEEN ||
						   pieceOnSquare == W_BISHOP)
							return true;

						// If it's white's turn to move and the piece is a white pawn it
						// can attack the square.
						//
						// We do this distinction so we don't confuse black and white pawns,
						// since they can only move in one direction depending on color.
						if(toMove == 1 && pieceTypeOnIndex(attacker) == W_PAWN)
							return true;
						break;

					}
					case ATTACK_KQBbP:
					{
						if(pieceOnSquare == W_KING  ||
						   pieceOnSquare == W_QUEEN ||
						   pieceOnSquare == W_BISHOP)
							return true;

						// If it's black's turn to move and the piece is a white pawn it
						// can attack the square.
						if(toMove == -1 && pieceTypeOnIndex(attacker) == B_PAWN)
							return true;
						break;						
					}
					case ATTACK_QB:
					{
						if(pieceOnSquare == W_QUEEN || pieceOnSquare == W_BISHOP)
						{
							// If the traverse hits the attacked square
							// the piece can attack it.
							if(traverseDelta(attacker, attacked))
									return true;
						}
						break;
					}
					case ATTACK_N:
					{
						// Knights can jump over pieces so we don't have to
						// check for pieces in the way.
						if(pieceOnSquare == W_KNIGHT)
							return true;
						break;
					}
				}
			}
		}

		return false; // If the loop didn't return true, no piece can attack the square
	}
	// END isAttacked()
	
	/**
	 *  Used by isAttacked() to traverse a piece's delta to
	 *  see if it runs in to any pieces on the way to the attacked square
	 *
	 *  @param attacker The attacking square
	 *  @param attacked The attacked square
	 *  @return boolean True if the piece can reach the attacked square, false if not
	 */
	public boolean traverseDelta(int attacker, int attacked)
	{
		int deltaIndex = attacker; // Initialize from first square
		int delta = DELTA_ARRAY[attacked - attacker + 128]; // Find the delta needed

		while((deltaIndex & 0x88) == 0) // Traverse until off the board
		{
			deltaIndex += delta; // Add the delta to move to the next square

			// We reached the attacked square, so we return true
			if(deltaIndex == attacked) return true;

			// A piece was found on the way, so return false
			if(pieceTypeOnIndex(deltaIndex) != EMPTY_SQUARE) return false;
		}
		return false; // If we for some reason missed the attacked square and wandered off the board
			      // return false. This shouldn't happen.
	}
	// END traverseDelta()
}
