Version (1.0.39) released. Undo support, DnD move, faster AI

[telengard]

A lot of big changes in this release!

I re-enabled Undo support. In the GUI, Ctrl-U undoes your last action and you can go right back all the way to the beginning of the game.

I also enabled dragging of pieces for spawning, moving, shifting, and disruption placement.

Through a good chunk of time staring at Shark performance captures I've managed to speed up the minmax AI by ~40% w/ the default warbands. Hopefully that gain is mostly across the board as it was core engine code.

Other noteworthy changes:

- Spacebar can be used for passing on may abilities, going to the next phase, done choosing targets etc.
- Fortunate was improved a lot such that it takes minutes rather than hours when the AI is contemplating how to deal with high numbers of dice rolled for an attack.
- As usual lots of bug fixes and improvements.
- A new custom using a variant of Venom (Rot).
- A pretty bad bug w/ Defender was also fixed.

All the changes made can be viewed here:
http://home.comcast.net/~bsturk/dreamblade/CHANGELOG

NOTE: This particular release shows up still as 1.0.38 due to me forgetting to update the version header during this development release. You can tell you have 1.0.39 by seeing if Undo is mentioned in the welcome dialog.

Have fun and Happy Holidays!
~telengard

[Huggybaby]

WOW.

Undo to the beginning of the game.
Dragging.
40% AI speedup.

You added a major option, a major interface enhancement, and basically made the game smarter in one release. Good work telengard!

1) How do you implement undo? How do you record the game state?

2) What programming language does Dreamblade use again? Is it Java? Because I googled Shark and it looks to be an Apple app.

3) Can you tell us more about using Shark? That sounds like interesting stuff. Code optimization is interesting because it can make such a big difference, and the perception is that code optimization is a lost art since the assembly language days.

[telengard]

WOW.

Undo to the beginning of the game.
Dragging.
40% AI speedup.

You added a major option, a major interface enhancement, and basically made the game smarter in one release. Good work telengard!

1) How do you implement undo? How do you record the game state?

2) What programming language does Dreamblade use again? Is it Java? Because I googled Shark and it looks to be an Apple app.

3) Can you tell us more about using Shark? That sounds like interesting stuff. Code optimization is interesting because it can make such a big difference, and the perception is that code optimization is a lost art since the assembly language days.

Hiya Huggybaby,

Thanks for the complements!

1) The way I handle undo is just to leverage the existing framework for committing (and undo'ing) changes to the game state. Any change goes through the state_change engine. So if I change an int, pointer, list, anything, it goes through that. Here's an example. Every time a piece comes into play it bumps its instance number.

Code: Select all

    change_state_int( this, &_piece->instance_id, ++_piece->instance_id );


which does this:

Code: Select all

void
change_state_int( game_state* _game_state, int* _val_to_change, int _new_val )
{
    MEMPOOL_GET_STATE_CHANGE_PTR( _game_state, change, state_change_int );
    change->init( _val_to_change, _new_val );

    change_state( _game_state, change );
}


change_state() just pushes the change onto the undo_queue and then invokes the do_change() of the particular change. All of these state_changes also tuck away what they changed so they can be undone.

Allowing Undo of human moves is just some extra bookkeeping and UI support (and a few other details).

2) It is in C++ for raw speed. I originally did the program in python and it was way too slow. I tinkered with D, Clojure, lisp, and Java too and they were slower also.

3) Shark is a very nice profiling program on OS X. It is similar to gprof but can give you the hotspots within your functions line by line. This gets you part of the way there. The rest is up to me to figure out *why* it is slow. Most of the slowdowns in my app are memory allocations due to temporaries or copies of STL collections (well also the evaluation function which is expensive). I have a dedicated memory pool to avoid allocations/deallocations which kill performance when you do them hundreds of thousands of times a second (when the AI is thinking).

I've spent a lot of time over the life of the project optimizing it. 2 AIs can play an entire game against each other at a depth of 4 in usually around 5 seconds. The issue is, once you start getting up to 7 and 8, the branching factor causes the time it takes to go through the entire tree to increase a lot. I still believe there is even more I can do. Adding support for threads was another big boost. Running the program on my Mac at work which has a lot of cores, things go a lot faster.

~telengard