Thanks for your detailed answer. I just came home from an exhausting day at work, and it seems that there are a whole lot more to come; so I'll have to look into it as soon as I get some "room to breathe".

By a quick look, I noticed one thing that's unclear:

You store a position in the TT by storing the bound type and alpha:

TT.store_hash(P.get_hash(), bound_type, alpha);

But later, you retrieve what seems to be the lower bound and upper bound:

TT.retrieve(P.get_hash(), &hash_lower_bound, &hash_upper_bound);

Where has the bound type gone? And where is the lower bound coming from?

This is roughly what I had in mind:

void TranspositionTable::store_hash(HashKey hash_key, BoundType bound_type, int score) {
  TT_Entry &entry = find_entry(hash_key); // If not found, this sets up an entry with lower_bound=-Infinity, upper_bound=+Infinity
 
  switch (bound_type) {
    case Exact:
      entry.lower_bound = entry.upper_bound = score;
      break;
    case LowerBound:
      entry.lower_bound = score;
       break;
    case UpperBound:
      entry.upper_bound = score;
  }
}

Okay, I made some progress. I designed the TT to store nodes from all depths (not just the beginning of a trick), resulting in a speed improvement between the factor 1.5 and 2.5, increasing JVM memory usage to about 780 MB in average.

The example you provided I believe I already have implemented basically.

I am currently giving move ordering a try, but surprisingly, it slows down the execution dramatically. I took the following suggestion from the reference in my first post:

I have to put this into perspective. First of all, I improved the move ordering function, which speeds it up a couple percent. Second of all, I noticed that move ordering will be more efficient if the analyzed game is "complex" (I believe extreme distributions of suits/trumps could play a big role). Generally, when alpha beta without move ordering takes about 6-8 seconds of CPU time, move ordering will "break even"; that is, move ordering is faster when the game takes longer to be analyzed.

To your question: The number of visited nodes seems to be reduced by the factor of 1.5, the number of TT lookups is reduced to almost 50%. Interestingly enough, the more optimization techniques I implement, the faster the CPU runtime (the execution time of the main thread) gets, but the bigger the ratio of real time / CPU time will be. I believe this is due to the JVM having other threads running (e.g. garbabe collection); especially since I can see the CPU load (quad-core) peak to about 50%, which means that secondary threads fully utilize their own core.

Anyway, another thing I've tried is to store the move ordering in the transposition table (not just the best move itself). Unfortunately, that will not just blow up RAM consumption, but also leads to inferior execution speeds, although memory wasn't the bottleneck. Weird! Maybe it's JVM's fault ;)

Currently, I'm trying to find a good way to reproduce the "optimal strategy". In other words, I want to keep track of the path from the root to the leaf that represents the optimal course of play. Since every succesful TT lookup will lead to a "shortcut", the algorithm will eventually just cut off the optimal path and I'm left with a lonely position somewhere in the middle of the tree. To my understanding, every move along the optimal path will be stored in the TT as a valid node. Consequentially, I store the best move for VALID nodes. When alphaBetaTT has finished, I go as far down as possible (that is, as long as I could keep track of the optimal moves, until a TT cutoff occured). From there, I just look up all the optimal moves in the TT until I reach a leaf.

I hope I made myself clear enough! If yes, does that plan make sense to you?

I'll post my results asap, just wanted to let you know what I've achieved in the meantime and what I've been thinking about ;)

My advice, switch to C++.

I spent the last days reading in C++, and I think I know enough to port my project. But there's one thing I just can't get to work. In order to import Skat games, I want to parse HTML documents of previously played games, like in the link from my first post. And I thought this would be a good starting point to learn the language, since I'm very fond of HTML parsing. I know this question doesn't belong here, but I searched the whole web, and still didn't succeed.

All I want to do is import the library htmlcxx and use it. But how do I do that? I'm using Visual Studio Express 2013 on Windows. I've tried adding the library directory to the include directories, importing it into my project etc. but I'm still getting weird Linker errors. It can't be that hard, can it? Maybe you could give me a hint ;[