Author: Brian McKinley
Date: 18:18:54 09/29/99
Go up one level in this thread
On September 29, 1999 at 17:53:20, Andrew Williams wrote: >On September 29, 1999 at 16:12:35, Brian McKinley wrote: > >>On September 29, 1999 at 06:40:29, Andrew Williams wrote: >> >>>Again, because you never establish >>>exact scores, you can't keep the PV in the normal way; you need to use your >>>hashtable to keep track of it. >>> >> >>I am concerned about this statement because I use MTD(f) and don't use my hash >>tables to determine my PV. Maybe I don't use the normal way of tracking the PV. > >Don't be too concerned. I had never considered any other way of tracking the >PV. If I live to be a million I would never have come up with your approach. >It's a bit late, so I don't want to do anything now, but I am DEFINITELY going >to try this the next time I sit down to work on my program. > > >> When I save a score from a evaluation or a lookup that might be backed, I save >>the "path" with it. This way the both the PV and the score get backed up. This >>may sound slow, but I only save the PV if there is a chance the score will be >>backed up at the previous ply (currentply.best < -previousply.best). This is >>only true for a small percentage of the nodes evaluated. I keep a pointer to a >>PV at each ply. Before I back up a score with an associated PV and return to >>the previous ply I swap the PV pointers for the current ply and the previous ply >>so that I can reuse that space the next time I need to save a PV at the current >>ply and so that my current PV storage space doesn't get overwritten. >> >>Once lowerbound >= upperbound I simply use the PV associated with the score from >>the last iteration. This seems to work. What am I missing? >> > >Nothing, as far as I can see. See above. > >>I have found positions in the past where AlphaBeta does not return the same PV >>as MTD(f), but mostly the scores have been the same and difference appears to be >>because of move ordering. In the other cases, the MTD(f) search appeared to >>suffered from a transposition that was searched deeper and returned a lower >>score causing the need for a research. Because I don't do a research, I got a >>bad PV and score. I haven't figured out (or given much thought to) how to deal >>with this problem. Maybe I should trap for this condition and clear the hash >>table when it happens. This seem drastic with MTD(f) and could seriously affect >>performance if it happens often. There might be the potential for an infinite >>loop if I don't reset the upper or lower bound too. At this point I am simply >>thinking out loud so it is time to post. >> >>-Brian > >Well my approach doesn't give perfect PVs, particularly when the hashtable >starts to get stressed. I've found that on test-sets, my PV leads to a position >with a score that is the same as the backed-up score in a very high proportion >of cases, even when long searches are attempted. When playing games, however, >I find that this figure drops dramatically. > >What is the name of your program? My apologies if I've missed it in the past. >Does it run on ICC or FICS? > >It's really good to "meet" someone else using MTD. > >Andrew WildChild is the name of the program and it can sometimes be found running on ICC. It originally only played loser's chess. It now plays crazyhouse and normal chess, but neither very well. I am currently in the middle of a major restructure so it has not been running for a few months. I have added a parallel search, and I am considering distributing the search at or near the root. At the same time I am re-organising some of the classes and turning them into COM objects. I hope to have it running again in a month or so, but I haven't had much time to work on it lately. Once I finish these changes I plan to focus on normal chess and hopefully bring that rating inline with its loser's rating. Brian
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.