undo & atomic actions in magic

[silly freak]

hi all!
i'm working on my own rules enforcing MTG, and find that an undo system is very important. not only to allow the user to undo choices made by mistake, but also for AI and in the situation of impossible actions (say, not being able to pay for a spell; whatever)

what I wanted is to have actions that do the modifications - one action per changed property - and every one is able to undo the change. there are two additional main requirements:
first, it has to feel natural to the programmer - the effort to respect undo in individual cards should be minimal
second, there's the requirement to navigate through the actions

my idea was a tree structure, so actions can be divided into moves, phases,... and the really small actions (like incrementing the game's timestamp) should be an atomic part of the full action. on the other hand, navigating in a tree is not that easy: the most important is to move forward (to the chronologically next action) and backward, regardless of the tree structure. additionally, storing the current action (the last one that was executed/not undone) is easier in a simple list...

I hope you other developers can use my thoughts, and any help and ideas would be very appreciated

[telengard]

The way I did undo in my engine (both for a human player and for the AI when doing minmax) was to have every action they can take have an unique id # (this is a number that is incremented each time an action derived instance is allocated).

Any changes to game state after the action is taken are applied (in their respective places like ability/effects classes etc, the classes are change_state_x, where x can be bool, int, string, hook_func, lists, all kinds of stuff) and put on a list of changes. When another action is taken a new "change set" is made.

When undo'ing an action I can just specify an id to undo up to and all the changes get backed out for that action. It has worked very well so far. I used to support auto-executing by the AI if only a single action was present so there were cases where multiple actions would be done by a back-out. I now have the AI execute even single actions so it works w/ the phase and tree depth correctly (less of a 'horizon' issue this way).

~telengard

[frwololo]

telengard, can you give more details (maybe actual code) for your data structures to handle that?
What does a set of changes look like ? How do you store the various "actions" and their id ? How are they related to each set of change ? I'm guessing you just have a queue of "ChangeSet" objects but I would like to know if you ran into anything tricky ?
Do your "changes" all inherit from some kind of "Undoable" class ?
How far do you go in terms of "what change is atomic"?

[telengard]

telengard, can you give more details (maybe actual code) for your data structures to handle that?
What does a set of changes look like ? How do you store the various "actions" and their id ? How are they related to each set of change ? I'm guessing you just have a queue of "ChangeSet" objects but I would like to know if you ran into anything tricky ?
Do your "changes" all inherit from some kind of "Undoable" class ?
How far do you go in terms of "what change is atomic"?

Oh sure, no problem... (for the sake of clarity I've pruned out ASSERTs and my debugging stuff which is everywhere.)

So any change that I need to make to the game state (my game state class encapsulates everything about the current game, the pieces in play, where they are, continuous effects, the stack, hooks, spawn pool (think mana), everything) has to go through the undo engine. I'll start with something simple like changing an integer value. Here is the class for that:

Declaration...

Code: Select all


#ifndef __UNDO_STATE_CHANGE_INT_H__
#define __UNDO_STATE_CHANGE_INT_H__

///////////////////////////////////

#include "undo/game_state_change.h"

///////////////////////////////////

class state_change_int : public state_change
{

public:

   state_change_int() { type = STATE_CHANGE_TYPE_INT; }
   void init( int* _int_to_change, int _new_value );

    void do_change  ( game_state* _game_state );
    void undo_change( game_state* _game_state );

private:

    int* changed;
    int  saved_val;
    int  new_val;
};

#endif


and implementation...

Code: Select all

#include "state_change_int.h"

///////////////////////////////////

void
state_change_int::init( int* _int_to_change, int _new_value )
{
    changed = _int_to_change;
    new_val = _new_value;
}

///////////////////////////////////

void
state_change_int::do_change( game_state* _game_state )
{
    saved_val = *changed;
    *changed  = new_val;
}

///////////////////////////////////

void
state_change_int::undo_change( game_state* _game_state )
{
    *changed  = saved_val;
}


The type field of the class is used for indexing into a string array and also used for grabbing new ones from the memory pool (which could be another whole discussion).

As you can see this class inherits from class state_change, which just defines 2 necessary methods (which now that I look at it, should probably be pure virtual):

Code: Select all

#ifndef __UNDO_STATE_CHANGE_H__
#define __UNDO_STATE_CHANGE_H__

#include "undo/defs.h"

class game_state;

///////////////////////////////////

class state_change
{
public:

    state_change() { type = STATE_CHANGE_TYPE_INVALID; }
    virtual ~state_change() {};

    virtual void do_change  ( game_state* _game_state ) {};
    virtual void undo_change( game_state* _game_state ) {};

   int type;

#ifdef __DEBUG__
    virtual string to_str( void ) { return state_change_strs[type]; }
#endif
};

#endif


Another code module has an stl vector (this will eventually be moved to the game state so I can re-try doing a multithreaded engine... this stuff used to be in there and I moved it out)

Code: Select all

static vector<state_change*> undo_queue;


In addition there are these variables:

Code: Select all

static stack<struct undo_entry*> undo_stack;
static int                       g_undo_id = 0;

void back_out_changes( game_state* _game_state, struct undo_entry* _u );


In the routine that handles all the details of executing an action, the last thing it does is this:

Code: Select all

return handle_undo_stack( this, _action );


That routine handles all of the changes that have happened and returns a 'cookie' used by the minmax code to roll back everything:

Code: Select all

///////////////////////////////////

int
handle_undo_stack( game_state* _game_state, action* _action )
{
    struct undo_entry* u    = get_undo_entry();
    u->undo_cookie          = ++g_undo_id;

    undo_queue.swap( u->changes );
    undo_stack.push( u );

    return u->undo_cookie;
}


An undo_entry is just a very small struct holding all the changes and the cookie:

Code: Select all

///////////////////////////////////

struct undo_entry
{
    int undo_cookie;
    vector<state_change*> changes;
};


In the ai player code there is a section that executes an action and then evaluates the game state based on taking that action, and then backs everything out (all necessary for minimax unless you are copying the entire game_state which I found to be terribly slow and error prone given the sheer quantity of stuff that needs to be kept track of)

Code: Select all

        int undo_cookie = _game_state->execute_action( a );
        int val         = alphabeta_value( _game_state, _ai, 1, start_turn, start_phase, _alpha, _beta );

        pop_state( _game_state, undo_cookie );


The pop_state() routine does all of the backing out:

Code: Select all

void
pop_state( game_state* _game_state, int _until_id )
{
    struct undo_entry* u = NULL;

    if ( _until_id != INVALID_UNDO_COOKIE )
    {
        /* go back all actions until specified ID */

        bool done = false;

        while ( !done )
        {
            u = undo_stack.top();
            undo_stack.pop();

            if ( u->undo_cookie == _until_id )
                done = true;

            back_out_changes( _game_state, u );

            put_undo_entry( u );
        }
    }

    else
    {
        /* go back one action's worth of state changes */

        if ( !undo_stack.empty() )
        {
            u = undo_stack.top();
            undo_stack.pop();

            back_out_changes( _game_state, u );

            put_undo_entry( u );
        }
    }
}


The [get|put]_undo_entry are calls into the memory pool.
back_out_changes just calls undo_change on all the state_changes.

Only other thing left to show is probably how an ability/effect etc would use this. This is the Shackle ability which uses change_state_int (and others) in a few places to make stateful changes:

Code: Select all

#include "shackle.h"

#include "events/piece_disrupted.h"
#include "pieces/piece.h"
#include "players/player.h"
#include "utils/mem_pool.h"
#include "utils/misc.h"

///////////////////////////////////

#define STATE_APPLY_SUSTAINED_EFFECT  ( 1 )
#define STATE_CHOOSE_MOVE_PIECES      ( 2 )
#define STATE_PLAYER_DONE             ( 3 )

///////////////////////////////////

shackle::shackle( piece* _piece, int _num_targets )
   : triggered_ability( ABILITY_TYPE_SHACKLE, _piece, EVENT_ID_PIECE_DISRUPTED_MOVED )
{
    /* TODO: See design doc for some weird handling of this ability out of combat */

    num_targets      = _num_targets;                               /* NOTE: This is "up to" */
    target_zone      = NULL;
    state            = STATE_APPLY_SUSTAINED_EFFECT;
    is_group_ability = true;
    num_moved        = 0;
    desc             = string( "Shackle " ) + ltoa( num_targets );
    desc_long        = desc + " - Whenever this creature is disrupted and removed from its cell, choose up to " + ltoa( num_targets ) + " target enemies from that cell. Put those targets in the same cell as this creature.  There can be no combat in this cell this phase.";
    continue_context = desc + ": Finished moving targets";
}

///////////////////////////////////

bool
shackle::does_ability_trigger( game_state* _game_state, void* _info, bool& _resolve_now )
{
    event_info_piece_disrupted* e = ( event_info_piece_disrupted* )_info;

    /* TODO: Is disrupted and moved the same as disrupted and removed from its cell? */

    if ( e->disrupted_piece == owning_piece )        /* we were disrupted & moved */
        return true;

    return false;
}

///////////////////////////////////

void
shackle::on_triggered( game_state* _game_state, void* _info )
{
    event_info_piece_disrupted* e = ( event_info_piece_disrupted* )_info;

    change_state_zone( _game_state, &target_zone, e->disrupted_from_zone );
    change_state_int( _game_state, &num_moved, 0 );
    change_state_int( _game_state, &state, STATE_APPLY_SUSTAINED_EFFECT );
}

///////////////////////////////////

bool
shackle::resolve_ability( game_state* _game_state )
{
    if ( state == STATE_APPLY_SUSTAINED_EFFECT )
    {
        MEMPOOL_GET_ACTION_PTR( e, effect_cant_strike_in_cell );

        e->init( controller, ( ability* )this, _game_state, owning_piece->current_zone, owning_piece->controller->opponent );
        e->enable( _game_state );

        _game_state->add_sustained_effect( EVENT_ID_PHASE_EXIT, e );
        change_state_int( _game_state, &state, STATE_CHOOSE_MOVE_PIECES );
    }

    if ( state == STATE_CHOOSE_MOVE_PIECES )
    {
        if ( num_moved < num_targets )
        {
            foreach( piece* p, target_zone->pieces )
            {
                if (    _game_state->is_enemy( owning_piece->controller, p )
                     && _game_state->can_piece_move( _game_state, p->controller, p )
                     && _game_state->can_piece_be_target_of_ability( _game_state, p, this )
                   )
                {
                    if ( _game_state->can_zone_be_entered_into_by_piece( _game_state, owning_piece->current_zone, p, p->controller, false, false ) )
                    {
                        MEMPOOL_GET_ACTION_PTR( effect_ptr, effect_move_piece );
                        effect_ptr->init( controller, ( ability* )this, p, owning_piece->current_zone );
                        effect_ptr->set_notify( this );
                        effects.push_back( effect_ptr );
                    }
                }
            }

            if ( !effects.empty() )
            {
                MEMPOOL_GET_ACTION_PTR( ap, action_continue_on );
                ap->init( controller, continue_context );
                ap->set_notify( this );
                effects.push_back( ap );

                return true;
            }
        }
    }

    return false;
}

///////////////////////////////////

void
shackle::notify( game_state* _game_state, action* _action )
{
    if ( _action->type == ACTION_TYPE_CONTINUE_ON )
        change_state_int( _game_state, &state, STATE_PLAYER_DONE );

    else
        change_state_int( _game_state, &num_moved, num_moved + 1 );
}


change_state_x are just wrapper functions that handle the allocation of the corresponding state_change object and initializing it (and a few other things).

As far as atomicity goes. If something has to change the game_state it goes through the engine. Some things are queried for all the time so do not need to be tucked away, for instance the current actions available or effects generated by an ability. A given game state will always produce the same available actions/effects for a player to deal with.

A lot of this stuff was more convoluted in the past because I supported 'replaying' games. Due to some optimizations for the AI (which I didn't want to conditionalize for performance reasons) I can no longer support replays so it was gutted out.

Also, the terms undo id and cookie are interchangable (and I should probably be more consistent with that). In my previous post I mentioned unique action ids, I was confusing that w/ the undo cookie. The unique action id was part of the whole replay thing which is now gone.

If this isn't clear I can elaborate more.

~telengard

[frwololo]

Thanks a lot