                           XIANG QI

   Xiang qi (象 棋) or chinese chess is a common game in the world.
Players can be seen on the streets of China and in Chinese temples in
Bangkok. The game is a game of the common people, including women. Jung
Chang describes players amongst her family in her book 'Wild Swans'
which charts the life of several generations of her family in diverse
parts of China.

   The game is played on a board, and the pieces are usually discs with
the names of the pieces written on. It is possible to make a
functioning set from a sheet of A4 paper and a blank postcard. With a
ruler and a black pen, draw the board on a sheet of paper. Next draw 32
rectangles on the postcard. An 8x4 arrangement is convenient. Draw 5
pawn symbols, 2 chariot symbols, 2 cannon symbols, 2 horse symbols, 2
elephant symbols, 2 advisor symbols and a general for each colour. Use
a red pen for the first player and any other colour for the second
player. Cut out the cardboard pieces and trim to size.

    Now you have a sort of book. You and your opponent make up the story
each time the game is played. The story contains violence but that is a
metaphore for the real world. The chess pieces started off as common
imitations of warriors and their machines in ancient warfare. Chinese
war chronicles are still taught at places like Westpoint military
academy in New England (or in Whampoa, China).

                 THE BOARD

        1  2  3  4  5  6  7  8  9
    10  .__.__.__.__.__.__.__.__.
        |  |  |  |\ | /|  |  |  |
     9  .__.__.__.__.__.__.__.__.        GREEN
        |  |  |  |/ | \|  |  |  |
     8  .__.__.__.__.__.__.__.__.
        |  |  |  |  |  |  |  |  |
     7  .__.__.__.__.__.__.__.__.
        |  |  |  |  |  |  |  |  |
     6  .__.__.__.__.__.__.__.__.
                                         RIVER
     5  .__.__.__.__.__.__.__.__.
        |  |  |  |  |  |  |  |  |
     4  .__.__.__.__.__.__.__.__.
        |  |  |  |  |  |  |  |  |
     3  .__.__.__.__.__.__.__.__.        RED
        |  |  |  |\ | /|  |  |  |
     2  .__.__.__.__.__.__.__.__.
        |  |  |  |/ | \|  |  |  |
     1  .__.__.__.__.__.__.__.__.
        9  8  7  6  5  4  3  2  1


    The game is played on grid. Pieces are placed at the intersections
of the lines, just as in WEI-QI, another Chinese game. Red has the
first move. The horizontal lines are called ranks, and the vertical
lines are called files.
The central area of the lower side is the King's Palace,
or General's office. The King and the two Advisors may not leave
the Palace. At the top of the board is the palace of the opponent's
King. The objective of the game is to capture the enemy king or to
force the king into a position where there is no legal move.

    The King must remain in the palace but also there must be no
clear line of sight to the opposing Kings. If two Kings are on the
same file, there has to be at least one piece between the two Kings.
Because of this rule it is possible to win an endgame of King and
Pawn versus King and also King plus Horse versus King.

                        THE PIECES

    The Chariot is called 'CHE' in Chinese. The traditional symbol is
like a top view of a cart with wheels going across the page. The modern
symbol looks like a cut back stealth bomber. It is the most powerful
piece on the board and moves like a rook in chess. It moves along
horizontal and vertical lines in the board, until stopped. In
English notation it is written 'R'.

    The Horse is called 'MA'. The traditional symbol is easily
recognised because it shows a stylised horses head with mane, and four
little strokes at the bottom representing four legs. The modern
character looks a bit like a tank. The horse moves like a knight in
modern chess, but it cannot jump over pieces. The rule is that the
horse moves one straight and one diagonal. If the straight portion of
the path is blocked by another piece, then the horse cannot move in
that direction.

    The Cannon is called 'PAO' in Chinese. The symbol is either a fire
radical or a stone radical followed by a couple of interlocking
combinations representing a 'BAO' sound. The piece moves around the
board like a rook, but in order to make a capture it must jump over
exactly one piece of either colour before capturing. The cannon
must have a pivot.

    The Elephant is called 'XIANG' in Chinese. Two symbols are used for
red and green pieces. The green version is a very complicated symbol
looking like a fern, or a tree radical + eye combination also
pronounced 'XIANG'. The Elephant moves two diagonal moves in either
direction, but the must stay in the first five rows of the board. An
elephant may be blocked, just like a Horse.

    Advisors are called 'SHI' and the symbol is an inverted T with a
longer horizontal line across the middle. Advisors move one space
diagonally within the King's palace (General's Office).

    Pawns are called 'BING' or 'ZU'. The symbols are either a box like
pattern on two short legs, or a plant like ideogram. They move one
point forwards, but after crossing the river they can also move
sideways. When a pawn reaches the far side of the board the pawn is not
promoted, but it can only move sideways until the end of the game.

    The King or General is called 'JIANG' or 'SHUAI'.
    It moves one square up, down, left, or right, but it must remain in
the palace. The JIANG has a bed radical followed by some up down
composite while the SHUAI ideogram looks like two vertical lines
followed by a downwards pointing three pronged fork.

    The King just moves on square along a rank or a file.

                  THE STARTING POSITION


        1  2  3  4  5  6  7  8  9
    10  r__h__e__a__k__a__e__h__r
        |  |  |  |\ | /|  |  |  |
     9  .__.__.__.__.__.__.__.__.        GREEN
        |  |  |  |/ | \|  |  |  |
     8  .__c__.__.__.__.__.__c__.
        |  |  |  |  |  |  |  |  |
     7  p__.__p__.__p__.__p__.__p
        |  |  |  |  |  |  |  |  |
     6  .__.__.__.__.__.__.__.__.
                                         RIVER
     5  .__.__.__.__.__.__.__.__.
        |  |  |  |  |  |  |  |  |
     4  P__.__P__.__P__.__P__.__P
        |  |  |  |  |  |  |  |  |
     3  .__C__.__.__.__.__.__C__.        RED
        |  |  |  |\ | /|  |  |  |
     2  .__.__.__.__.__.__.__.__.
        |  |  |  |/ | \|  |  |  |
     1  R__H__E__A__K__A__E__H__R
        9  8  7  6  5  4  3  2  1

    There are 32 pieces on 9x10=90 intersections. In international chess
there are 32 pieces on 64 squares, so there is a lower density of pieces.
Kings (K) and Advisors (A) may not leave the palace while the Elephants (E)
may not cross the river. The attacking pieces Chariots (R), Horses (H),
Cannon (C) and Pawns (P) are able to cross the river and surving pawns
may form a phalanx to crush the enemy palace. A single enemy pawn
can trap a King in a corner of the palace.

                THE RULES
    Each player makes alternate moves. Red starts.

    The two kings may not be in line on an open file.
    When a player's king may be captured, it is 'In Check'.
    No player may make a move which leaves his king in check.
    No position may be repeated, unless avoiding check.
    If the player cannot make a legal move, he loses.
    Checkmate is check with no possible escape.
    If a player can never lose by checkmate, the game is a draw.

    The repitition rule is the hardest to understand and also
it is not easy to recognise some repititions during play. Normally
the person just giving check, or chasing some other pieces must
give up the repitition. The repitition rule is ideal for computer
programs because it drastically prunes the game graph and allows
random walk style programs to find checkmate with superior material.

    The game has more open spaces (90) than chess, so it is often
impossible to defend all threatened pieces. Because Horses and
Elephants may be blocked, purely obstructive moves are important
in both attack and defence.

                XIANG QI PROGRAMS

    There are many excellent Xiang Qi programs around. Any game
program is a sort of electronic book. In the fifties and sixties
MCO or Modern Chess Openings was a 'must have' for serious Chess
players. The more educated could get the latest nuances from
Informateur with recognisable diagrams (not many) and game scores
and analyses in Russian. People could play through the games of
grandmasters, from books.

    Most chess programs incorporate an openings library. Such
electronic books have been around for about thirty years. Gary
Kasporov was keen to use computer chess databases from the start
of his own career.

    Because Xiang Qi is a Chinese game, the programs are not much
used in the West. Viet-Nam seems to be the 'foreign' country
where Xianq Qi is most popular.

                TERMINAL INTERFACE

    The Unicode terminal seems a promising environment for retro
style games with special drawing characters. Sam Sloane is a
pioner in this field. Back in the 1980s he programmed both Weiqi
and Shogi, or Japanese chess. Later in that decade I tried to
program Thai chess, using STSC's APL interpretor. It was hard
to get the program to do anything interesting.

    The Unicode terminal allows Xiang Qi to be played with ordinary
Chinese Hanzi for the pieces. SCIM or Smart Chinese Input Method
along with Open Office allow programs to incorprate more or
less Chinese content in ordinary DATA style statements.

    The Xiang Qi program has played several thousand games against
itself since development started. The earliest Random Walk style
programs were very fast and extremely stupid. Later algorithms
tend to make games slower.

    The main runfile is xqsh. xq.d4f contains the Xiang Qi engine.
files with suffix .xq are games.

    The program regularly crashes. The games are often protracted
because as written so far the algorithm selects endless rook checks
and futile cannon moves. Moves are selected according to where
pieces can go, with a simple calculation based on legal moves
in a position. This misses points from the 'line of fire' of
a cannon which are not legal moves when a square is empty. This
also means that the King is blind to cannon fire and sometimes
walks into a rook check to escape a harmless cannon. In the
endgame the cannon has many useless moves, although a cannon
may be useful sometimes to avoid loss of the game by trapped king.

    The program plays automatic games, but it's quite flakey.
Long games of over 100 moves are shortened by a resignation
routine. There is a move evaluation function bassed on aggression
point scoring. The computer will take higher value piece which is not
defended.

    Adding checkmate detection shortened the games. Many synthetic
games have early double cannon checkmates on the central file.
The next thing is to detect checkmate from several moves back and
this requires some sort of recursive graph enumeration algorithm.

    The recursive algorithm should mark vertices to avoid repititions
in search paths. A limit should be set on positions to be examined.

    tree.df detects illegal position, check, no moves, checkmate,
checkmate in two. This information is for the agressor. No
defence. Detecting checkmate in two slows down the program.

    The new 'GAME' routine allows human and different programs.

    Human       Input moves with mouse.
    Zombie      Always takes. -> Power function.
    Moron       Uses tree.df
    Select      Crashes system too often -> phase out

    H<-XQ_PLAY "HZ" gives Human (Red) versus Zombie (Black)
and H<-XQ_PLAY "MM" is Moron versus Moron. If you want to try
HH, it is better to make a board with a postcard and paper, and
use that.

    Moron makes a random walk in the game graph until a nearby
terminal node is seen, and then takes the path towards checkmate.
The checkmate in two is not 100% working. Sometimes it takes
perpetual check (illegal). It is tricky to decide in which order
to do the tests.

    Tree leaf routine still needed work. Use trace output from
'Moron' to fix errors.

                       NEWS FLASH
    When recent traffic jams clogged up some of China's modern
highway many waiting were seen to be playing cards or chess
to while away the time. Traffic jams on a large scale happened
in Germany during the 1960s in the Ruhr area, and it is quite
ironic how parts of modern China seem reminiscent of Germany
as much as any Oriental nation.

                        ZOMBIE

    Zombie now has checkmate testing and a slightly better survival
algorithm. Survival means being able to avoid loss until a chance
comes... a form of opportunism. The calculation of control of
the board cannot work as it stands. Control of a square is not
the same as being able to make a legal move to that square.
This naive calculation allows a rook or cannon to run away from
a rook and think it escaped.

                        GAME TRANSCRIPTS
    The old style notation (C2=5 H2+3 etc.) appears in several
documents. This notation is ambiguous, and the .pdf files using
this scheme have many errors. Computer generated transcripts
simply list the moves as 5-byte strings. Axxyy where A is a
letter designating the piece, and xxyy stand for the source and
destintion of the move. Rows and columns are labeled from 0-9
and 0-8 (zero origin indexing), so xx and yy are just pairs of
decimal digits.

   Other tokens should be in transcripts, rather like .sgf format
for go games. These tokens have square brackets.

   G[RB]        Game   RB=red program, black program
   RE[dd]       Result 10 00 or 01
   MV[nn]       Number of moves.

   The 'Game' tag contains the pairing given to the XQ_PLAY function.
The 'Result' tag contains R+, B+ or R=B for red win, loss or draw.
Analysis of matches between different algorithms gives a clue as
to whether adding new code is making a stronger program.

                            XQ_SHI
   Sun Sep 12 08:53:28 BST 2010
   A new routine is needed to deal with captures. This is hard coded
in C, just like XQ_MOVES. XQ_SHI answers the question posed as:-

   'If Red moves a piece from a to b, can that piece be captured ?'

   Z<-XY XQ_SHI G
   Here XY is an Mx2 matrix of possible moves, G is the board position
and Z is an (M,1) column vector of numbers V[i] with V=0 if a piece
cannot be captured at once.

   Z<-X XQ_SHI G
   X is a column vector of points. Z is a numeric vector with 0
indicating whether the square X[i] is in range of a black piece.
If the left arguement is absent, it is assumed to be a pointer to
the red king position and a result of 0 indicates a legal position.

   Z<-XQ_SHI G
   Test if Red has a legal position.

                PINS AND BLOCKING MOVES
   Mon Oct  4 02:45:59 BST 2010.
   Side effects of moves are not handled correctly.










