|
Vince Mounts writes:
> First a message to Gary. I would love to see your move generating code.
OK, I'll include it at the end of this article. (I edited it slightly
so the code matches what we actually ended up talking about, so it doesn't
generate an explicit list any more).
> As far as the better method for controlling move input... It seems to me
> that Gary's solution is very good for a neural net that needs a list of
> moves to evaluate also. And is a nice useful and reusable routine.
> However I see potential problems for user interface design. The only way
> it would really work is of the person can move any checker anywhere they
> want. Even onto the opponents points,, and then once "enter" is hit the
> program decides if this legal(here i am making the assumption that it is
> only the final positions that are being generated,,, if the actual code
> is for individual checkers then most of the rest of this post is a moot
> point). Otherwise there will be a need for code that determines if each
> move is valid.
Yes, you're entirely right. The code does only check the final
position. Whether you WANT a program to check for legal moves on a
chequer-by-chequer basis or only when the user attempts to "enter"
their move is a matter of opinion. Personally, I have tried using
programs that attempt to enforce legal moves chequer by chequer, and I
don't like them. I realise there will be users that prefer this
behaviour, though. Ideally I suppose a program should be configurable
to support whichever model the user prefers, but my code can't cope
with that :-) Your ideas certainly sound like a valid approach to
achieving the chequer-by-chequer play.
As a brief justification of why I _don't_ like chequer-by-chequer
verification: sometimes I WANT to make "mistakes"! That might sound
stupid, but consider what you do when you play backgammon on a real
board. You experiment with moves; you play some and take them back;
the board is never necessarily in a legal state except before you
start to move and (hopefully! :-) when you pick up your dice. Suppose
I roll 62; I want to be able to "drag" a chequer from my midpoint to
my bar, then from my 6 point to the 4; change my mind, drag the
chequer off my bar and drop it on my 11 instead, etc. I have never
seen a "chequer-by-chequer" style interface that would let me play
this way without fighting it every step of the way (hitting "undo"
every time I change my mind). I would rather have complete control
over the chequers until I pick up my dice (at which point the annoying
box on my desk is permitted to complain if I did something naughty).
The only time the chequer-by-chequer style actually _helps_ the user
is when they accidentally move a chequer the wrong number of pips,
say. Personally I don't think it's worth the hassle (I would guess
that I typically want to "experiment" with moves at least once every
game, and on average I'd make a mistake that would be caught by the
chequer verification less than once a game). It's not worth the
occasional frustration of wanting to tell the computer "Yes, I KNOW
it's wrong! If you'll just let me do it MY way, I'll fix it in a
moment!"
Now that I've thought about it a bit, I guess the optimal behaviour
would be to permit _all_ chequer moves (until the dice are picked up,
at which point illegal moves are rejected), but give enough visual
feedback during the move that the user knows which chequer plays are
legal.
If anybody wants other code, there are a few files in
ftp://ftp.cs.arizona.edu/people/gary/ that may be of interest:
neuralnet.tar.gz - bare bones neural net library; it handles feed-forward
MLPs of arbitrary size with a single hidden layer and will perform
evaluations and standard (supervised) backprop training and read and
write weights from/to streams. This is the basic stuff you'd come up
with by reading any standard NN textbook; no backgammon specific code,
I'll make that available one day when I get around to it.
prime-0.0e.tar.gz - Unix X11 FIBS client. Tries to draw a pretty board :-)
(see board.jpg)
sigmoid.c - fast polynomial sigmoid function for use in neural nets.
Includes a SPARC assembly language version (if compiling on a SPARC)
that calculates about 2.2 million sigmoids per second on an Ultra 170.
Cheers,
Gary.
------------8<------------ cut here ------------8<------------
/*
* Code for checking the legality of a backgammon move.
*
* by Gary Wong, 1997-8.
*
* Takes a starting position, ending position and dice roll as input,
* and as output tells you whether the "move" to the end position was
* legal, and if so, gives a chequer-by-chequer description of what the
* move was.
*
* Boards are represented as arrays of 28 ints for the 24 points (0 is
* the opponent's bar; 1 to 24 are the board points from the point of
* view of the player moving; 25 is the player's bar; 26 is the player's
* home and 27 is the opponent's home (unused)). The player's chequers
* are represented by positive integers and the opponent's by negatives.
* This is compatible with FIBS or pubeval or something like that, I
* forget who I originally stole it from :-) The dice roll is an array of
* 2 integers. The function returns true if the move is legal (and fills
* in the move array with up to 4 moves, as source/destination pairs),
* and zero otherwise. For instance, playing an opening 31 as 8/5 6/5
* would be represented as:
anBoardPre[] = { 0 -2 0 0 0 0 5 0 3 0 0 0 -5 5 0 0 0 -3 0 -5 0 0 0 0 2 0 0 0 }
anBoardPost[] = { 0 -2 0 0 0 2 4 0 2 0 0 0 -5 5 0 0 0 -3 0 -5 0 0 0 0 2 0 0 0 }
anRoll[] = { 3 1 }
* and LegalMove( anBoardPre, anBoardPost, anRoll, anMove ) would return true
* and set anMove[] to { 8 5 6 5 0 0 0 0 }.
*/
typedef struct {
int fFound, cMaxMoves, cMaxPips, cMoves, cPips, *anBoard, *anRoll,
*anMove;
} movedata;
void ApplyMove( int anBoard[], int iSrc, int nRoll ) {
int iDest = iSrc - nRoll;
if( iDest < 1 )
iDest = 26;
anBoard[ iSrc ]--;
if( anBoard[ iDest ] < 0 ) {
anBoard[ iDest ] = 1;
anBoard[ 0 ]++;
} else
anBoard[ iDest ]++;
}
int EqualBoard( int an0[], int an1[] ) {
int i;
for( i = 0; i < 28; i++ )
if( an0[ i ] != an1[ i ] )
return 0;
return 1;
}
int CanMove( int anBoard[], int iSrc, int nPips ) {
int i, nBack = 0, iDest = iSrc - nPips;
if( iDest > 0 )
return ( anBoard[ iDest ] >= -1 );
for( i = 1; i < 26; i++ )
if( anBoard[ i ] > 0 )
nBack = i;
return ( nBack <= 6 && ( iSrc == nBack || !iDest ) );
}
void SaveMoves( int cMoves, int cPips, int anBoard[ 28 ], int anMove[ 8 ],
movedata *pmd ) {
int i;
if( cMoves < pmd->cMaxMoves || cPips < pmd->cMaxPips )
return;
pmd->cMaxMoves = cMoves;
pmd->cMaxPips = cPips;
if( EqualBoard( anBoard, pmd->anBoard ) ) {
pmd->fFound = 1;
pmd->cMoves = cMoves;
pmd->cPips = cPips;
for( i = 0; i < 8; i++ )
pmd->anMove[ i ] = i < cMoves * 2 ? anMove[ i ] : 0;
} else if( pmd->cMaxMoves > pmd->cMoves || pmd->cMaxPips > pmd->cPips )
pmd->fFound = 0;
}
int GenerateMoves( int anBoard[ 28 ], int nMoveDepth, int iPip, int cPip,
int anMove[ 8 ], movedata *pmd ) {
int i, iCopy, fUsed = 0;
int anBoardNew[ 28 ];
if( nMoveDepth > 3 || !pmd->anRoll[ nMoveDepth ] )
return -1;
if( anBoard[ 25 ] ) {
if( anBoard[ 25 - pmd->anRoll[ nMoveDepth ] ] <= -2 )
return -1;
anMove[ nMoveDepth * 2 ] = 25;
anMove[ nMoveDepth * 2 + 1 ] = 25 - pmd->anRoll[ nMoveDepth ];
for( i = 0; i < 28; i++ )
anBoardNew[ i ] = anBoard[ i ];
ApplyMove( anBoardNew, 25, pmd->anRoll[ nMoveDepth ] );
if( GenerateMoves( anBoardNew, nMoveDepth + 1, 24, cPip +
pmd->anRoll[ nMoveDepth ], anMove, pmd ) )
SaveMoves( nMoveDepth + 1, cPip + pmd->anRoll[ nMoveDepth ],
anBoardNew, anMove, pmd );
return 0;
} else {
for( i = iPip; i; i-- )
if( anBoard[ i ] > 0 && CanMove( anBoard, i,
pmd->anRoll[ nMoveDepth ] ) ) {
anMove[ nMoveDepth * 2 ] = i;
anMove[ nMoveDepth * 2 + 1 ] = i - pmd->anRoll[ nMoveDepth ];
if( anMove[ nMoveDepth * 2 + 1 ] < 1 )
anMove[ nMoveDepth * 2 + 1 ] = 26;
for( iCopy = 0; iCopy < 28; iCopy++ )
anBoardNew[ iCopy ] = anBoard[ iCopy ];
ApplyMove( anBoardNew, i, pmd->anRoll[ nMoveDepth ] );
if( GenerateMoves( anBoardNew, nMoveDepth + 1, pmd->anRoll[ 0 ]
== pmd->anRoll[ 1 ] ? i : 24, cPip +
pmd->anRoll[ nMoveDepth ], anMove, pmd ) )
SaveMoves( nMoveDepth + 1, cPip +
pmd->anRoll[ nMoveDepth ], anBoardNew, anMove,
pmd );
fUsed = 1;
}
}
return fUsed ? 0 : -1;
}
int LegalMove( int anBoardPre[ 28 ], int anBoardPost[ 28 ], int anRoll[ 2 ],
int anMove[ 8 ] ) {
movedata md;
int i, anMoveTemp[ 8 ], anRollRaw[ 4 ];
int fLegalMoves;
md.fFound = md.cMaxMoves = md.cMaxPips = md.cMoves = md.cPips = 0;
md.anBoard = anBoardPost;
md.anRoll = anRollRaw;
md.anMove = anMove;
anRollRaw[ 0 ] = anRoll[ 0 ];
anRollRaw[ 1 ] = anRoll[ 1 ];
anRollRaw[ 2 ] = anRollRaw[ 3 ] = ( anRoll[ 0 ] == anRoll[ 1 ] ) ?
anRoll[ 0 ] : 0;
fLegalMoves = !GenerateMoves( anBoardPre, 0, 24, 0, anMoveTemp, &md );
if( anRoll[ 0 ] != anRoll[ 1 ] ) {
anRollRaw[ 0 ] = anRoll[ 1 ];
anRollRaw[ 1 ] = anRoll[ 0 ];
fLegalMoves |= !GenerateMoves( anBoardPre, 0, 24, 0, anMoveTemp, &md );
}
if( !fLegalMoves ) {
for( i = 0; i < 8; i++ )
anMove[ i ] = 0;
return EqualBoard( anBoardPre, anBoardPost );
}
return md.fFound;
}
--
Gary Wong, Department of Computer Science, University of Arizona
gary@cs.arizona.edu http://www.cs.arizona.edu/~gary/
|
![[Recommended reading]](pics/Star2.gif)
![[Long message]](pics/Long.gif)
![[GammOnLine forum]](pics/GammOnLine.gif)
From GammOnLine
![[Recent addition]](pics/New.gif)
Recent addition