I'm slowly trying to improve my chess program. It's written in Java and can look ahead 4 ply in a few seconds but going up a level means waiting too long for a reply. I already use ID and remove the worst 20% of moves on each loop. Obviously I could use C/C++/assembler etc to improve speed but I want it to run in a browser.
I tried to implement extensions but this seemed to make it play worse (?) so I guess I messed up. My current plan is to try the following. Does this look right? is it likely to improve it's play? is there anything I need to watch out for? are null moves required or are they just an improvement?
...
put on move
if the move is check
or response to check
or the move is a pawn to the 7th or 8th
or the move takes a piece on a square played recently then
extend by 1
else if the move takes a piece or moves a pawn to 6th
extend by 0.5
else
no extend
score = go up a level( depth + extend )
better score?
takeoff
...
It's a bad idea to extend both checks and responses to checks by one ply - You might end up extending till some wired in depth limit kicks in. try extending only checks and nothing more, then add ideas one by one and see which one hurts.
as for null move, it is of great help, but some precautions are needed (good material on this and other topics might be found on chesprogramming wiki)
when you extend both check and check escapes make sure you extend only those escapes where the side in check has only one legal move (maybe two but than do not extend a full ply in case of two).
You also want to make sure that you extend not to much when several of your conditions match, so when you get of of check by checking the opponent by a pawn push to the 7th you usually do not want to extend 3 ply, but just one.
PK : It's a bad idea to extend both checks and responses to checks by one ply I've now implemented it so it doesn't extend on response to check. It works OK but it still makes mistakes - I'm obviously doing something wrong!
tpetzke : when you extend both check and check escapes make sure you extend only those escapes where the side in check has only one legal move (maybe two but than do not extend a full ply in case of two). I'll add this shortly.
tpetzke : BTW 4 ply in a few seconds seems very slow is this because it runs in a browser because java should not slow you down that much.
I'm afraid I had to reorganise the code to generate these figures hence the delay in responding :
Depth 1
MinMax #n=20 time=79 nps=0k score=71
AlphaBeta #n=20 time=0 nps=0k score=71
Depth 2
MM #n=238 time=15 nps=15k score=3
AB #n=238 time=16 nps=14k score=3
Depth 3
MM #n=3691 time=453 nps=8k score=84
AB #n=3691 time=157 nps=23k score=84
Depth 4
MM #n=41859 time=1515 nps=27k score=-6
AB #n=41859 time=1328 nps=31k score=-6
Depth 1 - numbers look fine to me though your depth 1 showed 40 nodes so I assume your depth 1 is really 2 ply then.
Depth 2 - looks a little odd because the number of nodes (#n) shows 238 - I'd of thought it would be 20*20=400.
Also odd that the AlphaBeta shows the same number of nodes as the MinMax even though it runs quicker - this could be my reporting or the code. At least the scores generated are the same and it's calculating this score in less time
The nps on yours is 1211999 while on mine I get around 31000. This suggest yours is 40 times quicker. Java usually uses a JIT (just in time) compiler and normally I don't have issues with speed. C++ is obviously going to be quicker than Java and I'm guessing that you hard core chess programmers use slightly better hardware than I do (Celeron 2.4 Ghz single core with 1GB ram). Going 40 * quicker would allow me to search an extra ply but I don't think that will make a massive difference to the programs strength.
I found an issue in the reporting and this looks better. I believe it's showing 420 for minmax at depth 2 because the same function is called to see if any move is available to check for stalemate/checkmate. This output also shows that the number of nodes is always less for alpha beta, faster and generates the same move as it should.
The number of minimax nodes at d=2 should be 400+20+1, if you also count internal nodes. A bit more, in fact, because of quiescence search, as in 14 positions after 2 ply a capture is possible, and in some even deeper captures (e.g. 1. e4 d5 2.exd5 Qxd5). But because of alpha-beta you will have fewer. Some of the ply 1 moves will be rejected before all replies have been tried. If the counts you report are alpha-beta nodes, though, they seem a bit high. In Joker I have:
I'm assuming the 1st ply should be 20 but you seem to show 21? do you include resigning as a possible move Your report also showed 44 for ply 2 which I don't understand, surely there are 20 moves for white and then 20 for black resulting in 20*20 nodes. I'm certain alpha beta won't knock this down to 44. I know I'm getting 420 nodes at ply 2 but I don't know the reason for this at the moment. The extensions were turned off in my code for this report.
The alphabeta figures were shown as AB and the MinMax as MM in the table above.
I count all nodes, also internal ones. The root is also a node.
The 44 is not the complete count after 2 ply, but the count after the PV move was searched. You can see there is a later d=2 output (with the same PV) at the end of the iteration, which reports 102 nodes. If the previous best move would have been overturned, there would have been outputs in between.
So for the remaining 19 first-ply moves, there were 58 nodes needed to search them. 19 to reach them, and then at the second ply 39 to refute them. That means on average only two moves of the 20 possible black replies had to be searched to produce a beta cutoff at ply 2.
I guess Joker does not reset the count between iterations, so the 44 includes the earlier reported 21, which means it took 23 nodes to search 1. e4. That is 1 to get there, and 20 for all possible black replies, plus two QS. After 1. e4 f5 there is probably no QS but a stand-pat cutoff, as f5 is bad enough in itself even if it would not give away the f-Pawn.
