[MUD-Dev] Better Combat (long)

[Vincent Archer]

According to Byron Ellacott:
> David Kennerly wrote:

>> knowledge base of known vertices with known values.  I'd love to
>> hear from a chess programmer or a self-conscious chess player
>> about the internals of either intelligence.  How do chess
>> programs think?  How do chess players think?

> The game can be seen as an n-ary tree of legal moves leading to
> new board states.  It's an infinite tree, since there are legal
> moves that can loop states.  From any given state S, you do a
> breadth

Not too much however. You can go thru any given state only 3 times.
After that, the game is reputed a draw.

Anyway, a chess program has four important parts:

  - The evaluation function. This function takes a board, and
  attempts to determine whether or not the situation is in favor of
  one side, and if so how much does it favor said side.

  - The move generator, which generates, from a given board position
  all legal moves in an "interesting" order (more of this below)

  - The quiescent determinator (more of this below)

  - The alpha-beta algorithm. This is a very well known and simple
  algorithm. A Google search will turn several explanations of the
  way it works.

The evaluation function is typically what is the most critical
function of the game. The fastest it is, the deeper you can go in
the game. This is what was advertised in Deep Blue and the
like. When they say "you can analyse 1.000.000 moves per second",
what it means is: you can do a full board evaluation 1.000.000 per
second.

The move generator is an important piece of software as well. If you
look at alpha-beta, you'll see that the order in which you evaluate
your moves is important. If you have a tree of 5 moves at each
point, 5 deep, you have 3125 positions to evaluate. Depending in
which order you do the evaluation, you can have from anything from
3125 to 55 positions to evaluate (a perfect ordering leads to square
root of total positions being used).

The quiescent determinator is a piece that most layman descriptions
on chess pass over. One problem of chess is that positions change
sometime quickly. If your programe decides to see at a depth of 10
moves. You have a position, and you're ahead. It looks good.

Of course, at move 11, your opponent takes your queen and puts you
in check. That's called the Horizon effect: your programe doesn't
see below the horizon. Modern programs don't look at a fixed depth;
instead they have a "quiescent" determinator which tells them when
its safe to evaluate a board, because the position is not expected
to change greatly over the next few turns.

Those are the components of a chess program's intelligence.

> The apparent skill of the AI is thus determined by how many moves
> you are willing to look ahead, and how effective your desirability
> function is.  Most consumer grade chess programs use the
> difficulty setting to determine how far ahead they look.

That, and the ordering. For the same amount of moves evaluated, the
order can mean an enormous difference in the depth of the tree.

--
	Vincent Archer			Email:	archer at frmug.org

All men are mortal.  Socrates was mortal.  Therefore, all men are Socrates.
							(Woody Allen)
_______________________________________________
MUD-Dev mailing list
MUD-Dev at kanga.nu
https://www.kanga.nu/lists/listinfo/mud-dev