jamesa%betelgeuse@Sun.COM (James D. Allen) (05/24/88)
The `goto' flames seem to be dying out; I'd like to add some
gasoline. While others have been defending relatively `structured' goto's
(eg, "break 2", common code coalescing) my favorite goto is really horrendous:
a jump from one inner loop to a different inner loop. I am sincerely curious
if there is a "better way."
Following is edited but fairly faithful pseudocode for a contract
bridge endgame analysis program. Since performance is an issue I mention that
the pseudostatements each compile to very terse machine code.
initialize;
for (tricknum = 0; outcome still undecided; tricknum++) {
for (player = winner of prev trick; other players; player++) {
determine legal plays;
remove redundancies; /* A == K , etc. */
select most likely play;
BACKTRACK:
play the card;
push set of legal plays;
if (player == winner of previous trick)
restrict others to suit_led;
}
determine winner of trick;
}
while (--tricknum >= 0) {
for (player = last_to_play; other players; player--) {
pop set of legal plays;
undo played_card and delete from legal plays;
if (player is on losing side && other play available)
goto BACKTRACK;
}
}
print solution;
Here are some alternate coding methods with my objections.
1) Do a recursive function call for each played card. Clumsy (you either
have to pass a lot of arguments or maintain the data as globals).
Execution time increases significantly.
2) Do a recursive function call for each trick. Reasonable, but doesn't
completely sidestep the problem since backtracking occurs *within*
a trick.
3) Rewrite in Prolog. Plausible but pedantic.
4) Stuff the forward loop into the middle of the backtrack loop, or
vice versa (left as an exercise). Requires clumsy boolean flags
(my code uses none). Less readable because intuitively the forward
and backtrack loops are separate.
I don't claim that this is a general solution for backtracking.
Simpler problems can be handled nicely with nested `while's; harder problems
will require a more general method. But for this program, depicting the
backtracking with a single powerful "goto" expresses the paradigm more
clearly (and certainly more efficiently) than the alternatives.bill@proxftl.UUCP (T. William Wells) (06/12/88)
In article <54281@sun.uucp>, jamesa%betelgeuse@Sun.COM (James D. Allen) writes: > Following is edited but fairly faithful pseudocode for a contract > bridge endgame analysis program. Since performance is an issue I mention that > the pseudostatements each compile to very terse machine code. > > initialize; > for (tricknum = 0; outcome still undecided; tricknum++) { > for (player = winner of prev trick; other players; player++) { > determine legal plays; > remove redundancies; /* A == K , etc. */ > select most likely play; > BACKTRACK: > play the card; > push set of legal plays; > if (player == winner of previous trick) > restrict others to suit_led; > } > determine winner of trick; > } > while (--tricknum >= 0) { > for (player = last_to_play; other players; player--) { > pop set of legal plays; > undo played_card and delete from legal plays; > if (player is on losing side && other play available) > goto BACKTRACK; > } > } > print solution; One alternate is to first recast this as a state machine. Here is how: The first thing to do is to put IN all the gotos. (Well, almost all; some are obviously irrelevant to determining the global control structure, do not bother with those.) Eliminate labels immediately before gotos (by changing the gotos to that label). Then, add a goto just before each label that is not preceded by a goto. Next, recast this as a state machine and clean some of it up. Among other things, get rid of each state with only one reference to it. Then, after it is a state machine, one can then determine the flow of control and rewrite the code with non-goto control structures. The result looks something like this: (assuming I did everything right; if not, do not bother to grouse, just do it yourself and tell us how it really should be done.) initialize; tricknum = 0; player = winner of prev trick; while (1) { /* Moving forward ... this player has not yet had moves generated for him. Generate those moves. */ determine legal plays; remove redundancies; /* A == K , etc. */ while (1) { /* Note that in the original code, the BACKTRACK label should have been one statement eariler; were this code to duplicate the function of the other code, the `select' would have been outside this loop and no selection would have occured after backtracking. */ /* We get here either after moving forward or after backtracking. In either case, we must select a play to make. */ select most likely play; play the card; push set of legal plays; if (player == winner of previous trick) { restrict others to suit_led; } /* If all players have not had their turn, advance to the next player. */ if (there are more players for this trick) { ++player; break; } /* The trick is done. Should there be more tricks to play, advance to the next trick, making the winner of this trick the current player. */ determine winner of trick; if (outcome still undecided) { ++tricknum; player = winner of prev trick; break; } /* Time to back up; ascend the game tree till someone has a move to make. Also, do not stop ascending if the player who could move would win. After all, why explore OTHER ways of winning? */ player = last_to_play; while (1) { pop set of legal plays; undo played_card and delete from legal plays; if (player is on losing side && other play available) { break; } if (this is the first player for the trick) { if (--tricknum < 0) { print solution; return; } player = last_to_play; } else { --player; } } } } > 4) Stuff the forward loop into the middle of the backtrack loop, or > vice versa (left as an exercise). Requires clumsy boolean flags > (my code uses none). Less readable because intuitively the forward > and backtrack loops are separate. Well, as you can see, my code effectively does this. However, you will notice that there are no additional variables. Also, this code, while it appears to be much larger, actually has only one more statement than the original: player = last_to_play; And this additional statement may be optimized out by some of the better compilers. While I am on the subject of optimizers, note also that the goto-less version is likely to be better optimized than the original, as many optimizers choke when confronted with a goto.