FIBS software bugs..?
Murat Kalinyaprak
sotware I'm using or in the FIBS server may make
some innocent cases look like drops on the last move
of a game/match.
At the very end, if you have one last piece left on
your 4 point for example, and you roll a 62, 51, etc.
you're obligated to play the smaller number first
before you can bear it off with the bigger number.
Two such cases happened to me earlier and I was upset
thinking that the other player had dropped on my last
move while I was winning. What had actually happened
was that either the server or the interface software
hadn't accepted my move (i.e. bearing of the last
piece with the bigger number) and the other side had
probably disconnected after a few seconds thinking
that the game/match was over properly.
I hope the server or the interface software people
will get to read this so that they can correct this
problem which may already have had or will cause
players to incorrectly blame others for dropping...
Another "bug" in the BBT beta software causes you
to accept an invitation if the dialog box pops up on
the screen while you are typing a message. It looks
like pressing the space-bar has the same effect as
clicking on the "accept" button? This happened to me
numerous times. At the beginning, I even quit a few
such matches with the consent of the opponent and
with no moves made yet (whithout realizing that they
become recorded in your saved matches list). At times
it happened as I was typing a goodbye message getting
ready to log off and I just had to tell the inviter
that we had to resume/play it some other time. Having
to go through with playing matches that you haven't
intended to play gets pretty annoying after a while.
I hope the sofware's developers do something about
this also...
MK
Marie1948
>From: mu...@cyberport.net (Murat Kalinyaprak)
>At the very end, if you have one last piece left on
>your 4 point for example, and you roll a 62, 51, etc.
>you're obligated to play the smaller number first
>before you can bear it off with the bigger number.
I'm pretty sure if you 'toggle automove' the
move will be done automatically.
Cthulhu
> One thing I would consider a "bug" in the BBT beta
> sotware I'm using or in the FIBS server may make
> some innocent cases look like drops on the last move
> of a game/match.
>
> At the very end, if you have one last piece left on
> your 4 point for example, and you roll a 62, 51, etc.
> you're obligated to play the smaller number first
> before you can bear it off with the bigger number.
>
> Two such cases happened to me earlier and I was upset
> thinking that the other player had dropped on my last
> move while I was winning. What had actually happened
> was that either the server or the interface software
> hadn't accepted my move (i.e. bearing of the last
> piece with the bigger number) and the other side had
> probably disconnected after a few seconds thinking
> that the game/match was over properly.
>
> I hope the server or the interface software people
> will get to read this so that they can correct this
> problem which may already have had or will cause
> players to incorrectly blame others for dropping...
>
I don't know how the rules are in real-life BG. Not that it really
will matter there, since the result will be the same, but do you need
to perform both moves at the end or are you sllowed to just move it
out in one? What do the rules say about this?
This thing might take a lot of code to fix since FIBS can't deal
with it and I don't think the author(s) think(s) it's worth it, but I
might be wrong. However, if BB(G?)T let you execute the move when you
had moved only one piece, then I would call it a bug which should be
fixed because of the way FIBS deals with this.
This "bug" exists in my client too at the moment (I think), but you
won't be able to send the move to the server at least.
> Another "bug" in the BBT beta software causes you
> to accept an invitation if the dialog box pops up on
> the screen while you are typing a message. It looks
> like pressing the space-bar has the same effect as
> clicking on the "accept" button? This happened to me
> numerous times. At the beginning, I even quit a few
> such matches with the consent of the opponent and
> with no moves made yet (whithout realizing that they
> become recorded in your saved matches list). At times
> it happened as I was typing a goodbye message getting
> ready to log off and I just had to tell the inviter
> that we had to resume/play it some other time. Having
> to go through with playing matches that you haven't
> intended to play gets pretty annoying after a while.
> I hope the sofware's developers do something about
> this also...
It's not a bug, merely an annoying "feature". Guess the author would
gain in taking an HCI (human computer interaction) course. ;) This
"feature" is a complete no-no to do. But after all, the program is
still beta so anything can happen yet.
I must admit that I also have such a "bug" in a place in my prog but
it will disappear when I get the time.
If you're not happy with the software, use something else. There are
lots of fish in the sea. Maybe something else will make you less
frustrated.
--
Cthulhu
--
That is not dead which can eternal lie,
And with strange aeons even death may die.
Cthulhu
> This thing might take a lot of code to fix since FIBS can't deal
> with it and I don't think the author(s) think(s) it's worth it, but I
> might be wrong. However, if BB(G?)T let you execute the move when you
I take this back. It's pretty simple. It will only take one line of
code (in my client at least). You will still have to make two moves
though, but it won't let you bear off with the highest first.
Letting you bear off with the highest first too, that's another story,
which might suit my quoted text better.
Gary Wong
> Cthulhu wrote:
> > This thing might take a lot of code to fix since FIBS can't deal
> > with it and I don't think the author(s) think(s) it's worth it, but I
> > might be wrong. However, if BB(G?)T let you execute the move when you
>
> I take this back. It's pretty simple. It will only take one line of
> code (in my client at least). You will still have to make two moves
> though, but it won't let you bear off with the highest first.
>
> Letting you bear off with the highest first too, that's another story,
> which might suit my quoted text better.
It depends what you mean by "a lot of code" :-)
The obvious brute force method is to generate all legal moves from a
position and compare the position the user wants to submit to each of
them in turn. If you find a match, play the corresponding move. If
not, the move is illegal.
I've done this in about 50 lines of C. If anybody is interested, I
can post it, e-mail it, or put it up for FTP.
Cheers,
Gary.
--
Gary Wong, Department of Computer Science, University of Arizona
ga...@cs.arizona.edu http://www.cs.arizona.edu/~gary/
John Goodwin
>
>It's not a bug, merely an annoying "feature". Guess the author would
>gain in taking an HCI (human computer interaction) course. ;) This
>"feature" is a complete no-no to do. But after all, the program is
>still beta so anything can happen yet.
This is really a microsoft cock up. They have arranged that a space
operates the default button.
You thus get this problem with any window that will pop up
asynchronously.
Thus, if in the control room of a large nuclear reactor, the message:
"Press red button to avoid immediate meltdown"
Appears with an OK button set as default, and the engineer is, say, in
the middle of typing some text into a log, and happens to hit the
space bar just as the message is appearing ....
JG
Cthulhu
I was meaning the popping up of a dialog window out of nowhere.
That's a really bad way to handle it and marked as no-no in HCI.
Never ever bring up windows if the user doesn't ask for them, unless
(s)he's about to do something that (s)he might regret a split second
later. Or as in your example above where there are danger involved.
"Are you not sure you don't want to cancel the re-format of your
hardrive? Yes / No".
Cthulhu
> "Cthulhu" <-@earthdome.com> writes:
> > Cthulhu wrote:
> > > This thing might take a lot of code to fix since FIBS can't deal
> > > with it and I don't think the author(s) think(s) it's worth it, but I
> > > might be wrong. However, if BB(G?)T let you execute the move when you
> >
> > I take this back. It's pretty simple. It will only take one line of
> > code (in my client at least). You will still have to make two moves
> > though, but it won't let you bear off with the highest first.
> >
> > Letting you bear off with the highest first too, that's another story,
> > which might suit my quoted text better.
>
> It depends what you mean by "a lot of code" :-)
>
> The obvious brute force method is to generate all legal moves from a
> position and compare the position the user wants to submit to each of
> them in turn. If you find a match, play the corresponding move. If
> not, the move is illegal.
>
> I've done this in about 50 lines of C. If anybody is interested, I
> can post it, e-mail it, or put it up for FTP.
>
50 lines I definitely call a lot of code! I have a lot better solution
than this (guess I have to learn to have afterthoughts before
posting).
If the user tries to bear off with a one-die-move when he only have
one blot left and he must make two moves, all you need to do is
transform this move into one that moves the lowest die first and then
the highest. Piece of cake! It will take 2-4 lines of code for me.
The question is, should I implement it this way? Doesn't the rules say
that you *have* to move both dice if possible? Anyone has an opinion
about this?
Gary Wong
> Gary Wong wrote:
> > I've done this in about 50 lines of C. If anybody is interested, I
> > can post it, e-mail it, or put it up for FTP.
>
> 50 lines I definitely call a lot of code! I have a lot better solution
> than this (guess I have to learn to have afterthoughts before
> posting).
> If the user tries to bear off with a one-die-move when he only have
> one blot left and he must make two moves, all you need to do is
> transform this move into one that moves the lowest die first and then
> the highest. Piece of cake! It will take 2-4 lines of code for me.
> The question is, should I implement it this way? Doesn't the rules say
> that you *have* to move both dice if possible? Anyone has an opinion
> about this?
Sure, that solves that particular instance of the problem, but not the
problem in general. It does nothing to enforce the rule that if only
one die can be played, then (if possible) the larger one must be used,
for instance.
I guess it all depends what problem you're trying to solve.
Cthulhu
> "Cthulhu" <-@earthdome.com> writes:
> > Gary Wong wrote:
> > > I've done this in about 50 lines of C. If anybody is interested, I
> > > can post it, e-mail it, or put it up for FTP.
> >
> > 50 lines I definitely call a lot of code! I have a lot better solution
> > than this (guess I have to learn to have afterthoughts before
> > posting).
[SNIP]
> Sure, that solves that particular instance of the problem, but not the
> problem in general. It does nothing to enforce the rule that if only
> one die can be played, then (if possible) the larger one must be used,
> for instance.
>
> I guess it all depends what problem you're trying to solve.
Guess I forgot about that rule, and also the problem that you can move
the first blot so your second move will be impossible to perform. Any
more traps one have to think about?
Re-reading your original post, I also think I misunderstood what your
50 lines of code were doing. Your code is dealing with the whole
moving procedure, not just the special moves, isn't it? Anyhow, I
don't think it's an elegant way of solving it. It just takes too much
CPU time (not that it will bother the user since it will be fast in
most computers anyway). A better way, IMHO, is to check if the move
the player tries to perform is legal, and deal with the special
positions separately. Takes a lot less CPU, although I'm not sure if
it's less code.
Gary Wong
> Gary Wong wrote:
> > Sure, that solves that particular instance of the problem, but not the
> > problem in general. It does nothing to enforce the rule that if only
> > one die can be played, then (if possible) the larger one must be used,
> > for instance.
> >
> > I guess it all depends what problem you're trying to solve.
>
> Guess I forgot about that rule, and also the problem that you can move
> the first blot so your second move will be impossible to perform. Any
> more traps one have to think about?
Maybe, maybe not :-) That's why I use a simple solution (because I can
easily satisfy myself that it is correct) than a collection of
heuristics that were added to deal with every special case I could
think of (and hope that I did think of every special case).
> Re-reading your original post, I also think I misunderstood what your
> 50 lines of code were doing. Your code is dealing with the whole
> moving procedure, not just the special moves, isn't it?
Yes. The input is a board position and dice roll; the output is a
list of legal moves.
> Anyhow, I don't think it's an elegant way of solving it.
True. I'm certain that there ARE sets of heuristics you can apply
that will determine if an input move is legal, and which you can prove
are correct, but I haven't looked for any because the simple solution
seems adequate.
It would be interesting to find the smallest set of heuristics to
determine if a move is legal, but I haven't tried that myself.
> It just takes too much CPU time (not that it will bother the user
> since it will be fast in most computers anyway). A better way, IMHO,
> is to check if the move the player tries to perform is legal, and deal
> with the special positions separately. Takes a lot less CPU, although
> I'm not sure if it's less code.
You're right that there are less expensive solutions, but I am sure it
makes no difference in practice. A while ago I profiled the execution
of one of my programs (a neural net that plays against itself to
generate training data) to look for worthwhile parts to optimise. I
just had another look at the output to see how much time was being
spent in the move generator, and it was too small to measure -- the
profiler lists other measurements to a granularity of 10 microseconds,
so we assume it takes under 10 microseconds on average to generate a
list of legal moves. Considering that it takes me over 300
microseconds to perform a static evaluation of a position, and this
will have to be done for every single move that's generated, the (less
than) 10 microseconds it takes to generate all moves in the first
place is insignificant.
If you can think of an application where 10 microseconds to generate
all moves IS too slow, then I'll happily admit that my simple approach
is inadequate and some heuristics are called for :-)
Vince Mounts
>makes no difference in practice. A while ago I profiled the execution
>of one of my programs (a neural net that plays against itself to
>generate training data) to look for worthwhile parts to optimise. I
>just had another look at the output to see how much time was being
>spent in the move generator, and it was too small to measure -- the
>profiler lists other measurements to a granularity of 10 microseconds,
>so we assume it takes under 10 microseconds on average to generate a
>list of legal moves. Considering that it takes me over 300
>microseconds to perform a static evaluation of a position, and this
>will have to be done for every single move that's generated, the (less
>than) 10 microseconds it takes to generate all moves in the first
>place is insignificant.
First a message to Gary. I would love to see your move generating code. You
can post or just send it to me at vmo...@mindspring.com . Secondly, my
friday night hangover is still in full effect so I hope I am thinking
clearly, so here goes.
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. Take
jellyfish as an example. It is possible to get an illegal move message if
you try to move too few pieces. Or to move pieces when you dance on the bar.
But jellyfish wont let you move to an opponents point. I guess it would be
possible to determine this from the legal list of plays but it seems like a
lot of code would be neccessary. I am assuming a bit different style from
the Jellyfish interface.... for example more like the games grid or fibs/w
interface where you drag and drop a 6-5 roll 11 spaces away if you can move
6 and/or 5 first. Again that seems like a lot of code(especially when
doubles enter the picture) to decipher the list of moves(final positions) to
determine if individual moves are legal single move or 2 or more(for
doubles) die combo legal moves. Maybe I am wrong but I am assuming the 50
lines doesn't include the code to do this. Therefore both approaches are
neccessary or at the very least useful. Perhaps the solution to each
individual move would be to have a function that takes as parameters 1)the
current board state (including previously moved checkers) 2) the piece in
question to be moved and 3)a list of all dice (e.g. 2-1, 3-1, 4-4-4-4, etc
depending on what the roll was) and wether each of those dice have been
played yet. The function would return a list of all legal spots that checker
can go and the dice used that would be used to do so. This would also allow
those functions to determine "take back" moves if there is info about wether
a checker has been moved already, and the dice to make available again due
to the "take back". The 2 functions could then be used in tandem to 1)move
individual checkers and then when "enter" is hit to make sure all moves have
been played. Moreover, the list of all legal individual check plays from a
given position and dice availability would solve the original problem of
taking the last checker off in 1 "move" instead of 2. The function would
include "off" as a legal point to play to and that it uses all available
dice. I beleive that this apporach would be more than speedy enough and
provide an "elegant" reuasble solution . For example, if you decided to
include Acey-Duecy or another variant in your software package just write 2
new routines to determine legal final positions and individual checker plays
given current board state.
V
Vince Mounts
backgammon playing program before but am giving my 2 cents anyway. After
thinking about it a bit I think maybe using the legal moves list to generate
the legal individual checker moves(i.e. "function2" could use the output of
"function1") may be the most efficient after all. It would not so
difficult as I assumed. This is assuming the legal play list returned arays
or lists of individual moves and not just final positions. Then wether each
individual move has been played could be tracked to determine available
plays for a specific checker. This would eliminate some redundancy of my
orginial idea in that problems such as when both checkers can't be played
can be handled in one spot(hmmm,,, didn't Gary already say this :). I
originally made the deciphering of the list of legal plays more complex in
my mind than it is. I still contend however that for a robust interface
there needs to be functionality beyond the list of legal moves that controls
how a person inteacts with the software on an individual checker basis. It
just turns out that the legal move list can play more of a role than I
originally suggested.
-----
Vince Mounts (a.k.a einniv)
E-Mail: vmo...@mindspring.com
Home Page URL: http://vmounts.home.mindspring.com
Vince Mounts wrote in message <6v5bas$pl0$2...@camel19.mindspring.com>...
Lou Poppler
: If the user tries to bear off with a one-die-move when he only have
: one blot left and he must make two moves, all you need to do is
: transform this move into one that moves the lowest die first and then
: the highest. Piece of cake! It will take 2-4 lines of code for me.
: The question is, should I implement it this way? Doesn't the rules say
: that you *have* to move both dice if possible? Anyone has an opinion
: about this?
I can't say for sure how FIBS enforces this, because I have
toggle-automove turned on there, so FIBS makes such moves for me.
But I can tell you how NOBS deals with this :
NOBS notices the legal move which uses both dice, and says
"Please move 2 pieces" and sets the can_move field in the rawboard to 2.
But if the client sends in a move command bearing off using only the
larger die, NOBS accepts this. The test is whether the destination
of the single move is "off" AND the player already has 14 pieces off.
(The move will already have been rejected if the larger die is
not large enough to accomplish this bearoff).
The code is one C statement, but occupies more than one line ;)
-- Spider
Cthulhu
[SNIP]
I think I'm interested in your code after all. I'm really interested
in how you solved the problem anyway. Did you make a mathematical
proof to see that your code really generated all moves, and that they
were all legal?
Could you please email it to me or post it here in r.g.b.?
Thanks,
Cthulhu
> I can't say for sure how FIBS enforces this, because I have
> toggle-automove turned on there, so FIBS makes such moves for me.
> But I can tell you how NOBS deals with this :
> NOBS notices the legal move which uses both dice, and says
> "Please move 2 pieces" and sets the can_move field in the rawboard to 2.
> But if the client sends in a move command bearing off using only the
> larger die, NOBS accepts this. The test is whether the destination
> of the single move is "off" AND the player already has 14 pieces off.
> (The move will already have been rejected if the larger die is
> not large enough to accomplish this bearoff).
> The code is one C statement, but occupies more than one line ;)
>
> -- Spider
>
I would still have to do a patch for it since FIBS doesn't work like
this. At least it didn't last time I checked. Aren't you supposed to
slavishly follow FIBS btw? Now, you go and "correct" this behaviour in
NOBS! ;)
Seriously, I'd rather see marvin follow the implementation of your
protocol in NOBS instead though. Your protocol works better in the
features you have implemented. Like the moreboards for example. And
the ability to send more than one command to the server. Not being
able to do this in FIBS, effectively hampers client writing.
Guess one can't have the best of both worlds... <sigh>
Murat Kalinyaprak
> Murat Kalinyaprak wrote:
>> At the very end, if you have one last piece left on
>> your 4 point for example, and you roll a 62, 51, etc.
>> you're obligated to play the smaller number first
>> before you can bear it off with the bigger number.
>I don't know how the rules are in real-life BG. Not that
>it really will matter there, since the result will be
>the same, but do you need to perform both moves at the
>end or are you sllowed to just move it out in one? What
>do the rules say about this?
As you said it, the key is that in the case we mentioned
above it doesn't matter. Nobody asked from me nor have I
asked from anybody else in real life to move the smaller
number first before bearing off the piece with the bigger
number (when the bigger number is by itself enough to
bear of the last piece). I think such a requirement/rule
would be nothing more than a silly annoyance...
>This thing might take a lot of code to fix since FIBS
>can't deal with it and I don't think the author(s) think(s)
>it's worth it, but I might be wrong. However, if BB(G?)T
>let you execute the move when you had moved only one piece,
>then I would call it a bug which should be fixed because of
>the way FIBS deals with this.
Client software and/or the server deals with other cases
of "incomplete moves" fine (such as having your last man
in the 1 point or rolling a double which gives you 1-3
more moves than what you need to bear off the last 1-3
pieces) during bear-off as well as at other stages of
the game. Handling this particular exception and making
the move more convenient would be an improvement, since
players can really get puzzled by it at first.
MK
Murat Kalinyaprak
>This is really a microsoft cock up. They have arranged
>that a space operates the default button.
Thanks for pointing this one out, John. I guess I
hadn't run into it previously in other software to
realize this. Sorry for thinking this was a bug in
the (BBT) client sotware.
MK
Gary Wong
> 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
> I think I'm interested in your code after all. I'm really interested
> in how you solved the problem anyway. Did you make a mathematical
> proof to see that your code really generated all moves, and that they
> were all legal?
No, I never really went in for formal proofs of correctness, that's too
much like hard work :-)
But with a bit of handwaving, you can satisfy yourself that all the rules
about playing both dice if possible; playing the larger if only one die
may be played, etc. all boil down to "you must play as many pips as
possible". You can generate a superset of all legal moves with a simple
recursive function that attempts to play the next die roll from each point
the player has a chequer on in turn (or just the bar, if the player is on
the bar). Once you have played as many dice as possible, add up the pips
you played; you will find one of the following cases:
- the pips moved in this move are less than for some other existing move;
this move is therefore illegal, so ignore it
- an equal number of pips to the maximum found so far: we think this move
is legal, add it to the list
- more pips than any previous move: we now know all prior moves are illegal;
delete them all and add the current move to a new (empty) list.
If you are only checking for legality and don't want the moves for anything
else then you obviously don't have to store them in an explicit list (just
keep track of the current maximum, and check to see if the move you're
given ever occurs).
If you are keeping track of legal moves, be aware that the list can get
VERY big -- a trivial upper bound is C(18,4) which is 3,060 legal moves.
(Think about the case where a player has 15 blots spread out from the bar
to his ace point and rolls 11; you can play a single chequer more than once
so the bound is C(18,4) not C(15,4). Some of these moves will be duplicated
so the true limit will be somewhat less.) I've come across positions where
there have been well over 1,000 legal moves in real games; needless to say,
the bots get VERY slow at pushing 1,000 positions through their nets,
especially if many of those positions get evaluated again with deeper
searches!
Cheers,
Gary.
Chuck Bower
Gary Wong <ga...@cs.arizona.edu> wrote:
>"Cthulhu" <-@earthdome.com> writes:
>> I think I'm interested in your code after all. I'm really interested
>> in how you solved the problem anyway. Did you make a mathematical
>> proof to see that your code really generated all moves, and that they
>> were all legal?
>
>No, I never really went in for formal proofs of correctness, that's too
>much like hard work :-)
>
>But with a bit of handwaving, you can satisfy yourself that all the rules
>about playing both dice if possible; playing the larger if only one die
>may be played, etc. all boil down to "you must play as many pips as
>possible".
Whoa, Gary! This is not true. Look at:
oxx
oxxx--
123456
X to play 41. 4/off, 3/2 uses 5 pips. 4/3, 3/off uses 4, but is legal
AND "best". Hope you will teach your NN this!
Chuck
bo...@bigbang.astro.indiana.edu
c_ray on FIBS
Gary Wong
Whoops! I guess what I wrote above is quite ambiguous (replace "a bit
of handwaving" with "a lot of handwaving" :-)
To be more precise I should have specified _dice_ pips rather than
_chequer_ pips (ie. in the quote above, "pips" means "the sum of the
dice you actually play" rather than "the number your pip count
decreases by").
According to this definition, both of the plays you mention are
classified as playing 4 + 1 = 5 pips; the move generator would
evaluate them as distinct legal plays and allow either.
Chris Sells
> ...
> anRollRaw[ 0 ] = anRoll[ 1 ];
> anRollRaw[ 1 ] = anRoll[ 0 ];
I think it should be:
...
...
Nasti Chestikov
Chris Sells
> Seeing as you are reviving a thread that is 22 years old, I guess it's been fixed by now........
peps...@gmail.com
MK
paying attention to details and ppropose a correction (whether
it's really a bug or not to be decided)... Truely amazing!!!
It made me feel good additionally because I was the one who had
initiated the discussion. And look how everyone were polite (including
me;) and took time to discuss things seriously and in lengthy details.
On the eve of a new year, I just can't help wishing that "them good
old days" may return... Welcome 2021!
MK
Chris Sells
I think it's a bug because it uses a familiar pattern for someone that wants to do a swap but does it incorrectly (I've read code just like it a dozen times). I also think it's a bug because it looks like code derived from this code lives in eval.c from the GNU Backgammon project, except that the similar line in question [2] uses a function called "swap" instead of doing the normal three-line swap dance (which the original code seems to get wrong). Finally, I think it's a bug because it doesn't make any sense to check for another set of legal moves by changing the roll from two different values to two of the same values, depending on the order that the values were passed into the function via the array. On the other hand, it does make sense to swap the values and get the other value of the legal moves.
That said, I do hope 2021 is a great deal better than 2020 was.
[1] https://github.com/csells/fibscli
[2] https://cvs.savannah.gnu.org/viewvc/gnubg/gnubg/eval.c?view=markup#l2882