Author: Vincent Diepeveen
Date: 14:12:54 09/10/02
Go up one level in this thread
On September 10, 2002 at 16:02:10, martin fierz wrote: draughts = international 10x10 checkers. That's the polish rules as used in: Russia (and all the countries around it), France, Netherlands, Senegal and another load of countries. Of course UK and Italy have its own rules and the US has so many checker variations that i lost count, every pub has its own rules there i bet :) >On September 10, 2002 at 15:33:30, Vincent Diepeveen wrote: > >>On September 10, 2002 at 14:30:56, martin fierz wrote: >> >>>On September 10, 2002 at 09:26:14, Eli Liang wrote: >>> >>>>A couple of chess programming questions: >>>hmm, i only wrote a checkers program, but here's my take: >>> >>>>(1) Are there any uses for ProbCut and/or Multi-ProbCut in chess positions where >>>>the variance of leaf-nodes is low? >>> >>>i've tried multi-probcut and it works well in checkers. i never tuned it as much >>>as my own pruning algorithm, and it doesn't perform quite as well - but it is BY >>>FAR better than no pruning. i'll be trying to tune it in the near future. for >>>games where the eval doesnt swing wildly, MPC is a fantastic algorithm. >> >>In my draughtsprogram, of course draughts is a more complicated game >>than checkers and EGTBs play a smaller role there than they do in checkers. >> >>But in any endgame i search at a 10x10 board already like 40 ply fullwidth >>easily. Middlegame like 20 ply fullwidth *easily*. >> >>At the very quick time controls i get 16 ply easily with Napoleon. >> >>In endgames i outsearch even good draughtsprograms by about 10-20 ply. >> >>Napoleon has saved many lost positions in the endgame, despite that i >>feel its endgame code sucks ass. >> >>The whole game of draughts and checkers is only about zugzwang. >> >>How can MPC work *anyway* if doing nothing is a GREAT thing to do >>in checkers? >> >>The first few versions of napoleon used to forward prune the >>last few plies and it was great to solve the most difficult tricks >>even faster (it already sees everything any world champion has >>found in tactics within microseconds of course). I concluded then >>that it worked, but i am of course a very stupid draughtsplayer. >> >>I am at the level of draughts like most chessprogrammers are in >>chess. I know all the things, but if i play i blunder away so many >>stones that i get sick of it. >> >>When i threw it out, it played much better. >> >>Can you explain why MPC works for you? > >MPC generally is a good idea if scores of a shallow search have a good >correlation with scores of a deep search. in checkers, this is true. in chess it >is not true, or very much less so - and i think it's the same in draughts. >i think your version of draughts is with "flying kings" - right? my take on this >is that the main difference between american checkers and chess is that chess >has a king. you can sac a lot of material but still win, because you get to the >king. which destroys the basic MPC assumption that if you search to e.g. half >the depth of your nominal depth and the score is far out, it's a bad move. for >example, you sac a piece for a raging attack, but you don't search far enough so >you only see a missing piece. >in american checkers, if you lose a piece, you are simply lost in general. there >are very few exceptions to this simple rule, like when you get the first king, >but these exceptions can or should be part of your eval. so when you do MPC in >checkers, if you ever get to the point where you get a material advantage, it is >very likely that it is there to stay. also, in checkers, mistakes are there to >stay. like pawns in chess. if you move g4,h4 with your king on g1 in a "normal" >midgame position, you will be punished. if you move Nf3-h4 you will likely not >be punished, because you can move back to f3 - of course you lose time, but >often that's not such a problem. checkers is the equivalent of pawn play. you >move your last defending piece off you back rank, boom, you're busted. and the >eval knows this immediately. and MPC will find it and that's why it works. >in draughts with the flying kings it is much harder AFAIK - not that i know much >about it though... but i think you can sac up to 3 men to get the first king and >come back into the game. like chess, the MPC assumption is violated there. > >>Other question, not related to the above story, just general >>interest: how many professional checker players are there >>in the world now that tinsley is dead? > >i think the answer is "one". ron king. but i think tinsley was a math teacher or >something - not a professional checkers player. both checkers players and >checkers programs are really low-level compared to chess players and chess >programs. simply because the field is not anywhere near as competitive. we have >about 5 active checkers programmers. in chess you have much more. the more >competition, the harder you work and the greater the chance that you have some >good programmers among you... > >>Another question. What do you do in your qsearch for checkers? >just play on until no captures are on the board. since captures are forced in >checkers, that kind of works. schaeffer used some shot detection scheme to avoid >evaluating "quiet" positions that were in fact not quiet, and i think that's >been used to good effect in draughts too. ed gilbert once tried that but got >nothing out of it. i tried but got nothing out of it. it's well possible that >our implementations sucked ass, as you would say. schaeffer's data on this is >not very convincing though. i also think that in checkers, the effect of this >diminishes with increasing search depth - generally less pieces on the board, >and therefore less shots you miss. maybe that's why it never helped us, because >we search much deeper than chinook did when schaeffer tested this. still, it's >something i'd like to revisit some day... > >aloha > martin > >>>>(3) Reading Aske Plaat's search & re-search paper, it really seems like mtd(f) >>>>is something of a magic bullet. But I note it seems that more programs don't >>>>use it than do (for example Crafty). What is wrong with mtd(f) which Plaat >>>>doesn't say? >>> >>>i'm using MTD. i tried windowed search, PVS and MTD. in my tests, in long engine >>>matches, MTD performed marginally (no statistical significance...) better than >>>PVS. it typically searched a low 1-digit % less nodes for a given depth than >>>PVS. >>>i don't know how to get a PV out of MTD. in normal searches, a pv node is where >>>the value is > alpha but < beta. in MTD, you never get this condition. >>>retrieving a PV from the hashtable is possible, but in all probability, you will >>>not get the full PV. which is real bad for debugging if you want to know what >>>the program was thinking at the time... i once asked here how to get a pv from >>>MTD but got no answer - and if you can't get the pv, then that is a major >>>drawback. >>> >>>>(6) Has anyone found any real "practical" benefits to fractional-ply extensions? >>> >>>yes. i tried recapture extensions of different depth, and half a ply gave the >>>best result. don't ask me why, it's just an observation. >>> >>>aloha >>> martin
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.