-3

So my program is a chess AI. It works by making a tree for all the possible moves.

The problem is that after a depth of 4, this tree becomes really big. At the starting position, there are only 20 possible moves so it's not that bad, but once the program reaches later in the game, there are closer to 40 possible moves which means the tree is exponentially larger and this causes the error.

I'm also interchangeably getting java.lang.OutOfMemoryError: GC overhead limit exceeded

My question is whether there is a way to either increase the heap size to > 1024 Mb, or get around this issue some other way. Thanks <3

Pauk_Jhonson
  • 45
  • 2
  • possibly, your issues are solved by re reading and fixing some issues in your code – Stultuske Feb 05 '21 at 08:39
  • look at the `-Xms` and `-Xmx` options. Also you may want to read about alpha beta pruning. – Henry Feb 05 '21 at 08:39
  • yeah I'm implementing that right now but this will still be a problem if i want to reach further depths – Pauk_Jhonson Feb 05 '21 at 09:05
  • I'm not sure that it's code issues because on a depth of 3 it works fine, and 4 works for the first 2-3 moves then breaks down – Pauk_Jhonson Feb 05 '21 at 09:06
  • The maximum heap size depends on the Java VM used. 32-bit Java VMs have a small heap, 64-bit Java VMs can have larger heaps and the [Eclipse OpenJ9 _Large Heap_ VM](https://adoptopenjdk.net/releases.html?variant=openjdk15&jvmVariant=openj9) supports a heap sizes even greater than 57Gb. – howlger Feb 05 '21 at 10:34

1 Answers1

0

Increasing Heap size is rather straightforward. As described in this answer https://stackoverflow.com/a/6452812/7201500 you can use -Xmx

However, it will not get you very far, because your memory need will continue to grow exponentially with the number of move that you want to calculate. Considering what you said, even with a beefy computer, you are unlikely to calculate more than 10 moves.

You would need to use a strategy that doesn't keep in memory everything it calculated, and if possible that only calculated usable moves. Because after your memory problem, you are going to run into a computation problem. Processors are fast, but exponential grow is even faster.

As a first step, you might refine your code to discard every move analysed and found less optimal than the others. This should help you with the memory problem. To go further, the algorithm need to be more complex, but you are lucky : This subject have been studied a lot.

You can take a look at Stockfish or some other open source chess engine to get some idea on how to optimise your algorithm.

Kevin FONTAINE
  • 845
  • 8
  • 17