I tried to use optimal types to store and copy data, and used MapReduce to evaluate branches (actually, poorly implemented Map, and parallelized the Reduce function).
To give you an example of what I call optimal type to store data, here are what I did for my BFS, which is very linked to the performance of the recursion. The types I give in my explanation are Java type.
First of all, after looking at how optimizations are done for chess AI, I decided that positions (players and walls) would be Short. Actually, I wanted 4 bits for the x position and 4 bits for the y position. (Byte type use 8 bits, but one bit is used for negative number so it wasn’t handy).
In my BFS, I use a hash that gives me the previous point needed to get to one point. As points are of Short type, there are no possible collisions and this hash is accessible in O(1).
This hash allowed me to check whether I already tried a point or not, and I used it to recreate the shortest path.
To know which point I should check, I used the Queue ArrayDeque. I just wanted to push elements at the end of this queue and pop the first element. To do this, ArrayDeque is the fastest type I know.
To check if one point is on the objective, I used bitwise operations. Objective points were either going to a fixed x or a fixed y, so I put the non-fixed coordinate as 0x0F to distinguish it easily.
Even though it was fast, I just realized I could have done better: instead of doing bitwise operations every time, I could have created a hash in the beginning of the first round that link an objective to a Set of points. Then, I would have to get in O(1) the Set (only once per path finding) and look in O(1) if the Set contains the current point.
When the current point was not the objective, I used a hash to add all neighbors to the queue. This hash was created in the beginning of the first round and updated at the beginning of each round to remove neighbors that were not accessible because of a wall one AI put on the board.
In a nutshell, I stored data in hash (with no collisions) and queue, and used MapReduce. When possible, hashes were created upstream.