[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [computer-go] Data structures for Go
Makemove can be very important.
I incremental updated all kind of details for my poor go program.
That limited speed already considerable when i compare it to my 10x10
international draughts program (Napoleon). Whose only limit is the
hashtable speed to store and retrieve positions.
Single lookup to hashtable == 400 ns or so (280ns single cpu or so and
another 50% faster for opteron/a64).
So based upon that i guess you will understand why the draughts program
with a huge evaluation function, still was so much faster than the go
program which basically did majority incremental.
If you have defined in extra arrays for each group to where it influences
and where mobility goes and how strong, then the update for go is pretty
trivial and can be done relative pretty fast when i see the speed of
certain go programs.
Of course i never did local tactical searches. Just one thing that can
search a ply or 8-10 in go (brute force) from openingsposition (19x19).
Go in contradiction to chess and draughts where very little can be done
incremental, is especially suited to do many things incremental.
Best regards,
Vincent
At 17:04 13-10-2003 -0400, Don Dailey wrote:
>
>
>> The only way to do it is to run benchmarks, and I don't think ...
>
>Run benchmarks and decide for yourself, that's what I advocate too. I
>am only suggesting an alternative and have already given my
>disclaimer, your results may or may not agree with mine.
>
>
>> Could you say us what is a 'old' processor and a 'modern'
>> one? Seems to me this a very fast varying concept :-)
>
>I used the term loosely. I mean stuff we are using today which are
>fast (by todays standards!)
>
>I have heard that "modern processors" are designed to do fast memory
>to memory copies. You seem to believe that memory copies are done
>serially, but I had assumed that they must be done in parallel. I'm
>sure someone on this group knows the answer and will comment.
>
>Anecdotally, I could not do state copies many years ago in my chess
>programs because they slowed things down too much, and now I can.
>What has changed? Computer hardware and compilers. It's the same
>with Go. I would mention that I do everything in 9x9 go which does
>produce smaller states, but I can compiler for any board size. I'm
>sure I did this experiment when I had undo on 19x19 though.
>
>One thing you can do to find out how important any of this is, is to
>see how much time your program even spends making and unmaking moves.
>Many have posted really low numbers of nodes per second for their Go
>programs. That tells me very little time is spent making and unmaking
>moves in some programs in which case it might not matter at all. In
>such a case you might as well go for the simpler program that does not
>need undo and all the supporting data structures for bookeeping.
>
>If your program does spend most of the time in ladder/life death
>searches, and most of this time is making and unmaking moves, then it
>behooves you to do the fastest thing, whatever that is. You might be
>suprised to find the extra programming effort is not worth it, or you
>might not. To me, it's worth the trouble to run the benchmark and
>find out.
>
>Even if you get a slight slowdown, you may think it's worth it to have
>cleaner code, easier to understand code, easier to debug, easier to
>experiment with etc. Or you might not.
>
>Incidently, my program spends a lot of time making moves, since it
>does very little of anything else being a stupid program. So the undo
>test is a fair measure of the realive merits of getting rid of undo.
>For comparison, I have a Pentium 2.4 GHZ machine and do around 450K
>nodes per second. I believe most programs are doing much more
>sophisticated things and thus look at fewer nodes but I don't really
>know this for sure. In such a case, move making/unmaking speed is not
>a bottleneck anyway. Life is too short, get rid of undo :-)
>
>Don
>
>
>
>
>
>
> From: "Antoine de Maricourt" <antoine.de-maricourt@xxxxxxxxxxxxxxxxx>
> Date: Mon, 13 Oct 2003 21:37:15 +0200
> Content-Type: text/plain;
> charset="iso-8859-1"
> X-Priority: 3
> X-MSMail-Priority: Normal
> X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2800.1165
> X-BeenThere: computer-go@xxxxxxxxxxxxxxxxx
> X-Mailman-Version: 2.1.2
> Precedence: list
> Reply-To: computer-go <computer-go@xxxxxxxxxxxxxxxxx>
> List-Id: computer-go <computer-go.computer-go.org>
> List-Unsubscribe: <http://computer-go.org/mailman/listinfo/computer-go>,
> <mailto:computer-go-request@xxxxxxxxxxxxxxxxx?subject=unsubscribe>
> List-Archive: <http://computer-go.org/pipermail/computer-go>
> List-Post: <mailto:computer-go@xxxxxxxxxxxxxxxxx>
> List-Help: <mailto:computer-go-request@xxxxxxxxxxxxxxxxx?subject=help>
> List-Subscribe: <http://computer-go.org/mailman/listinfo/computer-go>,
> <mailto:computer-go-request@xxxxxxxxxxxxxxxxx?subject=subscribe>
> Sender: computer-go-bounces@xxxxxxxxxxxxxxxxx
>
> Hi Don,
>
> Could you say us what is a 'old' processor and a 'modern'
> one? Seems to me this a very fast varying concept :-)
>
> Memory bandwith is always increasing, but processor speed is also
> increasing at the same time. And the point is that if you perform only
state
> copying, the 'computing' units of your processor are idle at the same
time.
> On the other hand if you perform only computation, you could very well
> perform state copy at the same time for free (provided your computation
> uses only data within registers).
>
> The best performances are probably achieved with a well balanced
> strategy that makes sure the processor has no unit idle at any time
> (which is very difficult, and which is why Intel introduced
hyper-threading
> technology).
>
> The only way to do it is to run benchmarks, and I don't think we can
> state that such or such strategy is better for "modern" hardware. It will
> mainly depend on the ratio between memory bandwith and clock
> speed (but processor's intrinsic parallelism should be taken into account
> also).
>
> To answer your last question, I use undo.
>
> Regards,
>
> Antoine
>
>_______________________________________________
>computer-go mailing list
>computer-go@xxxxxxxxxxxxxxxxx
>http://computer-go.org/mailman/listinfo/computer-go
>
>
_______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx
http://computer-go.org/mailman/listinfo/computer-go