/* tsumes.c	Dec 3 1985	Nigel R. Haslock

/* This version repeatedly scans the tree, expanding only those
/* defensive moves where the number of options is less than the
/* current value of d_width.

/* Now adding an option to preserve completed sub trees for reuse.
/* i.e. If all of the responses to a move have been expanded and
/*      they all have the same result, MATE, the move is copied to
/*	the 'mate_heap' list, and the sub-tree below the move is
/*	associated with the copy.
/*	If a board state is found, subsequently, to match a state
/*	in the mate_heap list it is pointed to the move it matches,
/*	saving space and time.
/****************************************************************
/****************************************************************
/* The object of this program is to solve tsume shogi problems.
 * These are the equivalent of the 'white to play and mate in 5'
 * problems of european chess.
 *
 * There are one or two differences.
 *	Shogi allows captured pieces to be dropped onto the board.
 *	Thus tsume assumes that the attacker must check with
 *	every move on the basis that he will be mated if he doesn't.
 *	If a piece is dropped in defense, it must dropped on a defended
 *	square.
 *		This is to simplify move counts and is not quite right.
 *	Only rarely is the whole board shown, but the only piece assumed
 *	to be on the board is the attackers King. All undefined pieces
 *	are in the defenders hand.
 *	The solution must cover all possible responses and must show that
 *	all defenses lead to mate. This means that the attacker may not
 *	move to form an earlier board state.
 *****************************************************************
 *****************************************************************/

/* Major Data Structures
*
*	Tree of checked moves
*	Heap of proven mate positions
*/

/* Factors working to minimise the size of the tree.
*	The attack must always attack the king. If it is not possible
*	to find an attack then the previous move by the attacker must
*	be abandoned.
*	The defense must always relieve the attack.
*/

#include "tsume.h"
#include "tsumedat.h"

extern
STEM	att_move (),	def_move ();

/* These are the strings that will be used to identify pieces on the
 * board (board_str) and pieces being moved(name_str).
 * Names are indexed by piece number which is incremented by 10 when
 * a piece is promoted. Only pieces with numbers in the low ranges
 * can be promoted. Low ranges are 0 to 10 and 100 to 110.
 */
char	*name_str[] = {
	"",
	"P ", "L ", "H ", "S ", "",   "R ", "B ", "", "", "", /* 10 */
	"pP", "pL", "pH", "pS", "G ", "pR", "pB", "", "", "", /* 20 */
	"",   "",   "",   "",   "",   "",   "",   "", "", "", /* 30 */
	"",   "",   "",   "",   "",   "",   "",   "", "", "", /* 40 */
	"",   "",   "",   "",   "",   "",   "",   "", "", "", /* 50 */
	"",   "",   "",   "",   "",   "",   "",   "", "", "", /* 60 */
	"",   "",   "",   "",   "",   "",   "",   "", "", "", /* 70 */
	"",   "",   "",   "",   "",   "",   "",   "", "", "", /* 80 */
	"",   "",   "",   "",   "",   "",   "",   "", "", "", /* 90 */
	"",   "",   "",   "",   "",   "",   "",   "", "", "", /* 100 */
	"P ", "L ", "H ", "S ", "",   "R ", "B ", "", "", "", /* 110 */
	"pP", "pL", "pH", "pS", "G ", "pR", "pB", "K "        /* 118 */
	};

char	*brd_str[] = {
	"   ",
	"P ^", "L ^", "H ^", "S ^", "",    "R ^", "B ^", "", "", "",
	"pP^", "pL^", "pH^", "pS^", "G ^", "pR^", "pB^", "", "", "",
	"",    "",    "",    "",    "",    "",    "",    "", "", "",
	"",    "",    "",    "",    "",    "",    "",    "", "", "",
	"",    "",    "",    "",    "",    "",    "",    "", "", "",
	"",    "",    "",    "",    "",    "",    "",    "", "", "",
	"",    "",    "",    "",    "",    "",    "",    "", "", "",
	"",    "",    "",    "",    "",    "",    "",    "", "", "",
	"",    "",    "",    "",    "",    "",    "",    "", "", "",
	"",    "",    "",    "",    "",    "",    "",    "", "", "",
	"v P", "v L", "v H", "v S", "",    "v R", "v B", "", "", "",
	"vpP", "vpL", "vpH", "vpS", "v G", "vpR", "vpB", "v K"
	};

STATE	init_s;

LEAF	init_move;

STEM	mate_heap;

char	brd_line_n[] = "+---+---+---+---+---+---+---+---+---+\n";
char	brd_line_h[] = "+--+--+--+--+--+--+--+--+--+\n";

int	m_in_a_p, m_in_s_a, m_in_s_d, m_saved;
int	depth, d_max, new_moves;
int	sizes[100];
int	hp_flag;


/* Main flow
 *	collect agruments
 *	-h	use HP escape sequences
 *	-s0|1|2	run a standard problem	see tsumeinit.c for known timing
 *	-v1|2|3|4|5|6|7|8
 *		run one of a second set of problems not timed
 *	-b	run the monster problem
 *
 *	Initialize base state of board
 *	Get the initial state and location of all pieces
 *	get list of attacking moves
 *	make a move
 *	get list of defence responses
 *	make a move
 *	recurse on get list of attacking moves
 *	When recursion backs out to top level,
 *		print tree below first move and discard
 *	then step to next move until list exhausted
 *	stop.
 */

main ( argc, argv )
int	argc;
char	*argv[];
{	int	i, junk;
/* initializations */
	depth = 0;
	m_in_a_p = m_in_s_a = m_in_s_d = m_saved = 0;

	mate_heap = NULL;

	init_move.next = init_move.prev = init_move.prev_level = NULL;
	init_move.board_now = &init_s;

/* Clear the board and give all of the pieces to the defense. */
	for ( i = 0; i < 40 ; i++ )
		init_s.att_h[i] = init_s.board[i] = NULL;
	for ( i = 0; i < 18 ; i++ )
		init_s.def_h[i] = DEF_PAWN;
	for ( i = 18; i < 22 ; i++ )
		init_s.def_h[i] = DEF_LANCE;
	for ( i = 22; i < 26 ; i++ )
		init_s.def_h[i] = DEF_HORSE;
	for ( i = 26; i < 30 ; i++ )
		init_s.def_h[i] = DEF_SILVER;
	for ( i = 30; i < 34 ; i++ )
		init_s.def_h[i] = DEF_GOLD;
	init_s.def_h[34] = DEF_ROOK;
	init_s.def_h[35] = DEF_ROOK;
	init_s.def_h[36] = DEF_BISHOP;
	init_s.def_h[37] = DEF_BISHOP;
	init_s.def_h[38] = NULL;

	for ( i = 40; i < 91 ; init_s.board[i++] = NULL );

	king_x_pos = king_y_pos = 0;

/* If your terminal is an Hewlett Packard terminal then the display */
/* strings are significantly different. Use -h to set at run time.  */
	hp_flag = 0;

/* Check the arguments */
	while ( --argc > 0 )
	{	*(argv++);
		if ( strcmp ( *argv, "-h" ) == NULL )
		{	hp_flag = 1;
			continue;
		}
		if ( strcmp ( *argv, "-b" ) == NULL )
		{	setup_big ( &init_s );
			break;
		};
		if ( strcmp ( *argv, "-s0" ) == NULL )
		{	setup_s0 ( &init_s );
			break;
		};
		if ( strcmp ( *argv, "-s1" ) == NULL )
		{	setup_s1 ( &init_s );
			break;
		};
		if ( strcmp ( *argv, "-s2" ) == NULL )
		{	setup_s2 ( &init_s );
			break;
		};
		if ( strncmp ( *argv, "-v" ) == NULL )
		{	setup_v ( &init_s, argv[2] - '0' );
			break;
		};
/* This does not work yet!!!
/*		if ( *argv[0] != '-' )
/*			setup_file ( *argv );
 */
	}
/* Nor does this!!!
/*	if ( king_x_pos == 0 )
/*		setup_interactive ();
 */

/* Display the start position */
	print_board ( &init_s );

/* Set limits on the generation of the initial tree */
/* and generates the initial set of attacking moves */
	d_max = 1;
	att_phase ( &init_s, &init_move, &junk );

/* Solve the problem */
	while ( scan_tree_a ( &init_s, &init_move, &junk ) == TREE )
	{	if ( new_moves != 0 )
		{	for ( depth = 0; depth < 100 ; sizes[depth++] = 0 );
			summ_tree ( init_move.next_level, 0 );
/* trace */		printf ( "\n%d %d:", m_saved, d_max );
			for ( depth = 0; depth < 100 ; depth++ )
			{	if ( sizes[depth] != 0 )
					printf ( " %d", sizes[depth] );
				else	break;
			}
		}
		else	d_max++;
		new_moves = depth = 0;
	}

	printf ( "\nTree built. Printing." );
	printf ( "\n Tree summary : mates %d, %d",
			 m_saved, m_in_s_d );
	print_tree ( init_move.next_level, 0, 0 );

	printf ( "All Done.\n" );
}


/* Print tree
 *	This routine is called with a move tree.
 *	It scans the tree and types the termination points.
 *	If all terminators are of the same type, it prints
 *		the longest path in the tree.
 *	Otherwise it calls itself for each move in the top level.
 */

print_tree ( tree, l_mar, level )
STEM	tree;
int	l_mar, level;
{	STEM	this_l, this_m, p_tree;
	int	i;

	printf ( "\n" );
	while ( tree != NULL )
	{	i = 0;
		while ( i++ < l_mar )	printf ( " " );

		p_tree = ( tree->mate_twig != NULL ? tree->mate_twig : tree );
		if ( tree->loc_from_x == 0 )
			printf ( "%s dr %1d%1d",
				name_str[p_tree->piece_moving],
				p_tree->loc_to_x,
				p_tree->loc_to_y );
		else	printf ( "%s %1d%1d-%1d%1d",
				name_str[p_tree->piece_moving],
				tree->loc_from_x,
				tree->loc_from_y,
				p_tree->loc_to_x,
				p_tree->loc_to_y );

		if ( tree->promo_now == YES )
			printf ( "p  " );
		else	printf ( "   " );

		if ( tree->capture != NULL )
			printf ( "takes %s ", name_str[tree->capture] );

		if ( tree->mate_twig != NULL )
		{	printf ( " (stored)\n" );
			print_board ( p_tree->board_now );
		};

		if ( p_tree->next_level == NULL )
		{	if ( level == 0 )
				printf ("MATE\n");
			else	printf ("ESCAPED\n");
		}
		else if ( ( int ) p_tree->next_level == TREE )
			printf ( "pending\n" );
		else	print_tree ( p_tree->next_level,
					     l_mar+1, 1-level );

		tree = tree->next;
	}
}


/* Print Board
 *	This routine draws a representation of the board on the
 *	default output device.
 */

print_board ( brd )
I_STATE	brd;
{	int	i, j;

	printf ( "\n" );
	for ( j = 9; j < 90; j += 9 )
	{	if ( hp_flag == 0 )
		{	printf ( brd_line_n );
			for ( i = 9; i > 0 ; i-- )
			{	if ( brd->board[i+j] > 100 &&
				     brd->board[i+j] < 119 ||
				     brd->board[i+j] < 100 &&
				     brd->board[i+j] > 0 )
					printf ( "|%s", brd_str[brd->board[i+j]] );
				else	printf ( "|   " );
			}
		}
		else
		{	printf ( brd_line_h );
			for ( i = 9; i > 0 ; i-- )
			{	if ( brd->board[i+j] > 100 &&
				     brd->board[i+j] < 119 )
					printf ( "|\033&dB%s\033&d@",
						 name_str[brd->board[i+j]] );
				else if ( brd->board[i+j] < 100 &&
					  brd->board[i+j] > 0 )
					printf ( "|%s",
						 name_str[brd->board[i+j]] );
				else	printf ( "|  " );
			}
		}
		if ( j == 9 )
		{	printf ( "| In ATT Hand " );
			i = 0;
			while ( brd->att_h[i] != NULL )
				printf ( "%s", name_str[brd->att_h[i++]] );
			printf ( ".\n" );
		}
		else	printf ( "|\n" );
	};

	if ( hp_flag == 0 )
		printf ( brd_line_n );
	else	printf ( brd_line_h );
}


/* This routine is called with a board state.
 *	It generates a list of possible attacking moves, with
 *		the defense responses to each move.
 *	If there are none, it returns ESCAPED
 *	It calls def_phase for each possible move
 *	It def_phase returns MATED, it discards all other moves and
 *		sub-trees and returns MATED
 *	Otherwise it returns TREE
**** compare with def_phase and scan_tree_a because this routine is
**** a combination of the two.
 */

att_phase ( prev_s, prev_m, sub_size )
I_STATE	prev_s;
STEM	prev_m;
int	*sub_size;
{	STEM	this_l, this_m, t_move;
	I_STATE	new_s;
	int	result, sub_tree, junk;

/* At this point prev_s describes a position */

	depth++;
	junk = 0;

	this_l = att_move ( prev_s );
	prev_m->next_level = this_l;
	prev_m->mate_twig = NULL;

	if ( this_l == NULL )
		return ESCAPED;

	new_s = ( I_STATE ) malloc ( sizeof ( STATE ) );
	sub_tree = NULL;

	this_m = this_l;
	while ( this_m != NULL )
	{	*new_s = *prev_s;
		new_s->board[this_m->loc_from_x + 9 * this_m->loc_from_y]
			= NULL;
		new_s->board[this_m->loc_to_x + 9 * this_m->loc_to_y]
			= this_m->piece_moving + 10 * this_m->promo_now;

		if ( this_m->capture != NULL )
			captured ( new_s->att_h, this_m->capture );
		else if ( this_m->loc_from_x == 0 )
			dropping ( new_s->att_h, this_m->piece_moving );

		this_m->prev_level = prev_m;
		this_m->board_now = new_s;
		t_move = prev_m;
		while ( t_move != NULL )
		{	if ( same_state ( new_s,t_move->board_now ) == NULL )
			{	this_m->board_now = NULL;
				t_move = this_m;
				this_m = this_m->next;
				if ( t_move->prev != NULL )
					t_move->prev->next = this_m;
				else
				{	this_l = this_m;
					prev_m->next_level = this_l;
				}
				if ( this_m != NULL )
					this_m->prev = t_move->prev;
				free ( t_move );
				break;
			}
			else	t_move = t_move->prev_level;
		}
		if ( t_move != NULL )		continue;

		this_m->heap_head = NULL;
		result = NULL;

		this_m = this_m->next;
	}

	this_m = this_l;
	while ( this_m != NULL )
	{	*new_s = *prev_s;
		new_s->board[this_m->loc_from_x + 9 * this_m->loc_from_y]
			= NULL;
		new_s->board[this_m->loc_to_x + 9 * this_m->loc_to_y]
			= this_m->piece_moving + 10 * this_m->promo_now;

		if ( this_m->capture != NULL )
			captured ( new_s->att_h, this_m->capture );
		else if ( this_m->loc_from_x == 0 )
			dropping ( new_s->att_h, this_m->piece_moving );

		this_m->prev_level = prev_m;
		this_m->board_now = new_s;

		this_m->sub_tree_size = 0;
		result = def_phase ( new_s, this_m, &this_m->sub_tree_size );
		junk += this_m->sub_tree_size;
		depth--;

		if ( sub_tree == NULL )
			sub_tree = result;
		else if ( sub_tree != result )
			sub_tree = TREE;

		if ( result == MATED &&
		     this_m->loc_from_x == 0 &&
		     this_m->piece_moving == ATT_PAWN &&
		     this_m->next_level == NULL )
/* this is an illegal mate */
		{	t_move = this_m;
			this_m = this_m->next;

			if ( t_move->prev != NULL )
				t_move->prev->next = this_m;
			else	prev_m->next_level = this_l = this_m;

			if ( this_m != NULL )
				this_m->prev = t_move->prev;

			t_move->next = t_move->prev = NULL;
			free ( t_move );
			junk--;
		}
		else if ( result == MATED )
		{	t_move = this_m->next;
			this_m->next = NULL;
			discard ( t_move );

			if ( this_m->prev != NULL )
			{	this_m->prev->next = NULL;
				this_m->prev = NULL;
				discard ( this_l );
			};
			prev_m->next_level = this_m;
			this_m->board_now = new_s;
			this_m->sub_tree_size = 2;
			*sub_size += 2;
			return	MATED;
		}
		else	this_m = this_m->next;
		junk++;
	}

	prev_m->next_level = this_l;

	free ( new_s );
	*sub_size += junk;
	return	sub_tree;
}


/* this routine generates a defense sub tree
 *	It is passed a board state.
 *	It generates a list of all possible moves that avoid mated.
 *	If there are no such moves it returns MATED
 *	Otherwise the routine returns TREE
 */

def_phase ( prev_s, prev_m, sub_size )
I_STATE	prev_s;
STEM	prev_m;
int	*sub_size;
{	STEM	this_l, this_m, t_move;
	int	result;

/* At this point prev_s describes a position */

	depth++;

	this_l = def_move ( prev_s );
	prev_m->next_level = this_l;
	prev_m->mate_twig = NULL;

	if ( this_l == NULL )		return MATED;

	this_m = this_l;
	while ( this_m != NULL )
	{	this_m->prev_level = prev_m;
		this_m->next_level = ( STEM ) TREE;
		this_m->mate_twig = NULL;
		this_m = this_m->next;
		new_moves += 1;
		*sub_size += 1;
	}
	return	TREE;
}


/* This routine is called with a board state.
 *	It recurses down through the existing tree
 *	If the tree is complete, it returns the result.
 *	If the tree is incomplete, it calls att_phase and scan_tree_d 
 *	It cleans up the tree when appropriate
 *	It returns TREE if the tree is still incomplete
 */

scan_tree_a ( prev_s, prev_m, sub_size )
I_STATE	prev_s;
STEM	prev_m;
int	*sub_size;
{	STEM	this_l, this_m, t_move;
	I_STATE	new_s;
	int	result, sub_tree, junk;

/* At this point prev_s describes a position */

	depth++;
	junk = 0;

	this_l = prev_m->next_level;

/* this_l == NULL if this level of moves has been generated completely.
/* prev_m->mate_twig will point to the mate sub-tree if
/* it exists, otherwise it will be NULL.
 */
	if ( this_l == NULL )
	{	if ( prev_m->mate_twig == NULL )
			return ESCAPED;
		else	return MATED;
	}

/* We need to generate a new set of moves */
	result = NULL;
	if ( ( int ) this_l == TREE )
	{	depth--;
		result = att_phase ( prev_s, prev_m, &junk );
		*sub_size = junk;
		if ( result != TREE )		return ( result );
/* att_phase may have altered prev_m->next_level */
		this_l = prev_m->next_level;
		depth++;
	};

	new_s = ( I_STATE ) malloc ( sizeof ( STATE ) );
	sub_tree = NULL;

/* now we examine each of the generated moves */
	this_m = this_l;
	while ( this_m != NULL )
	{
/* This is to preferentially move pieces close to the enemies king.  */
/* d_max will eventually increase ensure that all moves are expanded */
		if ( sub_tree == TREE && this_m->distance > 6 + d_max )
		{	this_m = this_m->next;
			continue;
		};

/* This is to provide a good board state for scanning the next level. */
		*new_s = *prev_s;
		new_s->board[this_m->loc_from_x + 9 * this_m->loc_from_y]
			= NULL;
		new_s->board[this_m->loc_to_x + 9 * this_m->loc_to_y]
			= this_m->piece_moving + 10 * this_m->promo_now;

		if ( this_m->capture != NULL )
			captured ( new_s->att_h, this_m->capture );
		else if ( this_m->loc_from_x == 0 )
			dropping ( new_s->att_h, this_m->piece_moving );

		this_m->board_now = new_s;

		this_m->sub_tree_size = 0;
		result = scan_tree_d ( new_s, this_m, &this_m->sub_tree_size);
		junk += this_m->sub_tree_size;
		depth--;

/* This lets sub_tree reflect the overall state of the results of the next  */
/* level of moves. NULL is unset, TREE is unresolved, else MATED or ESCAPED */
		if ( sub_tree == NULL )
			sub_tree = result;
		else if ( sub_tree != result )
			sub_tree = TREE;

/* If MATED, go no further, junk every other alternative and return */
		if ( result == MATED )
		{
/* Discard subsequent alternatives. */
			t_move = this_m->next;
			this_m->next = NULL;
			discard ( t_move );

/* Discard everything we already checked out */
			if ( this_m->prev != NULL )
			{	this_m->prev->next = NULL;
				this_m->prev = NULL;
				discard ( this_l );
			};
/* Preserve this move and return */
			prev_m->next_level = this_m;
			this_m->board_now = new_s ;
			*sub_size += 2;
			return	MATED;
		}
		else	this_m = this_m->next;
	}

/* To end up here, the result is either ESCAPED or TREE   */
/* So we add the list to the tree, free up the temporary  */
/* board and return the net result. junk is an inaccurate */
/* count of the size of the tree at this level and below. */
 	prev_m->next_level = this_l;

	free ( new_s );
	*sub_size += junk;
	return	sub_tree;
}


/* this routine scans a defense sub tree
 *	It is passed a board state.
 *	It generates a list of all possible moves that avoid mate.
 *	If there are no such moves it returns MATED
 *	It calls att_phase for every move in the list.
 *	If any move results in ESCAPED, all other moves in the tree are
 *		discarded and the routine returns ESCAPED
 *	Otherwise the routine returns TREE
 */

scan_tree_d ( prev_s, prev_m, sub_size )
I_STATE	prev_s;
STEM	prev_m;
int	*sub_size;
{	STEM	this_l, this_m, t_move;
	I_STATE	new_s;
	int	result, sub_tree, list_len, junk;

/* At this point prev_s describes a position */

	depth++;

	this_l = prev_m->next_level;

	if ( this_l == NULL )	return MATED;

/* Limit the depth of the scan */
	if ( depth > d_max * d_max )	return TREE;

	this_m = this_l;
	list_len = 0;
/* Limit the width of the scan */
	while ( this_m != NULL && list_len <= d_max - ( depth / d_max ) )
	{	if ( this_m->loc_from_x != 0 &&
		     this_m->mate_twig == NULL )
			list_len++;
		this_m = this_m->next;
	};
	if ( list_len > d_max - ( depth / d_max ) )
	{	*sub_size += list_len;
		return TREE;
	};

	new_s = ( I_STATE ) malloc ( sizeof ( STATE ) );
	sub_tree = NULL;

/* loc_from_x is set to 0 to indicate a drop */
/* drops are expanded only if we have nothing better to look at */
/* this is because the response to a drop is probably the same  */
/* regardless of what was dropped. */
	junk = list_len;
	this_m = this_l;
	while ( this_m != NULL )
	{	if ( sub_tree == TREE &&
		     ( this_m->loc_from_x == 0 ||
		       this_m->distance > d_max * d_max ) )
		{	this_m = this_m->next;
			continue;
		};

/* create a correct board state for the move we are looking at */
		*new_s = *prev_s;
		new_s->board[this_m->loc_from_x + 9 * this_m->loc_from_y]
			= NULL;
		new_s->board[this_m->loc_to_x + 9 * this_m->loc_to_y]
			= this_m->piece_moving + 10 * this_m->promo_now;

		if ( this_m->capture != NULL )
			captured ( new_s->def_h, this_m->capture );
		else if ( this_m->loc_from_x == 0 )
			dropping ( new_s->def_h, this_m->piece_moving );

		this_m->board_now = new_s;

		result = NULL;
/* new mates are added to the head of mate_heap */
/* head_head is the last value of mate_heap we  */
/* checked against. This code checks to see if  */
/* the board state we just built matches one on */
/* the mate_heap, fairly efficiently.		*/
		if ( this_m->mate_twig == NULL &&
		     this_m->heap_head != mate_heap )
		{	t_move = mate_heap;
			while ( t_move != NULL )
			{	if ( same_state ( new_s, t_move->board_now )
				     == NULL )
				{	discard ( this_m->next_level );
					this_m->next_level = NULL;
					this_m->mate_twig = t_move;
					m_in_s_d++;
					junk = 1;
					result = MATED;
					break;
				}
				else	t_move = t_move->next;
			};
			this_m->heap_head = mate_heap;
		};
/* Nothing so far, so we check the level below. */
		if ( result == NULL )
		{	result = scan_tree_a ( new_s, this_m, &junk );
			depth--;
		}

/* Maintain net result */
		if ( sub_tree == NULL )
			sub_tree = result;
		else if ( sub_tree != result )
			sub_tree = TREE;

/* If the net result from below is now MATED we   */
/* move it onto mate_heap and tidy up afterwards. */
		if ( result == MATED &&
		     this_m->next_level != NULL )
		{	this_m->board_now =
				 ( I_STATE ) malloc ( sizeof ( STATE ) );
			*(this_m->board_now) = *new_s;
			t_move = ( STEM ) malloc ( sizeof ( LEAF ) );
			*t_move = *this_m;
			this_m->next_level = NULL;
			this_m->mate_twig = t_move;
			t_move->next = mate_heap;
			mate_heap = t_move;
			m_saved++;
			this_m = this_m->next;
		}
/* If the result is escaped, we simply clean up. */
		else if ( result == ESCAPED )
		{	t_move = this_m->next;
			this_m->next = NULL;
			discard ( t_move );

			if ( this_m->prev != NULL )
			{	this_m->prev->next = NULL;
				this_m->prev = NULL;
				discard ( this_l );
				prev_m->next_level = this_m;
			}

			free ( new_s );
			*sub_size += 2;
			return ESCAPED;
		}
		else	this_m = this_m->next;
	}
	free ( new_s );
	*sub_size += junk;
	return	sub_tree;
}


/* This routine is used to adjust the list when */
/* piece is captured. The piece is reset to its */
/* unpromoted value and entered in the list at  */
/* an appropriate point.			*/
captured ( lis, piece )
char	*lis, piece;
{	int	i;

	i = 0;
	if ( piece > 110 && piece != DEF_GOLD )
		piece -= 110;
	else if ( piece > 100 )
		piece -= 100;
	else if ( piece > 10 && piece != ATT_GOLD )
		piece +=  90;
	else	piece += 100;

	while ( lis[i++] != NULL );

	if ( i-- == 1 )
	{	lis [0] = piece;
		return;
	};

	while ( lis[--i] > piece )
		lis[i+1] = lis[i];

	lis[i+1] = piece;

	return;
}


/* This routines is used to adjust the list of */
/* pieces in hand whenever a piece is dropped. */
dropping ( list, piece )
char	list[], piece;
{	register int	i;

	i = 0;
	while ( list[i] != piece )	i++;

	while ( list[i++] != NULL )
		list[i-1] = list[i];
}


/* This routine scans the tree to find the number of moves generated */
/* for each of the first hundred levels. Printing this at the end of */
/* each full scan of the tree gives a picture of how the work is     */
/* progressing. The numbers are not accurate as the mate_heap is     */
/* ignored.							     */
summ_tree ( tree, deep )
STEM	tree;
int	deep;
{	if ( deep > 99 )	return;

	while ( tree != NULL )
	{	sizes[deep]++;
		if ( ( int ) tree->next_level != TREE &&
		     tree->next_level != NULL )
			summ_tree ( tree->next_level, deep + 1 );
		tree = tree->next;
	}
}