Path: utzoo!attcan!uunet!tut.cis.ohio-state.edu!usenet.ins.cwru.edu!abvax!iccgcc!schmidtg
From: schmidtg@iccgcc.decnet.ab.com
Newsgroups: comp.lang.forth
Subject: How do I do this in FORTH?
Message-ID: <1450.2719bf62@iccgcc.decnet.ab.com>
Date: 15 Oct 90 18:53:38 GMT
Lines: 106


I'm new to this news group and I'm also relatively new at writing
non-trivial Forth programs.  I have written a 3-D Tic-Tac-Toe playing
program in 'c' which I am now trying to convert to Forth.  All has
been going smoothly so far until attempting to write the minimax
routine in Forth.  The minimax routine is responsible for performing
a depth first search and is therefore recursive.  The current 'c'
implementation requires three arguments along with four automatic
variables which constitute a new stack frame for each recursive
invocation.  The problem I am encountering in Forth is the difficulty
of accessing seven variables on the stack while still using the
stack for intermediate results.  Forth seems to do well when the
number of items on the stack is no greater than four.  It seems
like my attempts so far have resulted in very awkward code.  I'm
looking for ideas/solutions to this problem.  I don't see how this
routine could be easily factored to resolve this problem, especially
since it is recursive.  Also, using variables is out of the question
as context must be preserved during recursion.  I have considered
defining some scheme for maintaining a "frame pointer" and allowing me
to reference variables off the stack symbolically.  This seems like
overkill, and would probably be very inefficient.  I seem to be at a
roadblock here and I wonder if I have just managed to find an application
that Forth is not very good at.  All ideas are welcome.

The "minimax" routine as written in 'c'...


int minimax(level,alpha,beta,pbest_move)
int level;
int alpha, beta;
int *pbest_move;
{
	int temp_move, the_move;
	int temp_score;
	int node_type;

	temp_move = -1;
	if ( ((temp_move = next_move(temp_move)) < 0)
		|| level == MAX_LEVEL
		|| win_check() )
			node_type = TERM;
	else
	{
		if (level & 1) /* odd ply */
			node_type = MIN;
		else /* even ply */
			node_type = MAX;
	}

	if (node_type == TERM) /* terminal node */
		return(static_eval());
	else
	{
		do {
			make_move(level,temp_move);
			temp_score = minimax(level+1,alpha,beta,&the_move);
			unmake_move(temp_move);
			if (node_type == MAX)
			{
				if (temp_score > alpha)
				{
					alpha = temp_score;
					*pbest_move = temp_move;
				}
			}
			else
			{
				if (temp_score < beta)
				{
					beta = temp_score;
					*pbest_move = temp_move;
				}
			}

		} while ( ((temp_move = next_move(temp_move)) > 0)
			&& alpha < beta);
		if (alpha >= beta)
		{
			if (node_type == MAX)
				a_cut++;
			else
				b_cut++;
		}
		if (node_type == MAX)
			return(alpha);
		else
			return(beta);
	}
}

-------------------------------------------------------------------------
| Greg Schmidt				| Not much of a .sig right now! |
| schmidtg@iccgcc.decnet.ab.com		|                               |
-------------------------------------------------------------------------

-- 


=============================================================================
Disclaimer: If I ever had a truly original idea I wouldn't share it with you!
-----------------------------------------------------------------------------
"People with nothing to hide have nothing to fear from O.B.I.T"
	-- Peter Lomax
=============================================================================
Greg Schmidt -> schmidtg@iccgcc.decnet.ab.com
=============================================================================