/*P*/
/****************************************************************/
/*								*/
/* movegen - these routines generate all possible moves for	*/
/* each color. They are not at all trivial, and you'd think	*/
/* that they are too long for one function. However, breaking	*/
/* these apart makes them run more slowly, and makes them much	*/
/* more difficult to follow, unfortunately.			*/
/*								*/
/****************************************************************/

#include	<stdio.h>
#include	"bkg.h"

#define		WORST		-32768
#define		TEXT_COLOR	0x07
#define		MIN( a, b )	( a < b ? a : b )
#define		OFF		0
#define		ON		1

/*P*/
/****************************************************************/
/*								*/
/* b_movegen							*/
/*								*/
/* This will generate all of the possible moves for black. If	*/
/* the "computer" parameter is false, this procedure will look	*/
/* to find the moves that are possible for black, returning the	*/
/* number. This is so that the black player is required to	*/
/* make 2 moves if a 2-move is possible. If the "computer" flag	*/
/* is true, the routine calls "b_eval" to find the best of the	*/
/* moves generated. This best move is formatted and returned in	*/
/* "line", in a format that can be understood by the command	*/
/* parser (just as if a user had entered it).			*/
/*								*/
/* An explanation of the "level" variable is in order. It'll	*/
/* keep temporary tabs on how many dice we have been able to	*/
/* apply in a given attempt. If we find a possible move that	*/
/* has a value in "level" that is < the largest possible	*/
/* "level" so far, then this is illegal, since we have to use	*/
/* all of the dice if we can.					*/
/*								*/
/****************************************************************/

b_movegen( die_1, die_2, computer, biggest, line, echo )

int	die_1, die_2;
int	computer, *biggest;
char	line[];
int	echo;

	{

	char	*format[ 5 ];
	int	p[ 4 ], die[ 4 ], best_p[ 4 ], best_die[ 4 ], i, j;
	int	temp, level, finished, copy, best, value, count;
	int	test[ SIZE ][ 3 ];

	/* These are format spec's to be used	*/
	/* by computer generated moves.		*/

	if ( ! computer )
		*biggest = 0;
	else
		{
		format[ 0 ] = "software bug?";
		format[ 1 ] = "%d/%d";
		format[ 2 ] = "%d/%d %d/%d";
		format[ 3 ] = "%d/%d %d/%d %d/%d";
		format[ 4 ] = "%d/%d %d/%d %d/%d %d/%d";
		best = WORST;
		}

	count = 0;
	die[ 0 ] = die[ 2 ] = die_1;
	die[ 1 ] = die[ 3 ] = die_2;

	/* Copy the board into the test area. The 2	*/
	/* is a temp. holding area for the opponents	*/
	/* men that are bumped off.			*/

	movmem( board, test, BOARD_IN_BYTES );

	finished = 0;

	while ( finished < 2 )
		{

		/* Try all possible first uses for the	*/
		/* dice, from the bar on out.		*/

		for( p[ 0 ] = B_BAR; p[ 0 ] < 25; p[ 0 ]++ )
			{

 			/* If this is an illegal move, forgetit */

			if ( ! b_valid_move( test, p[ 0 ], die[ 0 ] ) )
				continue;

			level = 1;

			b_change( test, p[ 0 ], die[ 0 ], OFF );

			/* Now do the same thing within here,	*/
			/* using the other die as the value.	*/
	
			for( p[ 1 ] = B_BAR; p[ 1 ] < 25; p[ 1 ]++ )
				{
	
				if ( ! b_valid_move( test, p[ 1 ], die[ 1 ] ) )
					continue;
	
				b_change( test, p[ 1 ], die[ 1 ], OFF );

				/* If we have doubles, we have yet another	*/
				/* iteration of the two dice to go through here	*/
	
				if ( die[ 0 ] == die[ 1 ] )
					{
	
					for( p[ 2 ] = B_BAR; p[ 2 ] < 25; p[ 2 ]++ )
						{

						if ( ! b_valid_move( test, p[ 2 ], die[ 2 ] ) )
							continue;
	
						level = 3;
	
						b_change( test, p[ 2 ], die[ 2 ], OFF );

						/* Now do the same thing within here,	*/
						/* using the other die as the value.	*/
	
						for( p[ 3 ] = B_BAR; p[ 3 ] < 25; p[ 3 ]++ )
							{
	
							if ( ! b_valid_move( test, p[ 3 ], die[ 3 ] ) )
								continue;

							b_change( test, p[ 3 ], die[ 3 ], OFF );
	
							if ( bar_first( p, MIN( board[ B_BAR ][ BLACK ], 4 ) ) )
								{

								level = 4; ііііііііііііііііііііііііііііііі ііііііііііііііііііііііііііііііі ііііііііііііііііііііііііііііііі ііііііііііііііііііііііііііііііі ііііііііііііііііііііііііііііііі ііііііііііііііііііііііііііііііі ііііііііііііііііііііііііііііііі ііііііііііііііііііііііііііііііі ііііііііііііііііііііііііііііііі ііііііііііііііііііііііііііііііі ііііііііііііііііііііііііііііііі ііііііііііііііііііііііііііііііі ііііііііііііііііііііііііііііііі ііііііііііііііііііііііііііііііі ііііііііііііііііііііііііііііііі ііііііііііііііііііііііііііііііі loop */
	
						if ( level == 3 )
							{

							if ( ( *biggest <= 3					 ) &&
							     ( bar_first( p, MIN( board[ B_BAR ][ BLACK ], 3 ) ) ) )
								{

								if ( ! computer )
									*biggest = ( *biggest < 3 ) ? 3 : *biggest;
								else
									{

									value = b_eval( test, count++ );
									if ( value > best )
										{

										best = value;
										for( copy = 0; copy < 3; copy++ )
											{
											best_p[ copy ] = p[ copy ];
											best_die[ copy ] = die[ copy ];
											}
										}
									}
								}

							} /* level 3 */
	
						/* Put the pieces back where they were	*/
						/* so that the next time through the	*/
						/* loop we'll be using the originals.	*/
	
						b_change( test, p[ 2 ], die[ 2 ], ON );

						} /* p[ 2 ] control loop */

					/* If we had doubles but can only make	*/
					/* two moves out of the possible 4...	*/
					/* (Read the words "bug fix" here!)	*/

					if ( level == 1 )
						{

						level = 2;

						if ( ( *biggest <= 2					 ) &&
						     ( bar_first( p, MIN( board[ B_BAR ][ BLACK ], 2 ) ) ) )
							{

							if ( ! computer )
								*biggest = ( *biggest < 2 ) ? 2 : *biggest;
							else
								{

								value = b_eval( test, count++ );
								if ( value > best )
									{
									best = value;
									for( copy = 0; copy < 2; copy++ )
										{
										best_p[ copy ] = p[ copy ];
										best_die[ copy ] = die[ copy ];
										}
									}
								}
							}
						}

					} /* Doubles handler */
				else
					{
	
					/* If there were men on the original bar, we	*/
					/* must remove them prior to making any other	*/
					/* moves.					*/
	
					if ( ( *biggest <= 2					 ) &&
					     ( bar_first( p, MIN( board[ B_BAR ][ BLACK ], 2 ) ) ) )
						{

						level = 2;

						if ( ! computer )
							{
							*biggest = ( *biggest < 2 ) ? 2 : *biggest;
							return;
							}
						else
							{

							value = b_eval( test, count++ );
							if ( value > best )
								{

								best = value;
								for( copy = 0; copy < 2; copy++ )
									{
									best_p[ copy ] = p[ copy ];
									best_die[ copy ] = die[ copy ];
									}
								}
							}
						}
	
					} /* not doubles */
	
				b_change( test, p[ 1 ], die[ 1 ], ON );

 				} /* p[ 1 ] control loop */
	
			/* If "level" is still 1, we did not	*/
			/* find any use for the other die.	*/
	
			if ( level == 1 )
				{

				if ( ( *biggest <= 1					 ) &&
				     ( bar_first( p, MIN( board[ B_BAR ][ BLACK ], 1 ) ) ) )
					{

					if ( ! computer )
						*biggest = ( *biggest < 1 ) ? 1 : *biggest;
					else
						{

						value = b_eval( test, count++ );
						if ( value > best )
							{
							best = value;
							best_p[ 0 ] = p[ 0 ];
							best_die[ 0 ] = die[ 0 ];
							}
						}
					}
	
				} /* level 1 */
	
			/* Put the pieces back where they were	*/
			/* so that the next time through the	*/
			/* loop we'll be using the originals.	*/
	
			b_change( test, p[ 0 ], die[ 0 ], ON );

			} /* p[ 0 ] control loop */

		/* If we had doubles, then we're done.	*/
		/* Otherwise rotate the dice (swap) and	*/
		/* do it all again, using, say 5,3 now	*/
		/* if the roll was 3,5.			*/

		if ( die[ 0 ] == die[ 1 ] )
			finished = 2;
		else
			{
			temp = die[ 0 ];
			die[ 0 ] = die[ 1 ];
			die[ 1 ] = temp;
			finished++;
			}

		} /* while not finished yet */

	if ( computer )
		{

		/* Format the move we've decided on.	*/
		/* The "eval" proc may have written	*/
		/* a few words below the dice, so we'll	*/
		/* space them out here.			*/

		sprintf( line, format[ *biggest ],
			 best_p[ 0 ], best_die[ 0 ],
			 best_p[ 1 ], best_die[ 1 ],
			 best_p[ 2 ], best_die[ 2 ],
			 best_p[ 3 ], best_die[ 3 ] );

		write_at( 15, 65, "           ", TEXT_COLOR );

		} /* computer */

	} /* b_movegen */

/*P*/
/****************************************************************/
/*								*/
/* b_exit_ok							*/
/*								*/
/* This returns true if it is ok for black to exit the board	*/
/* from this position, using this roll. "Test" is a temporary	*/
/* playing board.						*/
/*								*/
/****************************************************************/
	
b_exit_ok( test, psn, roll )

int	test[ SIZE ][ 3 ];
int	psn, roll;

	{
	
	int	i;
	
	/* First off, if there is anyine not in the	*/
	/* inner table, you can not move them off.	*/

	for( i = B_BAR; i < 19; i++ )
		if ( test[ i ][ BLACK ] )
			return( FALSE );

	/* Now, if the sum is EXACTLY 25, it is ok to	*/
	/* take them off regardless of the others.	*/

	if ( ( psn + roll ) == B_HOME )
		return( TRUE );

	/* Lastly, if we have, say, a 5 but there are	*/
	/* only men on 1, 2, and 3, ok to take off the	*/
	/* one at 3 only.				*/

	for( i = psn - 1; i > 18; i-- )
		if ( test[ i ][ BLACK ] )
			return( FALSE );

	return( TRUE );

	} /* b_this_ok */

/*P*/
/****************************************************************/
/*								*/
/* b_valid_move							*/
/*								*/
/* Return true if it is currently ok for black to move from	*/
/* the position "point" a distance of "die" on the board "test"	*/
/* Otherwise return false.					*/
/*								*/
/****************************************************************/

b_valid_move( test, point, die )

int	test[ SIZE ][ 3 ], point, die;

	{

	if ( ! test[ point ][ BLACK ] )
		return( FALSE );

	if ( ( point + die ) > 24 )
		{
		if ( ! b_exit_ok( test, point, die ) )
			return( FALSE );
		}
	else
		{
		if ( test[ point + die ][ WHITE ] >= 2 )
			return( FALSE );
		}

	return( TRUE );

	} /* b_valid_move */

/*P*/
/****************************************************************/
/*								*/
/* b_change							*/
/*								*/
/* Take the "test" board and move the black player from the	*/
/* position "point" a distance of "die". We may either be 	*/
/* putting the man on the new position from the old ("on" == 1)	*/
/* or we might be moving him back to where he was originally.	*/
/* The 2'th dimension on the most-significant dimension of 	*/
/* "test" holds a 1 if a white player has been kicked off this	*/
/* spot.							*/
/*								*/
/****************************************************************/

b_change( test, point, die, on )

int	test[ SIZE ][ 3 ], point, die, on;

	{

	if ( on )
		{

		test[ point ][ BLACK ]++;
		if ( point + die <= 24 )
			{
			test[ point + die ][ BLACK ]--;
			if ( test[ point + die ][ 2 ] )
				{
				test[ point + die ][ WHITE ]++;
				test[ point + die ][ 2 ]--;
				}
			}
		}
	else
		{

		test[ point ][ BLACK ]--;
		if ( point + die <= 24 )
			{
			test[ point + die ][ BLACK ]++;
			if ( test[ point + die ][ WHITE ] == 1 )
				{
				test[ point + die ][ WHITE ]--;
				test[ point + die ][ 2 ]++;
				}
			}
		}

	} /* b_change */

/*P*/
/****************************************************************/
/*								*/
/* bar_first							*/
/*								*/
/* If there are men on the bar, then we must move them offa	*/
/* there before doing anything else. It's illegal not to.	*/
/*								*/
/****************************************************************/

bar_first( points, num )

int	points[], num;

	{

	while( num )
		if ( ( points[ num - 1 ] != 0  ) &&
		     ( points[ num - 1 ] != 25 ) )
			return( FALSE );
		else
			num--;

	return( TRUE );

	} /* bar_first */

/*P*/
/****************************************************************/
/*								*/
/* w_movegen							*/
/*								*/
/* This will generate all of the possible moves for white. If	*/
/* the "computer" parameter is false, this procedure will look	*/
/* to find the moves that are possible for white, returning the	*/
/* number. This is so that the white player is required to	*/
/* make 2 moves if a 2-move is possible. If the "computer" flag	*/
/* is true, the routine calls "w_eval" to find the best of the	*/
/* moves generated. This best move is formatted and returned in	*/
/* "line", in a format that can be understood by the command	*/
/* parser (just as if a user had entered it).			*/
/*								*/
/* If all of that sounded familiar, it's because the remainder	*/
/* of these functions do the same thing as above, but with the	*/
/* direction (++ as opposed to --, < as opposed to >, etc.)	*/
/* reversed.							*/
/*								*/
/****************************************************************/

w_movegen( die_1, die_2, computer, biggest, line, echo )

int	die_1, die_2;
int	computer, *biggest;
char	line[];
int	echo;

	{

	char	*format[ 5 ];
	int	p[ 4 ], die[ 4 ], best_p[ 4 ], best_die[ 4 ], i, j;
	int	temp, level, finished, copy, best, value, count;
	int	test[ SIZE ][ 3 ];

	if ( ! computer )
		*biggest = 0;
	else
		{
		format[ 0 ] = "software bug?";
		format[ 1 ] = "%d/%d";
		format[ 2 ] = "%d/%d %d/%d";
		format[ 3 ] = "%d/%d %d/%d %d/%d";
		format[ 4 ] = "%d/%d %d/%d %d/%d %d/%d";
		best = WORST;
		}

	count = 0;
	die[ 0 ] = die[ 2 ] = die_1;
	die[ 1 ] = die[ 3 ] = die_2;

	/* Copy the board into the test area. The 2	*/
	/* is a temp. holding area for the opponents	*/
	/* men that are bumped off.			*/

	movmem( board, test, BOARD_IN_BYTES );

	finished = 0;

	while ( finished < 2 )
		{

		for( p[ 0 ] = W_BAR; p[ 0 ]; p[ 0 ]-- )
			{

			if ( ! w_valid_move( test, p[ 0 ], die[ 0 ] ) )
				continue;

			level = 1;

			w_change( test, p[ 0 ], die[ 0 ], OFF );

			/* Now do the same thing within here,	*/
			/* using the other die as the value.	*/
	
			for( p[ 1 ] = W_BAR; p[ 1 ]; p[ 1 ]-- )
				{
	
				if ( ! w_valid_move( test, p[ 1 ], die[ 1 ] ) )
					continue;
	
				w_change( test, p[ 1 ], die[ 1 ], OFF );

				/* If we have doubles, we have yet another	*/
				/* iteration of the two dice to go through here	*/
	
				if ( die[ 0 ] == die[ 1 ] )
					{
	
					for( p[ 2 ] = W_BAR; p[ 2 ]; p[ 2 ]-- )
						{

						if ( ! w_valid_move( test, p[ 2 ], die[ 2 ] ) )
							continue;
	
						level = 3;
	
						w_change( test, p[ 2 ], die[ 2 ], OFF );

						/* Now do the same thing within here,	*/
						/* using the other die as the value.	*/
	
						for( p[ 3 ] = W_BAR; p[ 3 ]; p[ 3 ]-- )
							{
	
							if ( ! w_valid_move( test, p[ 3 ], die[ 3 ] ) )
								continue;

							w_change( test, p[ 3 ], die[ 3 ], OFF );
	
							if ( bar_first( p, MIN( board[ W_BAR ][ WHITE ], 4 ) ) )
								{

								level = 4;

								if ( ! computer )
									{
									*biggest = 4;
									return;
									}
								else
									{

									value = w_eval( test, count++ );
									if ( value > best )
										{

										best = value;
										for( copy = 0; copy < 4; copy++ )
											{
											best_p[ copy ] = p[ copy ];
											best_die[ copy ] = die[ copy ];
											}

										}
									}
								}
	
							w_change( test, p[ 3 ], die[ 3 ], ON );

							} /* p[ 3 ] control loop */
	
						if ( level == 3 )
							{

							if ( ( *biggest <= 3					 ) &&
							     ( bar_first( p, MIN( board[ W_BAR ][ WHITE ], 3 ) ) ) )
								{

								if ( ! computer )
									*biggest = ( *biggest < 3 ) ? 3 : *biggest;
								else
									{

									value = w_eval( test, count++ );
									if ( value > best )
										{

										best = value;
										for( copy = 0; copy < 3; copy++ )
											{
											best_p[ copy ] = p[ copy ];
											best_die[ copy ] = die[ copy ];
											}
										}
									}
								}

							} /* level 3 */
	
						/* Put the pieces back where they were	*/
						/* so that the next time through the	*/
						/* loop we'll be using the originals.	*/
	
						w_change( test, p[ 2 ], die[ 2 ], ON );

						} /* p[ 2 ] control loop */

					/* If we had doubles but can only make	*/
					/* two moves out of the possible 4...	*/

					if ( level == 1 )
						{

						level = 2;

						if ( ( *biggest <= 2					 ) &&
						     ( bar_first( p, MIN( board[ W_BAR ][ WHITE ], 2 ) ) ) )
							{

							if ( ! computer )
								*biggest = ( *biggest < 2 ) ? 2 : *biggest;
							else
								{

								value = w_eval( test, count++ );
								if ( value > best )
									{
									best = value;
									for( copy = 0; copy < 2; copy++ )
										{
										best_p[ copy ] = p[ copy ];
										best_die[ copy ] = die[ copy ];
										}
									}
								}
							}
						}

					} /* Doubles handler */
				else
					{
	
					/* If there were men on the original bar, we	*/
					/* must remove them prior to making any other	*/
					/* moves.					*/
	
					if ( ( *biggest <= 2					 ) &&
					     ( bar_first( p, MIN( board[ W_BAR ][ WHITE ], 2 ) ) ) )
						{

						level = 2;

						if ( ! computer )
							{
							*biggest = ( *biggest < 2 ) ? 2 : *biggest;
							return;
							}
						else
							{

							value = w_eval( test, count++ );
							if ( value > best )
								{

								best = value;
								for( copy = 0; copy < 2; copy++ )
									{
									best_p[ copy ] = p[ copy ];
									best_die[ copy ] = die[ copy ];
									}
								}
							}
						}
	
					} /* not doubles */
	
				w_change( test, p[ 1 ], die[ 1 ], ON );

 				} /* p[ 1 ] control loop */
	
			/* If "level" is still 1, we did not	*/
			/* find any use for the other die.	*/
	
			if ( level == 1 )
				{

				if ( ( *biggest <= 1					 ) &&
				     ( bar_first( p, MIN( board[ W_BAR ][ WHITE ], 1 ) ) ) )
					{

					if ( ! computer )
						*biggest = ( *biggest < 1 ) ? 1 : *biggest;
					else
						{

						value = w_eval( test, count++ );
						if ( value > best )
							{
							best = value;
							best_p[ 0 ] = p[ 0 ];
							best_die[ 0 ] = die[ 0 ];
							}
						}
					}
	
				} /* level 1 */
	
			/* Put the pieces back where they were	*/
			/* so that the next time through the	*/
			/* loop we'll be using the originals.	*/
	
			w_change( test, p[ 0 ], die[ 0 ], ON );

			} /* p[ 0 ] control loop */

		/* If we had doubles, then we're done.	*/
		/* Otherwise rotate the dice (swap) and	*/
		/* do it all again, using, say 5,3 now	*/
		/* if the roll was 3,5.			*/

		if ( die[ 0 ] == die[ 1 ] )
			finished = 2;
		else
			{
			temp = die[ 0 ];
			die[ 0 ] = die[ 1 ];
			die[ 1 ] = temp;
			finished++;
			}

		} /* while not finished yet */

	if ( computer )
		{

		sprintf( line, format[ *biggest ],
			 best_p[ 0 ], best_die[ 0 ],
			 best_p[ 1 ], best_die[ 1 ],
			 best_p[ 2 ], best_die[ 2 ],
			 best_p[ 3 ], best_die[ 3 ] );

		write_at( 15, 65, "           ", TEXT_COLOR );

		} /* computer */

	} /* w_movegen */

/*P*/
/****************************************************************/
/*								*/
/* w_exit_ok							*/
/*								*/
/* This returns true if it is ok for white to exit the board	*/
/* from this position.						*/
/*								*/
/****************************************************************/
	
w_exit_ok( test, psn, roll )

int	test[ SIZE ][ 3 ];
int	psn, roll;

	{
	
	int	i;
	
	/* First off, if there is anyine not in the	*/
	/* inner table, you can not move them off.	*/

	for( i = W_BAR; i > 6; i-- )
		if ( test[ i ][ WHITE ] )
			return( FALSE );

	/* Now, if the sum is EXACTLY 25, it is ok to	*/
	/* take them off regardless of the others.	*/

	if ( ( psn - roll ) == W_HOME )
		return( TRUE );

	/* Lastly, if we have, say, a 5 but there are	*/
	/* only men on 1, 2, and 3, ok to take off the	*/
	/* one at 3 only.				*/

	for( i = psn + 1; i < 7; i++ )
		if ( test[ i ][ WHITE ] )
			return( FALSE );

	return( TRUE );

	} /* w_this_ok */

/*P*/
/****************************************************************/
/*								*/
/* w_valid_move							*/
/*								*/
/* Same as above. If white can legally make this move, return a	*/
/* "true", else a "false".					*/
/*								*/
/****************************************************************/

w_valid_move( test, point, die )

int	test[ SIZE ][ 3 ], point, die;

	{

	if ( ! test[ point ][ WHITE ] )
		return( FALSE );

	if ( ( point - die ) < 1 )
		{
		if ( ! w_exit_ok( test, point, die ) )
			return( FALSE );
		}
	else
		{
		if ( test[ point - die ][ BLACK ] >= 2 )
			return( FALSE );
		}

	return( TRUE );

	} /* w_valid_move */

/*P*/
/****************************************************************/
/*								*/
/* w_change							*/
/*								*/
/* Move a piece for white. If "on" is true, move it out. Else	*/
/* move it back where it was.					*/
/*								*/
/****************************************************************/

w_change( test, point, die, on )

int	test[ SIZE ][ 3 ], point, die, on;

	{

	if ( on )
		{

		test[ point ][ WHITE ]++;
		if ( point - die >= 1 )
			{
			test[ point - die ][ WHITE ]--;
			if ( test[ point - die ][ 2 ] )
				{
				test[ point - die ][ BLACK ]++;
				test[ point - die ][ 2 ]--;
				}
			}
		}
	else
		{

		test[ point ][ WHITE ]--;
		if ( point - die >= 1 )
			{
			test[ point - die ][ WHITE ]++;
			if ( test[ point - die ][ BLACK ] == 1 )
				{
				test[ point - die ][ BLACK ]--;
				test[ point - die ][ 2 ]++;
				}
			}
		}

	} /* w_change */
