schmidtg@iccgcc.decnet.ab.com (10/16/90)
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
=============================================================================mwnewman@watmsg.waterloo.edu (mike newman) (10/19/90)
In article <1450.2719bf62@iccgcc.decnet.ab.com> you write: > >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. Intereseting you should mention this. I'm doing exactly the same thing with an othello playing program. I haven't gotten very far, as I only last week found a un*x forth to run. The way I think I'll handle it is to define a seperate stack for alpha, beta, depth. Set it up analogously to the return stack, ie: define words like alpha-pop, alpha-push, alpha@ <==> r>, >r, r@ something like: variable alpha-stack 100 allot variable alpha-pointer alpha-stack alpha-pointer ! ( stack growing upwards - why not ? ) : alpha-pop alpha-stack @ 4 ( or 2 for 16-bit forths ) alpha-pointer -! ; : alpha-push 4 alpha-pointer +! alpha-stack ! ; : alpha@ alpha-stack @ ; : alpha-drop 4 alpha-pointer -! ; Now this looks like it might involve a lot of overhead, BUT: code these in assembly language. The only overhead is fetching and storing the stack pointers. And you could even keep these stack pointers in registers and kill that little bit of overhead too. code alpha-pop move alpha-pointer,r0 move (r0)+,-(sp) move r0,alpha-pointer c; better yet: (better for speed...) code alpha-pop move (r57)+,-(sp) ; r57 is reserved for alpha stack-pointer c; Note that this last is likely faster (depending on the machine) then a normal variable "@", or a frame pointer approach, since you don't have any literal offset to deal with. Of course this assumes that there are free registers, that are not being used by anything else. Then again, depending on the machine, the first may reduce to a single instruction too. I can't think of any other efficient way to do this, but then I often can't think of what day it is today :-) Hope this helps. I'd be interested in hearing about any other suggestions you get. mike newman mwnewman@msg.waterloo.edu