Don't get too caught up on the State Pattern. This has a specific usage which I don't think necessarily applies in your game, at least not when you are manipulating the state of play.

Take, for example, a drawing application. In this case, the button pressed in the toolbar affects the way the drawing panel reacts to certain stimuli -- in this case, you don't want the application to know what it is going to do, you just want it to pass the stimulus to the State object and let it figure out what to do.

So, the rectangle drawing button is down, the application holds a RectangleDrawingState from which it can request a mouse-over pointer type or a mouse-down action or whatever. If you press the elipse-drawing button then that control switches out the RectangleDrawingState for an ElipseDrawingState and the application continues to ask for a mouse-over pointer type and a mouse-down action and gets completely different responses.

This is the kind of situation that makes for a good use-case for the State Pattern.

Now you may want this in your turn-based strategy game, to handle whether the attack button is pressed or the gather resources button is pressed. But you should handle the state of the game differently.

The state of the game should be handled as a single mutable object, which is manipulated at the end of each action. This object needs to be serializable in some form.

What you should do then is get a Command object by whatever means necessary and act on the mutable state-of-play object (it might be that your immutable State object, which depends on the action selected at any given time, returns a command which can act on the state-of-play object, for example).

It sounds like you already know that Solution 2 is a bad plan. But solution 1 is giving you trouble as well.

I gather your classes end up looking like this:

class MoveCommand
{
   MoveCommand(Field from, Field to)
   {
      this->from = from;
      this->to = to;
   }

   State apply(State state)
   {
       MutableState mutable_state = new MutableState(state);
       Unit unit = mutable_state.GetUnit(from);
       mutable_state.RemoveUnit(from);
       mutable_state.PutUnit(to, unit);
       return mutable_state.AsState();
   }
}

Firstly, you've designed your immutable objects wrong. The idea is not to switch back and forth between immutable and mutable objects. Rather, if you want to use immutable objects, then methods on your immutable object should return new objects. So your code should look more like this.

State apply(State state)
{
    Unit unit = state.GetUnit(from);
    state = state.RemoveUnit(unit);
    state = state.PutUnit(to, unit);
    return state;
}

But immutability is great for small things like numbers, strings, etc. For handling the entire state of your game, it tends to get cumbersome. So really, I figure you should drop the immutable aspect and do:

void apply(State state)
{
    Unit unit = state.GetUnit(from);
    state.RemoveUnit(unit);
    state.PutUnit(to, unit);
}

However, an argument can be made that this makes the MoveCommand have logic that belong somewhere else. Perhaps the code should look like:

void apply(State state)
{
    state.move(from, to);
}

But this makes the whole MoveCommand class look a little pointless because it doesn't seem to really do anything. But I say: don't worry about it. Some commands will be trivially implemented using the game state objects. And that's a good thing.

I think you're fine using your first method. You will probably want to utilize a StateBuilder to allow the command to build out the new state.

Thus you've divided your state, your commands (allowing you to roll back to prior states, I assume), and your means of building new states.

That said, I'm not sure what the immutable state is giving you in this case, beyond something with a handle that can be tracked or rolled back to. If that is not your purpose, I don't know that you need it.

Perhaps you should separate Command (a request) from its affects (a response). You have a set of concrete Command classes and the State objects will behave differently for each, so you should consider using overloaded methods for each Command. This allows you to specifically handle each Command as only the State should know how to respond. You Command objects have no inherent behaviour, only the data needed for the request.

void State.Handle(MoveCommand)

void State.Handle(PassCommand)

void State.Handle(BidCommand)

The Handle methods are responsible for validating the Command against current state, and then raising appropriate domain events to affect the state of the model. The domain events contains the new data to be applied interested parties (e.g. 'MovedEvent' contains new position).

The Apply methods accept concrete domain event objects and change the state accordingly:

void State.Apply(MovedEvent)

void State.Apply(PassedEvent)

void State.Apply(BiddedEvent)

Domain events could also be routed to other affected objects.