Good performance when predicting future game states

This question is about my answer to this king-of-the-hill challenge on Code Golf. In short, the purpose of the challenge is to code a slime that, trough various possible moves gains control over an 8x8 play area against 3 other slimes. The slimes get their turn one after another.

My idea was to go trough all possible moves for the next few rounds, put a score on each possible outcome and then estimating which possible move would be the best. I decided I should at least look as far as after my own next move, but as there are somewhere around 100 possible moves each turn, this quickly gets too slow. I now randomly skip a certain percentage of possible moves, based on a guess of how many moves there are:

double skip = (us*2.5/(us*2.5 + 1))/4 + 0.735;

Where us is an integer that indicates how many of the currently active player are on the board. On the first turn, I don't skip any moves and on the second I multiply the skip ratio by itself, since the base of the tree is more important to me. As you can see, I am skipping a lot of branches.

TL; DR: I'm doing some tree searches on the board states of a game, I need to get the performance up.

How can I improve my code to run faster so I don't need to skip so many branches? Seeing as I'm not a very experienced programmer at all and Java is very new to me, I'm sure the performance can be orders of magnitude better.

A few things I can think of that could use improving:

• I have a fixed size array to store boardstates that have already been over (since some moves have the same outcome) the way I handle this might be slowing me down.

• Am I returning values that don't need returning since they are passed as a reference?

• Should I be storing the boardstates more efficiently?

• My choice of language might not be the best.

• Though probably not directly related to performance, the main loop in my getBestMove method is a mess.

Any other feedback on my code is of course also welcomed, but performance goes

Well, this is quite a bit of code so just some generic remarks and advise for now:

-
Your code is a prime example of what I would call spaghetti code. It's unmaintainable and if you come back to it in 6 months time you'll have a hard time understanding what all of it is doing.

-
Just from skimming over the code there seems to be a lot of code repetition especially in getBestMove.

-
Strings in Java are immutable. Which means any operation which modifies a string actually creates a new string. Also you do a lot of parsing and converting back and forth between strings and numbers which won't help with the speed issue.

So my general advise would be: Create a dedicated Board class which encapsulates the board access and operations performed on the board. As backing store I'd probably chose a 2d int-array representing the cells. If you need to print it on screen you can have a convenient output method which converts it into the string representation.

This will get rid of a lot of unnecessary converting to and from strings and should result in some speedup (how much exactly I can't say). It will also provide a starting point for a better code structure.

StackExchange Code Review Q#57752, answer score: 7