[computer-go] Monte Carlo combined with minimax search

[Chrilly]

I have ported a C chess programm which was initially written for a Hitachi 
microcontroller to Java. The Java version was on a PC only 15% slower. One 
can write C-programs in Java with the rules below. The 15% difference are 
due to the better optimization of a C-Compiler. The Java to Virtual-Machine 
compiler produces very poor code. Obviously the Just-In-Time compiler in the 
runtime does only some loophole optimizations which can not compete with the 
optimizations of a C-Compiler. When switching off the JIT-Compiler the Java 
code runs 15 times slower.

The rules to produce very fast Java codes are:

a) Avoid new, any creation of new objects.
b) Function/method codes are in Java expensive, because the correct method 
is determined dynamically. I C its a simply "call" instruction. The standard 
Java calling convention is by orders more expensive than in C. To circumvent 
this problem one has to declare the class as final. In this case the 
compiler can generate also a "call" instruction like in C. In my program 
there was only one big final class which contained all the functions/methods 
of the original code. I removed effectivly the object-system and wrote a 
flat-collection of functions like in plain C.
c) The Java Virtual Engine can only process 32-Bit numbers. All other data 
are second class citizens which are converted to 32-Bit. Using e.g. a Byte 
array makes things worse, because there is an additional Convert to 32-Bit 
instruction involved. In case of the chess programm, everything was packed 
as much as possible, because the Hitachi had only 4KByte of RAM. I had to 
blow up things to ints or used the trick described in d).
d) Do NOT convert C-structs to Java classes. The C-original used  a lot of 4 
Byte structures with 4  1-Byte Elements. E.g a move is encode as struct { 
Uint8 from, Uint8 to, Uint8 flags, Sint8 val; }
I converted this to a 32-Bit integer and exctracted the fields with 
bit-fiddling. This is much faster and compact than converting the struct to 
a class. But it produces ugly and error-prone code.
One could also use 4 int arrays. But the conversion was closer to the 
original. Additionally is the 32-Bit fiddling method more cache-friendly.

I did this as a programming excercise, but I see no point of writing bad C 
Code in Java.

Chrilly