Author: Uri Blass
Date: 08:00:15 01/24/02
Go up one level in this thread
On January 24, 2002 at 10:12:21, David Rasmussen wrote: >On January 24, 2002 at 08:32:39, Uri Blass wrote: > >> >>1)I admit that I understand nothing about hashtables in chess programs but I do >>not understand what is the problem to find a move at reduced depth and ignore >>previous hash table information if they can give you only a score and not a >>move. >> > >That's what I thought myself. But I thought there must be a reason why people >don't do that. I will of course test is myself, but I wanted to ask first. > >>2)I may be wrong but it seems to me that you simply read Crafty's code and >>decided to do the same and this is the reason that you use depth-2(crafty is >>using depth-2 in search.c) >> > >I don't know what you mean. Crafty isn't the only program using IID, and Hyatt >certainly didn't invent it. Lots of programs use it, so why shouldn't I? I made >statistics of how often my program is in the PV, but has no hash move. It was >quite often. That must hurt move ordering and take time. Then I implemented it >and it helps some, but as I said, it doesn't catch all cases. The reason why I >use depth-2 is because my testing shows that it's best. A lot of other people >use depth-2. Again, Hyatt didn't invent this, nor is he the only one who has >tested this. Anyway, why do you say that? > >>I guess that you also use alpha and beta like Crafty. >> > >Alpha-beta search? Yes, I must admit I do. So do 99% of all others. Hyatt >_certainly_ did not invent alpha-beta... I have been doing alpha-from the start, >long before I heard of Crafty. My program is not new, you know... I did not meant to the alpha beta algorithm, but to the values of alpha and beta in the iterative internal deepening. I know that your program is not knew but Crafty is also not new and it seems to me that a lot of people copy their algorithm from the same source. > >>I understand the idea of internal iterative deepening to find a move that is >>good enough at reduced move but I do not understand why start with good enough >>and not start with the best move at even reduced depth. >> > >What? I mean that internal iterative deepening(at least in the way that it is used in Crafty) does not always find the best move at reduced depth and it is "happy" if it finds a move that is better than beta. I already saw programs search illogical moves only because they did not reject it for the right reason and I believe that correct internal deepening can prevent it when the remaining depth is big enough. > >>I thought that it may be possible to start with >>search(-infinite,infinite,depth-4) and >>only later to continue with search(alpha,beta,depth-2) >>when you start from the best move that you found at depth-4. >> > >The Search() call in IID is not "just" a normal call at shallow depths to >determine a good move. In this call itself, there wont be any good move either, >so IID is performed again, until the remaining depth is less than some limit. >That's why it's iterative deepening. If you do depth-4, it will go (for example) >11,7,3 and possibly there wont be enough move ordering information from call to >call, for this to be effecient. Also, if you do depth-4, your lower limit, the >one mentioned before, will have to be at least 5. Anyway, I have tried with >different approaches, and this one works best for me. > >>Note that it is possible that 4 is not big enough and we need bigger number. >> >>The reason is the fact that search(-infinite,infinite,depth-4) may find a mate >>or winning a queen when search(alpha,beta,depth-2) may find the wrong move(a >>move that is good enough but not winning and search(alpha,beta,depth) may take >>more time(in the case of mate it is obvious and in the case of winning a lot of >>material it also seems usually correct to me because of null move pruning) >> > >The object is very seldom to spot a mate etc. In 99.999% of all IID cases, we >just want some reasonable move instead of having _no_ idea what is good. I agree that reasonable move is better than nothing but the best move may be even better than reasonable move espacially when finding the best move is easy and the remaining depth is big. I may change (-infinite,infinite) to (beta+100,infinite) at reduced reduced depth. If the reamaining depth is big enough and you do not find a move that is better than beta+100 at reduced reduced depth then you did not waste a lot of time and you can ignore it but if you find a move that is better than beta+100 starting with this move can clearly save time for searching at reduced depth and can clearly save time for the regular search later because when you start from the best move and not from a move with a score that is sligthly better than beta the opponent has less threats and you can prune more moves by null move pruning. I hope that my idea is clear. > >>3)Note that I do not plan to use hash tables in a similiar way that chess >>programs use them because I want to evaluate sequance of moves and not only one >>position so I can see if one side make no progress and punish that side in the >>evaluation. >> > >Your choice. > >>I dislike the fact that programs use hash tables in a similiar way that I did >>not learn so they cannot detect fortress position or positions when one side >>gets the initiative(this is a bigger practical problem and programs do not see >>that a sequence of moves when the program earns positional bonuses again and >>again is better than a sequence of moves with slightly better score when the >>program lose positional bonuses again and again) >> >>I do not know today exactly how to use hash tables but I do not plan to do >>something wrong only because it is better than what I do now. >> > >Why not, if you think it is better? If you really don't think it's better, then >fine by me. > >/David It is better than what I do now but I do not like the idea to do something in the near future only to destroy it later for something better that I may find later and I believe that I may find a better way to use hash tables. The problem is to define what is obvious for humans without destroying the information in the hash tables. I have other things to do before hash tables that are more important for playing strength(mainly iterative deepening and extensions,I am not sure about null move because I know that at least Junior does not use null move so it is possible to try other extensions and pruning ideas) Uri
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.