In article , Simon Waters
writes
Neil Fernandez wrote:

In addition it would be wrong to assume that there is no game with a
clearly defined and finite state space at which no computer programs
will be _able_ to play as strongly as the strongest humans can, even
with lots of processing power and parallel processing.

Urm can you rewrite that with less negatives?

Sure... In my opinion it is very feasible that finite games can exist,
at which humans will always be able to beat computer programs.

Given sufficient computing power we just solve any finite game, and play
it perfectly, which must be as good as the best human, unless the human
cheats ;-).

How do you know?

Okay there may be practical problems getting that much
computing power, but I thought we just assumed that limit away.

--
Neil Fernandez

In article ogers.com,
james writes

"Jeff Nowakowski" wrote in message
...
"james" wrote in message
e.rogers.com...

This actually sounds a lot like an excuse. The piece-value equivalence
in
Go is territory-occupied.

This has been beaten to death. Evaluation using piece values in
chess is stupid simple. It takes nano-seconds to compute and is a
very good heuristic in searching. Territory in Go is ill-defined and
not a good heuristic by itself.

-Jeff


If you see human as another kind of computer, you realize that human also
have to calculate, no matter it is Chess or Go. Stupid simple counting of
pieces - human can also do that. Only 32 pieces total. Territory
uncertainty - applicable to human too.

No matter how complicated the problem is, human computer also have to
calculate to get a result. Our semiconductor brother is missing something.
What is missing (AI?) is the big question. Semiconductor Computer can not
search for all positions in Go, neither can Human Computer.

"Too complicated" is an excuse for "we don't understand that yet".

Or...we cannot translate it sufficiently well to zeroes and ones. It
would be wrong to assume that it can be so translated.

--
Neil Fernandez

I would say that Xiangqi move generation is simpler than chess move
generation because there aren't all of the special cases; There are no
en passant captures, no castling, and no promotions.

That is true, but the blocking of the horse and elephant impose special
problems. It isn't anything too terribly difficult to work with, but I
am still unhappy with the algorithm I have currently created. Using
piece arrays doesn't have much trouble, but I am experimenting with
bitboard representation and move generation and the blockers do cause
some hassle.

But the
rule/repetition checking is far more complicated and can slow down an
engine significantly. Many Xiangqi servers fail to check and enforce
the rules because they are difficult to program, and as far as I know
none of the open source software does this correctly.

The repetition rules are incredibly complicated. Not too long ago we
talked about that problem here in rec.games.chinese-chess (most of you
probably are reading from elsewhere) and the concensus seems to be that
it is just too much to put into the engine and to leave the user in
charge. There is only one, non-free, xiangqi engine that I know of that
claims to adhere to the Asian rules and I don't recall the name.

To tell the truth I am still at a loss as to how to implement these
rules without slowing the engine to a crawl. In the current version of
my engine I had to give up on making the search consider this problem
and let it lose. I will probably still have to do that to some extent
no matter what because the degree of complexety is just too great.

Also as far as I can tell the computer-Xiangqi "scene" is not as well
developed as computer-chess. For example there is a lack of formally
defined standards like PGN, very few games available in electronic
format compared to chess, and no programs like Winboard which not only
simplify writing an engine, but also make it trivial to interface to
popular chess servers.

Not to tute my horn, but: http://xiangqi-engine.sourceforge.net is the
first attempt to create such a thing AFAIK. The first 3rd party
interface was released a week ago at http://cxboard.sourceforge.net - I
haven't coded my own interface yet Unfortunately it makes use some
hackery to work around an incomplete protocol and may not work later but
could turn into a very nice GUI. I am also looking into what needs to
be done, if anything, to the UCI protocol to make it work with xiangqi
because it looks like it might be a better option.

About the lack of PGN, this is sort of true. The current standard
appears to be the WXF format. There are some games on the internet in
this and in "algebraic" format which is basically PGN using unabreviated
algebraic notation. You can get games from club xiangqi and I don't
remember what format they use. A lot of people have been using things
like PGN, FEN, and others to represent xiangqi topics. This mostly
works but it would be better to have something specific to xiangqi so it
works better - hence my project.

So if someone is interested in developing either a chess or Xiangqi
engine they will find a far larger support group if they pick Xiangqi.
(Even more so if said person can't read Chinese characters.) I'm
interested in writing a Xiangqi engine, but am first writing a chess
engine to learn the techniques just for this reason.

I started with xiangqi; I never wrote a chess engine. There isn't any
strong reason why you need to write a chess engine first IMHO.

NR

"james" wrote in message ble.rogers.com...
I would say that Xiangqi move generation is simpler than chess move
generation because there aren't all of the special cases; There are no
en passant captures, no castling, and no promotions. But the
rule/repetition checking is far more complicated and can slow down an
engine significantly. Many Xiangqi servers fail to check and enforce
the rules because they are difficult to program, and as far as I know
none of the open source software does this correctly.


Repitition situation does not happen so often in Xianqi game. Not as often
as "Ko" in Go game. Chess also has repitition situation. For chess,
repitition basically leads to a draw, while in Xianqi repitition (capture,
check sequence) is not allowed. It is not that difficult to identify who
started the repitition and then judge accordingly.

In chess there are very simple algorithms for detecting repetition and
every competitive engine implements the draw by 3-fold repetition
rule. (The final Deep Blue chips even implemented repetition detection
in hardware.) In Xiangqi it's much more difficult since it's not just
about repetition of the position, and none of the open source engines
implements the complete set of rules. Are you familiar with the AXF
rules? They don't appear to be straightforward to implement.

I think that if human masters play Xiangqi engines and know that they
have problems with the rules, then they can exploit this weakness. So
even though you may not see this situation a lot in human-human master
level games, that doesn't mean that computers can ignore the problem.
This is pure speculation on my part since I'm not good enough to
demonstrate this ;-)

"Noah Roberts" wrote in message
...

http://clubxiangqi.com/rules/

The only thing I see is:

"It can be ruled a draw if both sides repeat a sequence of moves that return
to the same state..."

I don't see anything to indicate the necessity of anything more complicated
than chess-like repetition detection. Maybe someone needs to point to the
specific rule(s) of interest.

Russell Reagan wrote:
"Noah Roberts" wrote in message
...


http://clubxiangqi.com/rules/


The only thing I see is:

"It can be ruled a draw if both sides repeat a sequence of moves that return
to the same state..."

I don't see anything to indicate the necessity of anything more complicated
than chess-like repetition detection. Maybe someone needs to point to the
specific rule(s) of interest.



Then you haven't actually read that document.
Here are some examples:
#
# 34. A protected pieces cannot be perpetually chased if its protector
has lost its effectness. (See examples in Diagrams 83, 84, and 85)
#

*
* Knight chases Knight: If both side can capture the other side, this is
considered perpetual sacrifice and should be ruled as a draw. If one
side is blocked, the other side cannot perpetually chases it. (See
examples in Diagram 51 to 55)

#
# 29. A Pawn can perpetually chase. Two or more Pawns can work together
to perpetually chase. If one of the moves of the Pawn's perpetual chase
involves a Rook, Cannon, or Knight, it is still allowed. (See example in
Diagram 69 and 70)

Or how about these:

# 12. "One check and one chase" or "several checks and one chase" should
be ruled as a draw.(See example in Diagram 13.)
# 13. "One check and one idle" and "one check and one threatening to
check and capture" are both ruled as draw. (See examples in Diagrams 14,
15, and 16.)
# 14. "One chase and one threatening to check and capture" should be
ruled a draw. (See example in Diagram 17.)
# 15. One or two Cannons cannot perpetually chase a Rook even if the
Rook is protected, or both of the Rook's reacting moves are attacking an
unprotected piece. (See examples in Diagram 18 through 25.)

And the diagrams for #16 (two carts, one or two canons)
http://clubxiangqi.com/rules/d26to28.htm

It actually takes more than just reading the site, you have to examine
the supplied diagrams as well; as you notice in diagram 28 it takes 8.5
moves to discover a ruling. It is hard enough just figuring out what
the rules ARE, much less coding for them. And there are many, many
tests that are involved to find if it is indeed a perpetual chase/check,
and if so who wins or is it a draw. Testing with hash tables will make
you aware that there might be a case of perpetual chase/check, but they
will not catch all or even most cases. There are some rules where the
same pieces are not involved in the chase and these cases will never
turn up in a hash check because they don't involve repeating positions.

On the other hand, these are tournament style rules and are probably
unnecisary to implement when playing against humans in a "gentlemenly"
manner. You could simplify the rules and probably use a hash catching
scheme like you suggest. However, I believe it to be inadiquate if you
really want to implement the rules the *correct* way.

NR

Noah Roberts wrote:
Russell Reagan wrote:

"Noah Roberts" wrote in message
...


http://clubxiangqi.com/rules/



The only thing I see is:

"It can be ruled a draw if both sides repeat a sequence of moves that
return
to the same state..."

I don't see anything to indicate the necessity of anything more
complicated
than chess-like repetition detection. Maybe someone needs to point to the
specific rule(s) of interest.




I also forgot to mention a rule case where one side is a loser:

#
# 8. In "Two checks one check back", the perpetually checking side will
be ruled to lose. (See example in Diagram 5)

But once you figure out that you are in a perpetual chase/check
situation, finding out who wins is still pragmatically complex but adds
no bad overhead since we already know the game has ended. The only
problem becomes what to do when you hit such a position in a search,
should it get a mate or draw score? You could just assume it to be an
illegal position, but that might cause you to lose in cases where you
might have drawn. IMHO the answer is not easy. XiangQi's "special
rules" make life very interesting for the AI developer.

NR

http://clubxiangqi.com/rules/


The only thing I see is:

"It can be ruled a draw if both sides repeat a sequence of moves that
return
to the same state..."

I don't see anything to indicate the necessity of anything more
complicated
than chess-like repetition detection. Maybe someone needs to point to
the
specific rule(s) of interest.



Then you haven't actually read that document.
Here are some examples:
#
# 34. A protected pieces cannot be perpetually chased if its protector
has lost its effectness. (See examples in Diagrams 83, 84, and 85)
#

......
NR


That is a very nice description.

Most seasoned Xianqi players do not read rule books (some of them may read).
The is because the purpose of rule is to make the game more interesting to
play. This is the same as sport rules. Just follow common sense and you
are all right.

I think basically, the repitition rule of Xianqi is like this:

Player A, B

If player A started the repetition from which B can not get out without
losing a piece immediately or lose the game immediately (immediately is
important), then player A will be judged as lose if he does have an
alternative to stop the repitition without losing a piece or the game
immediately.

Ohterwise it is a draw.

There are exception cases but I think this is a good enough approximation.
One exception is, if A is using a pawn to force a capture repitition, it is
a draw.

james

"Russell Reagan" wrote in message news:MNsQa.57363$H17.18671@sccrnsc02...
"Noah Roberts" wrote in message
...

http://clubxiangqi.com/rules/

The only thing I see is:

"It can be ruled a draw if both sides repeat a sequence of moves that return
to the same state..."

I don't see anything to indicate the necessity of anything more complicated
than chess-like repetition detection. Maybe someone needs to point to the
specific rule(s) of interest.

Here's a pair picked randomly:

"# 17. Rook can perpetually chase a protected Cannon. If the Cannon is
protected in one move and not in another move, this chase is still
allowed. (See examples in Diagram 29, 30, and 31.)

# 18. A Rook cannot perpetually chase an unprotected Cannon even if
the Cannon is perpetually threatening to checkmate, has a check, or
has a check and a chase. A Rook also cannot perpetually chase an
unprotected Cannon even if both Cannon's reacting moves are attacking
two different pieces. (See example in in Diagram 32 to 38)"

How would you efficiently distinguish between these two cases? (And
note that this has to fit in with a bunch of other rules.)

On Fri, 11 Jul 2003 18:21:15 +0100, Neil Fernandez
wrote:

In article , JVT
writes

The best available software do
not perform any better (and often worse) on 9x9 than on 19x19 boards.

So is it basically the case that the best available go program, given
the most processing power it has ever run on, would lose every single
game against a weak club-level human opponent on a 9x9 board?

I suspect a 5-kyu human would lose once in a while to the best
programs, through tactical oversight.

-- Roy L