void
    find_optimal_play(){
        ... a few local variables ...

        ... initialize ...

        FOREVER {

            FOREVER {
                play one more card from alternatives
                set alternatives for next play
                if(  at end of trick  ){
                    advance state to next trick
                    if(  one side "won"  )  break;
                }
            }

            FOREVER {
                if(  at start of trick  ){
                    if(  at first trick  )  return;
                    regress state to previous trick
                }
                regress state to previous play
                undo effects of card played
                if(  this side should try other plays  )  break;
            }
        }
    }

I coded up something along these lines.  The control flow is just what
is shown here:  three infinite loops, two break's, one return.  The
state of the computation was in a data structure much like the one you
used - a stack of "tricks" with information about alternatives and
cards played.  Only a few local variables, and I made essentially no
effort to micro-optimize;  for example, the suit led is recalculated
each time through the "advance the state" loop:

    suit_led = SUIT( S->card_played[ S->on_lead ] );

Except for the different method of doing control flow, the two
programs use basically the same algorithm.  The structured code ran
about 25% faster than your code with goto's.