Quote:Original post by mandar9589
1. Why are java games slower in computing than games programmed in C/C++? is it that creation of objects in java takes more time, or is it the memory allocation?
I can think of several reasons. The abstraction that the virtual machine provides has a cost in performance, even if Java supporters tend to deny it.
It's probably the case that people that learn Java first develop habits that hurt performance in this type of program (although those habits might be good for other types of programs). For instance, I had been programming for 10 years before I heard the word "object", so I know how to program without them. If you go around creating objects all over the place, your performance will suffer (mostly because object creation in Java always implies dynamic memory allocation, if I am not mistaken). A fast alpha-beta searcher doesn't do any dynamic memory allocation.
Quote:
2.I have programed this game using negamax algorithm. I added alpha beta pruning to it. Since the number of nodes were very high even after pruning, I gave it a beta cut-off by writing *** Source Snippet Removed ***
again after writing this, the nodes very very high in number.
so I replaced alpha>beta by alpha>=beta. this change made drastic decrease in number of nodes. Is this correct?
Yes, that is correct. There will only be a huge difference if your evaluation often returns the same values.
Quote:3.Right now I have deleted all the previous evaluations done,and writing new one. so the basic step I took was to write the winning conditions only, on depth of 14 it takes about 2.91 mins(This is too much of time,and want to reduce the time significantly.) to compute the first move on the empty board.
and about 15ms to calculate at depth of 4. So how can I calculate the time which will be required to search till depth of 42plys?, I can see there is exponential relation in this.
Yes, there is an exponential involved. A search of depth 15 typically will take some constant factor of time more than a search of depth 14 (say, 2.5 times more time). The factor is what I call "effective branching factor", although I don't think that term is standard.
The effective branching factor depends on how well you program your search. In the worst case, you always explore the worst moves first and the best moves last, and then alpha-beta doesn't prune anything and your effective branching factor is around 7 (whatever is the true branching factor of the game tree, but let's say 7 for simplicity). If you had perfect ordering, the branching factor would be sqrt(7). But then again, perfect ordering requires knowing what the best move is, and if you know that you don't need to search. ;)
In practice, you should get close to the sqrt(7) limit. Actually, hash tables can bring the effective branching factor down even lower.
You should measure how long it takes your program to search depths 1, 2, 3... (until you get bored of waiting), and then plot the logarithm of the time spent. You'll probably get something close to a straight line, whose slope indicates the effective branching factor. This is a very useful thing to do if you are working on improving your move-ordering heuristics or your hash tables.
Quote:4.Since now my method has only one checking of whether its winning or not, it is computing very fast and more number of loops I add to this method, the more time it takes and this is undesireable. So even if I want to add all the configurations which will state whether its a odd threat or even threat, there would be atleast 16 more conditional statement in 4 loops and this will take most of the time and so my search depth has to compromise with the time available for search.and this is again undesireable.
Oh, the evaluation function that checks threats correctly will be much more complicated than that. When I wrote this with a friend many years ago, we ended up coding it in 1600 lines of assembly code. But a depth-8 search using this evaluation function will probably play much better than your depth-14 search with no knowledge of the game.
Quote:So do you have any more ideas as to how to speed up the search of the game,without reducing the depth,one of them might be using hashtables along with zobrist keys ?
The first thing is move ordering. Some form of "history heuristic" (look it up) will work well.
Hash tables also help, both because they eliminate searching repeated branches in some conditions and because you can store the most promising move to be explored first if you have to search this node again.
You should also use iterative deepening. Even if it sounds counter-intuitive, searching with depth 1, then 2, then 3, ... up to depth 14 is faster than searching depth 14 directly. Well, at least it is if your hash tables and move-order heuristics work well.
I think you should forget about perfect play for now and simply make a strong program. This is actually better practice if you want to eventually make programs for games that are too hard to fully solve (e.g. chess).
