On Feb 28, 10:59 am, gavino <·········@gmail.com> wrote:
> free ones to head of line
http://devtrigo.com:7159 - project from CS class last semester I wrote
from scratch in CL.
On Feb 29, 6:14 pm, jrwats <······@gmail.com> wrote:
> On Feb 28, 10:59 am, gavino <·········@gmail.com> wrote:
>
> > free ones to head of line
>
> http://devtrigo.com:7159- project from CS class last semester I wrote
> from scratch in CL.
I took a look, just cause I was curious. Page seemed remarkably
blank.
On the right hardware, with the right implementation, I imagine CL
would be a reasonable choice for writing a chess engine. I'm inclined
to think that that hardware/implementation combination doesn't exist
at the moment, at least if you were trying to write an engine that
would be competitive with good commercial engines (OTOH, if you could
write a chess engine that could be set to play at a certain level, and
which played in a fashion typical of players at that level you could
make a mint, and I think CL might be as good a choice for that as any
language.)
Chess is a pretty well-understood problem- at least the current
approach to chess is well-understood, and works amazingly well under
most circumstances. If humans can still compete with them it is
largely because they have learned a lot from them- in particular,
computers have shown that the defense usually has more resources than
even very strong players used to see.
The best engines don't disclose their evaluation functions, but I
think it's safe to say that they are all pretty simple. So there isn't
much gain in using a more expressive language to code that function.
What most professional chess programmers do (I think) is look for ways
to more efficiently prune the tree, and look for ways to shave cycles
from common operations. That, and wait for hardware to improve ;). I'm
impressed by how fast some CL implementations are, even (or
particularly) the open source ones. SBCL seems to compare well with
Sun's implementation of Java for x86 Linux. That's really impressive,
when you consider how much money has been poured into the Java(TM)
platform. But when it comes to this sort of problem- one where the
algorithms are well understood, and efficiency is the dominant factor-
both CL and Java are going to lose to C, particularly given the effort
that has gone into optimizing the code generation of the best C
compilers.
So, I'm a reasonably competent CL programmer (for some values of
reasonably competent), but I'm also a bit naive in some respects. I
tend to take the language as it is given to me, and any implementation
is fast enough for what I do with CL- I'm generally I/O bound anyway.
If I really need raw performance (and I rarely do these days)- well, I
made my daily bread with C for a few years, so I can just go write a C
program. But.. lately I've been playing with some IR algorithms, and
what I'm doing is getting more and more expensive, cycle-wise.
Hardware is cheaper than programmer time, of course, but.. the
overhead for the extra hardware isn't, necessarily. I guess I've never
entirely bought into the "performance doesn't matter" thing.
So, I'm curious about this- let's say that you have a particular
implementation (say SBCL or CMUCL) running under Linux on stock x86
hardware. You want to come as close as you can to the performance of
the best chess engines. In other words, in the end, you want to
generate the most efficient code you can, from CL. You have access to
all the important code (from the OS up, really). The constraint you're
working with is that if you have to go so far that writing it in C is
easier, you've gone too far. And, obviously, you can't design a
special chip.
What would your general approach be (beyond things like type
declarations, etc.)? How would you go about generating the most
efficient code? You're actually doing fairly simple computation here,
but you're doing it many, many times. I'm pretty sure I've seen people
talk about this here, with CMUCL, but I can't find the posts I am
thinking of. The compiler is available at compile-time, so... well,
anyway, I'll leave it at the initial question. What would your general
approach be if you had to speed up a brute force search to C-like
levels, if you didn't care about portability?
P� Sat, 01 Mar 2008 15:39:27 +0100, skrev Campo <··········@yahoo.com>:
> On Feb 29, 6:14 pm, jrwats <······@gmail.com> wrote:
>> On Feb 28, 10:59 am, gavino <·········@gmail.com> wrote:
>>
>> > free ones to head of line
>>
>> http://devtrigo.com:7159- project from CS class last semester I wrote
>> from scratch in CL.
>
> I took a look, just cause I was curious. Page seemed remarkably
> blank.
>
Funny I tried it in Opera, Exploer and Firefox and got the chessboard in
all.
> On the right hardware, with the right implementation, I imagine CL
> would be a reasonable choice for writing a chess engine. I'm inclined
> to think that that hardware/implementation combination doesn't exist
> at the moment, at least if you were trying to write an engine that
> would be competitive with good commercial engines (OTOH, if you could
> write a chess engine that could be set to play at a certain level, and
> which played in a fashion typical of players at that level you could
> make a mint, and I think CL might be as good a choice for that as any
> language.)
>
I tend to disagree in that. It is possible that it will run a bit slower,
but not enough to make much of a difference if you code it right. I also
don't see the point of writing a chess program that beats chess masters as
a primary goal. Most players are after all not chess masters and I feel it
is more important to engage the players at the level he is at so that
beating it is a difficult, but not impossible, challenge.
As such at beginner level the computer makes beginners mistakes. As you
advance the rules for evaluating moves change and become more involved. It
is simply no fun to play a program that can beat you every time, neither
is a good way to learn chess.
--------------
John Thingstad
On Mar 1, 11:00 am, "John Thingstad" <·······@online.no> wrote:
> På Sat, 01 Mar 2008 15:39:27 +0100, skrev Campo <··········@yahoo.com>:
>
> > I took a look, just cause I was curious. Page seemed remarkably
> > blank.
>
> Funny I tried it in Opera, Exploer and Firefox and got the chessboard in
> all.
Ah, well nothing showed for me, Firefox under Ubuntu. I didn't
investigate further.
> > On the right hardware, with the right implementation, I imagine CL
> > would be a reasonable choice for writing a chess engine. I'm inclined
> > to think that that hardware/implementation combination doesn't exist
> > at the moment, at least if you were trying to write an engine that
> > would be competitive with good commercial engines (OTOH, if you could
> > write a chess engine that could be set to play at a certain level, and
> > which played in a fashion typical of players at that level you could
> > make a mint, and I think CL might be as good a choice for that as any
> > language.)
>
> I tend to disagree in that. It is possible that it will run a bit slower,
> but not enough to make much of a difference if you code it right.
I think you might find that you're wrong about that. I would be very
surprised if someone wrote a chess engine in CL that was competitive
against the best commercial engines, absent heroic measures. I think I
explained why in my post. OTOH anyone could write an engine in a few
weeks that played at the master level- you might even be able to do
that in Python, though of course a good CL implementation would be a
much better choice. Getting from (USA) master to super-GM is a big
jump. The only way we know to make computers make that jump is to look
deeper down the tree- it's not exactly brute force search, as the tree
has to be mercilessly pruned, but it is the same from a performance
point of view. The more positions a machine can look at, the better it
plays.
> I also
> don't see the point of writing a chess program that beats chess masters as
> a primary goal.
I'm inclined to agree with you on this. But the bragging rights are
worth a lot. So engine authors do seek to make their engines stronger
(anyway, if you had devoted your life to programming computers to play
chess, what would you do? throw up your hands and say "It's done"?)
Also, the stronger the engine, the better its analysis of positions-
that's actually what most serious chess players use the engines for.
They don't play against them much, particularly now that they can play
blitz all day on the internet against other GMs.
> Most players are after all not chess masters and I feel it
> is more important to engage the players at the level he is at so that
> beating it is a difficult, but not impossible, challenge.
Well, that was my OTOH. If you could make a program that could play at
a beginner level, _like a beginner_, you would be rich and famous, and
you could clothe yourself entirely in supermodels- that would be hot.
The problem is that when you take a modern chess engine and set it to
"1600" strength, it plays like a grandmaster (sort of, but it won't be
giving up material) four moves in five, and then leaves a piece en
prise. Some work has been done on this, but it mostly amounts to
getting the engine to drop a piece to a 2 or 3 move combination. This
is a natural consequence of how machines currently play chess.
If you wanted to make a machine reason about the chess board, or
pattern match in the way a good player does, CL might be a great
choice (if I'm not mistaken SBCL's genesis had something to do with
Go). I'm an adequate chess player- when I play socially against most
people I don't really look ahead. I just put my pieces on good
squares. Usually people drop a piece early (and then play on, and
on..) If they are better than that, they wind up putting their pieces
on bad squares, and eventually I see a pattern that tells me I can
win- one place I do look ahead is when I am considering whether or not
I can simplify into a won endgame (as an aside, if you want to get
better at chess, learning as much as you can about which endgames are
won is worth a lot of rating points below a surprisingly high level-
the first time I beat a FIDE master it was because he let me simplify
into a won K+P ending). When I was 15 I knew hundreds of games by
heart. I've played over tens of thousands of games (the things we did
to pass the time before the internet...). I don't bother calculating
things I already know.
The problem is that machines don't play that way. They use a simple
evaluation function, but apply it to millions of positions. No one has
managed to build a chess engine that plays like a human. Actually, no
one is quite sure how humans play, but the memory bank of positions
theory is currently in vogue. It turns out that it is much harder to
write programs that reason by fuzzy analogy than it is to write
programs that look at a lot of nodes.
Anyway, my point was more general. Let's assume that looking at lots
of nodes is the way to go (chess is not the only problem like that)-
what heroic measures should I be willing to undertake, given current
implementations and hardware? I know there have been some posts here
about this sort of thing- my fuzzy pattern matcher is telling me I
ought to go read through Thomas Burdick's entire posting history.
> As such at beginner level the computer makes beginners mistakes. As you
> advance the rules for evaluating moves change and become more involved. It
> is simply no fun to play a program that can beat you every time, neither
> is a good way to learn chess.
I've beaten some of the strongest engines in the world, actually (if
only chess wins were transitive). I played some very offbeat Chess to
do so. There is a certain enjoyment to be derived from that, but
you're right that it is a niche taste. The problem is that no one has
ever built a chess engine that plays in the fashion you suggest- at
least no one has built one that can beat a retarded five year-old. But
I'm off Chess now. Go looks like it will have a bit more longevity.
P� Sat, 01 Mar 2008 22:44:44 +0100, skrev Campo <··········@yahoo.com>:
>
>> Most players are after all not chess masters and I feel it
>> is more important to engage the players at the level he is at so that
>> beating it is a difficult, but not impossible, challenge.
>
> Well, that was my OTOH. If you could make a program that could play at
> a beginner level, _like a beginner_, you would be rich and famous, and
> you could clothe yourself entirely in supermodels- that would be hot.
> The problem is that when you take a modern chess engine and set it to
> "1600" strength, it plays like a grandmaster (sort of, but it won't be
> giving up material) four moves in five, and then leaves a piece en
> prise. Some work has been done on this, but it mostly amounts to
> getting the engine to drop a piece to a 2 or 3 move combination. This
> is a natural consequence of how machines currently play chess.
>
>
>> As such at beginner level the computer makes beginners mistakes. As you
>> advance the rules for evaluating moves change and become more involved.
>> It
>> is simply no fun to play a program that can beat you every time, neither
>> is a good way to learn chess.
>
> I've beaten some of the strongest engines in the world, actually (if
> only chess wins were transitive). I played some very offbeat Chess to
> do so. There is a certain enjoyment to be derived from that, but
> you're right that it is a niche taste. The problem is that no one has
> ever built a chess engine that plays in the fashion you suggest- at
> least no one has built one that can beat a retarded five year-old. But
> I'm off Chess now. Go looks like it will have a bit more longevity.
I would do nothing as drastic as what you suggest.
It is sufficient to make a different evaluator function for each player
level.
The evaluator determines the criteria a beginner would look for. it would
know fewer opening and closing moves etc. It is ie. not necessary to mimic
human thinking, merely human behaviour.
Take a look at my Othello program for a basic idea..
http://home.online.no/~jpthing/games/othello.html
Take a basis in this function:
(defun computer-move (board level side)
(cond ((eq level 'clueless) (random-move-strategy board side))
((eq level 'beginner) (maximum-disc-strategy board side))
((eq level 'novice) (stable-disc-positional-strategy board side))
((eq level 'expert) (maximum-mobility-stategy board side))
(t (error "Not a legal level!"))))
To understand what this mean you need to know some othello strategy
http://www.site-constructor.com/othello/Present/Basic_Strategy.html
--------------
John Thingstad
On Fri, 29 Feb 2008 15:14:26 -0800 (PST), <······@gmail.com> wrote:
> On Feb 28, 10:59 am, gavino <·········@gmail.com> wrote:
>> free ones to head of line
>
> http://devtrigo.com:7159 - project from CS class last semester I wrote
> from scratch in CL.
Really?? I wonder why the page source says:
<script type='text/javascript' src='js/chess.js'></script>
Back your claim up with source...if you can.
This explains why someone with javascript disabled gets a blank
screen, the claim is false, there is not lisp code running here.
--
One of the strokes of genius from McCarthy was making lists
the center of the language - kt
--
Posted via a free Usenet account from http://www.teranews.com