/* Tic-tac-toe engine (5x5), adapted from a console program by
Alastair Francis, using minimax, alpha-beta pruning, and
depth-limited recursion with hueristic function
*/
/* This program is free software. You may redistribute and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 2 of the License or
 * (at your option) any later version.
 *
 * Refer to the file C:\LCARS24\DATA\COPYING.TXT for details.
 */


#include "wb5.h"


void Wb5InitBoard (Wb5BoardType* board)
{
	int i;

	for (i = 0; i < Wb5BOARD_SIZE; ++i)
	board->Wb5Element[i] = Wb5empty;
	board->Wb5Elements_occupied = 0;
}  /* end Wb5InitBoard */

void Wb5PlacePiece (Wb5BoardType* board, int position, Wb5GamePiece piece)
{
	board->Wb5Element[position] = piece;
	++(board->Wb5Elements_occupied);
}  /* end Wb5PlacePiece */

void Wb5RemovePiece (Wb5BoardType* board, int position)
{
	/* check if position is not already Wb5empty */
	if (board->Wb5Element[position] != Wb5empty)  {
		board->Wb5Element[position] = Wb5empty;
		--(board->Wb5Elements_occupied);
	}  /* end if */
}  /* end Wb5RemovePiece */


Wb5Boolean Wb5IsWinner (Wb5BoardType board)
{
  int i, position;
  int check_line;
  Wb5Boolean winner = Wb5False;

  /* check rows */
  position = 0;
  while ((! winner) && (position < Wb5BOARD_SIZE))  {
	  check_line = board.Wb5Element[position];

	  /* check each row for consecutive pieces which are the same */
	  for (i = (position + 1); i < (position + Wb5BOARD_WIDTH); ++i)
	check_line = check_line & board.Wb5Element[i];

	  winner = (check_line != Wb5empty) ? Wb5True : Wb5False;
	  position += Wb5BOARD_WIDTH;
  }  /* end while - check rows */

  /* check columns */
  position = 0;
  while ((! winner) && (position < Wb5BOARD_WIDTH))  {
	  check_line = board.Wb5Element[position];

	  /* check each column for consecutive pieces which are the same */
	  for (i = (position + Wb5BOARD_WIDTH); i < Wb5BOARD_SIZE; i += Wb5BOARD_WIDTH)
	check_line = check_line & board.Wb5Element[i];

	  winner = (check_line != Wb5empty) ? Wb5True : Wb5False;
	  ++position;
  }  /* end while - check columns */

  /* check diagonals */
  /* diagonal from top left to bottom right */
  if (! winner)  {
	  check_line = board.Wb5Element[0];
	  for (i = (Wb5BOARD_WIDTH + 1); i < Wb5BOARD_SIZE; i += (Wb5BOARD_WIDTH + 1))
	check_line = check_line & board.Wb5Element[i];

	  winner = (check_line != Wb5empty) ? Wb5True : Wb5False;
  }  /* end if */

  /* diagonal from top right to bottom left */
  if (! winner)  {
	  check_line = board.Wb5Element[Wb5BOARD_WIDTH - 1];
	  for (i = (2 * Wb5BOARD_WIDTH - 2); i < (Wb5BOARD_SIZE - 1);
					  i += (Wb5BOARD_WIDTH - 1))
	check_line = check_line & board.Wb5Element[i];

	  winner = (check_line != Wb5empty) ? Wb5True : Wb5False;
  }  /* end if */

  return winner;
}  /* end Wb5IsWinner */


Wb5Boolean Wb5IsFull (Wb5BoardType board)
{
  if (board.Wb5Elements_occupied == Wb5BOARD_SIZE)  {
	  return Wb5True;
  }
  else  {
	  return Wb5False;
  }  /* end if else */
}  /* end Wb5IsFull */


int Wb5Heuristic (Wb5BoardType board)
{
  int i, position;
  Wb5Boolean possible_winner;
  int utility_tally, utility = 0;

  /* determine utility of rows */
  position = 0;
  while (position < Wb5BOARD_SIZE)  {
	  /* check each row for possible winning rows */
	  possible_winner = Wb5True;
	  utility_tally = 0;
	  for (i = position; (i < (position + Wb5BOARD_WIDTH)) && possible_winner; ++i)  {
	if (board.Wb5Element[i] != Wb5empty)  {
		if (Wb5Players_piece != board.Wb5Element[i])  {
			/* row has non-Wb5Player piece, can't be a winning row */
			possible_winner = Wb5False;
			utility_tally = 0;
		}
		else  {
			/* utility_tally counts the number of Wb5Player pieces per row */
			++utility_tally;
		}  /* end if else */
	}  /* end if - board position not Wb5empty */
	  }  /* end for loop - utility of a row */

	  utility += utility_tally;
	  position += Wb5BOARD_WIDTH;
  }  /* end while - utility of all rows */

  /* determine utility of columns */
  position = 0;
  while (position < Wb5BOARD_WIDTH)  {
	  possible_winner = Wb5True;
	  utility_tally = 0;
	  for (i = position; (i < Wb5BOARD_SIZE) && possible_winner; i += Wb5BOARD_WIDTH)  {
	if (board.Wb5Element[i] != Wb5empty)  {
		if (Wb5Players_piece != board.Wb5Element[i])  {
			possible_winner = Wb5False;
			utility_tally = 0;
		}
		else  {
			/* utility_tally counts the number of Wb5Player pieces per column */
			++utility_tally;
		}  /* end if else */
	}  /* end if - board position not Wb5empty */
	  }  /* end for loop - utility of column */

	  utility += utility_tally;
	  ++position;
  }  /* end while - utility of all columns */

  /* determine utility of diagonals */
  /* diagonal from top left to bottom right */
  possible_winner = Wb5True;
  utility_tally = 0;
  for (i = 0; (i < Wb5BOARD_SIZE) && possible_winner; i += (Wb5BOARD_WIDTH + 1))  {
	  if (board.Wb5Element[i] != Wb5empty)  {
	if (Wb5Players_piece != board.Wb5Element[i])  {
		possible_winner = Wb5False;
		utility_tally = 0;
	}
	else  {
		++utility_tally;
	}  /* end if else */
	  }  /* end if */
  }  /* end for loop */
  utility += utility_tally;

  /* diagonal from top right to bottom left */
  possible_winner = Wb5True;
  utility_tally = 0;
  for (i = Wb5BOARD_WIDTH - 1; (i < (Wb5BOARD_SIZE - 1)) && possible_winner;
						i += (Wb5BOARD_WIDTH - 1))  {
	  if (board.Wb5Element[i] != Wb5empty)  {
	if (Wb5Players_piece != board.Wb5Element[i])  {
		possible_winner = Wb5False;
		utility_tally = 0;
	}
	else  {
		++utility_tally;
	}  /* end if else */
	  }  /* end if */
  }  /* end for loop */
  utility += utility_tally;

  return utility;
}  /* end Wb5Heuristic */


int Wb5FindBestMove (Wb5BoardType board, Wb5GamePiece piece)
{
	const int corner_positions[4] =
	{0, Wb5BOARD_WIDTH - 1, Wb5BOARD_SIZE - Wb5BOARD_WIDTH, Wb5BOARD_SIZE - 1};
	int best_move, corner, centre_pos;
	Wb5Boolean occupied;
	int dummy;

	centre_pos = Wb5BOARD_SIZE / 2;
	if (board.Wb5Elements_occupied == 0)  {
		/* no pieces on board, best move is centre */
		best_move = centre_pos;
	}
	else  {
		if (board.Wb5Elements_occupied == 1)  {
	 if (board.Wb5Element[centre_pos] == Wb5empty)  {
		 /* centre position not taken, best move centre position */
		 best_move = centre_pos;
	 }
	 else  {
		 /* centre already taken, best move on a corner */
		 occupied = Wb5False;
		 do  {
			 /* choose a corner position at random */
/* Turbo code			corner = corner_positions[random (4)]; */
/* DJGPP code */  corner = corner_positions[rand() % 4];


			 if (board.Wb5Element[corner] != Wb5empty)
		  occupied = Wb5True;
		 } while (occupied);

		 best_move = corner;
	 }  /* end if else - 1 piece already on board*/
		}
		else  {
	 /* 2 or more pieces already on the board */
	 /* call minimax with alpha-beta pruning and recursion depth limitation */
	 Wb5Players_piece = piece;
	 best_move = Wb5FindPlayerMove (board, piece, &dummy, INT_MIN, INT_MAX, 0);
		}  /* end else */
	}  /* end if else */

	return best_move;
}  /* end Wb5FindBestMove */

void Wb5FindOpponentMove (Wb5BoardType board, Wb5GamePiece piece, int* status,
			 int alpha, int beta, int depth)
{
	int i, dont_care;
	int current_status;

	if (Wb5IsWinner (board))  {
		/* goal state and terminal case, Wb5Player has won by last move */
		/* utility value is an arbitrarly large number < MAX_INT */
		*status = 1000;
	}
	else  {
		if (Wb5IsFull (board))  {
	 /* terminal case, game drawn */
	 *status = 0;
		}
		else  {
	 /*
		 Opponent maximizes its outcome, minimum Wb5Player outcome.
		 beta is the upper bound on the value that the minimizing node
		 may be assigned.
		 If the value of the min position is determined to be less than
		 or equal to the alpha value of the parent node, then we can stop
		 generation of the remaining children of this min node.
	 */

	 if (depth < Wb5MaxDepth)  {
		 *status = beta;

		 for (i = 0; (i < Wb5BOARD_SIZE) && (*status > alpha); ++i)  {
			 if (board.Wb5Element[i] == Wb5empty)  {
		  Wb5PlacePiece (&board, i, piece);
		  dont_care = Wb5FindPlayerMove (board, ((piece == R) ? S : R),
				 &current_status, alpha, *status, (depth + 1));
		  Wb5RemovePiece (&board, i);
		  if (current_status < *status)  {
			  /* found a better move for opponent */
			  *status = current_status;
		  }  /* end if */
			 }  /* end if - try game piece in non Wb5empty position */
		 }  /* end for - try all Wb5empty board positions */
	 }
	 else  {
		 *status = Wb5Heuristic (board);
	 }  /* end if else */

		}  /* end if else */
	}  /* end if else */

}  /* end Wb5FindOpponentMove */

/* minimax routines with alpha-beta pruning and recurive depth limitation */

int Wb5FindPlayerMove (Wb5BoardType board, Wb5GamePiece piece, int* status,
				int alpha, int beta, int depth)
{
	int i, best_move;
	int current_status;

	if (Wb5IsWinner (board))  {
		/* terminal case, opponent has won by last move */
		/* utility value is an arbitrarly small number > MIN_INT */
		*status = -1000;
	}
	else  {
		if (Wb5IsFull (board))  {
	 /* terminal case, game drawn */
	 *status = 0;
		}
		else  {
	 /*
		 Keep searching for a better move, maximum Wb5Player outcome.
		 alpha is the lower bound on the value the maximizing node may
		 be assigned.
		 If the value of a max position is determined to be greater than
		 or equal to the beta value of its parent node, then we can
		 stop generation of the remaining children of this max node.
	 */
	 if (depth < Wb5MaxDepth)  {
		 *status = alpha;

		 for (i = 0; (i < Wb5BOARD_SIZE) && (*status < beta); ++i)  {
			 if (board.Wb5Element[i] == Wb5empty)  {
		  Wb5PlacePiece (&board, i, piece);
		  Wb5FindOpponentMove (board, ((piece == R) ? S : R),
				&current_status, *status, beta, (depth + 1));
		  Wb5RemovePiece (&board, i);
		  if (current_status > *status)  {
			  /* Found a move with better utility for the Wb5Player. */
			  *status = current_status;
			  best_move = i;
		  }  /* end if */
			 }  /* end if - try game piece in non Wb5empty position */
		 }  /* end for - try all Wb5empty board positions */
	 }
	 else  {
		 *status = Wb5Heuristic (board);
	 }  /* end if */

		}  /* end if else */
	}  /* end if else */

	return best_move;
}  /* end Wb5FindPlayerMove */

