I was talking to someone the other day about the open source project Sunfish, which is a chess engine written with only 111 lines of Python code, which is not weak in itself. Almost immediately after our chat, I became interested in recreating Sunfish on Chinese chess, so I did the same. In fact, the code went incredibly well, porting the algorithm in just two days in my spare time, Output a implementation of Chinese chess engines with 124 lines of code elephantfish (making address https://github.com/bupticybee/elephantfish).

As for chess, I had no expectations for such a simplified Chinese chess engine. I played elephantfish and ELEPHantfish in two games, and I didn’t play chess for so long that I accidentally got caught and lost in both games. I also played Elephantfish and chess boy wizard on fool difficulty. The result is that elephantfish’s thinking time is 1 second, but when elephantfish’s thinking time expands to 5 seconds, they can finally play. (But at this point, the chess wizard’s thinking depth is 2, and elephantfish’s thinking depth is 7-9, so there is still a lot of room for improvement in the situation evaluation function.)

In fact, elephantfish has been able to complete elephantfish in such a short time for several reasons:

  1. Sunfish itself is written very generally-many data structures can be used with Chinese chess with very little change, some with very few changes, notably the key module Searcher code used for porting to Chinese chess was left unchanged.
  2. There are some excellent open source algorithms in the field of Chinese chess, such as Xiangyan, whose component force value table is very valuable for reference. In fact, I directly use part of xiangyan’s component force value table in the program.
  3. Xqbase provides a series of explanations and translations of common algorithms that make it easy for me to understand Sunfish’s logic.

The goal of this project is to provide a chess engine similar to Sunfish’s Codebase, so that even students who don’t study this field can easily and quickly do some experiments by hand. Or at least it only takes a little time for interested students to fully understand the data structures and algorithms required for a simple Chinese chess engine.

To illustrate how simple Elephantfish really is, let’s take a look at the data structures and algorithms elephantfish uses.

Chinese chess board representation

In elephantfish, the Chinese chess board is represented as a large string:

initial = (
    ' \n' 
    ' \n' 
    ' \n' 
    ' rnbqkqbnr \n' 
    '... \n' 
    ' .c..... c. \n' 
    ' p.p.p.p.p \n' 
    '... \n' 
    '... \n' 
    ' P.P.P.P.P \n' 
    ' .C..... C. \n' 
    '... \n' 
    ' RNBQKQBNR \n' 
    ' \n' 
    ' \n' 
    ' \n'
)
Copy the code

This is a string of length 16 * 16 = 256, with each position of the element corresponding to the empty space on the piece or board:

P - > soldier C - R - > > gun car N - > horse - > like Q - > B and K - > handsome. - > empty - > board outsideCopy the code

It is also easy to make moves on a large string board like this. For example, if we need to make a move of gun two draw five, we simply set the string element for the position of the second move to ‘.’ and replace the element for the position of the gun’s landing point with the gun.

Motion generator

The move generator is used to generate all the possible actions of “our side” in a situation. For example, in the opening case, the Red side can move the gun two even five, the horse two into three,… And so on other steps, because we need to use a search algorithm to traverse these possible actions, the method generator is necessary, but also a very key component, if the method generator generated by the problem, the whole search process is wrong.

Actual if we do not consider efficiency, a method of the generator than most of us think of simple, although there are some special rules in Chinese chess need special handling (such as horse leg, gun rack, general (pictured), and other pieces of activity rules are very simple, our the whole code generator with only more than 30 lines (remove comments) :

class Position(namedtuple('Position'.'board score')):
    """ A state of a chess game board -- a 256 char representation of the board score -- the board evaluation """
    def gen_moves(self):
        # For each of our pieces, iterate through each possible 'ray' of moves,
        # as defined in the 'directions' map. The rays are broken e.g. by
        # captures or immediately in case of pieces such as knights.
        for i, p in enumerate(self.board):
            if not p.isupper(): continue
            if p == 'K':
                # Judgment of general's face
                for scanpos in range(i - 16,A9,- 16) :if self.board[scanpos] == 'k':
                        yield (i,scanpos)
                    elifself.board[scanpos] ! ='. ':
                        break
            if p == 'C':
                The gun moves in a special way, get to the front to judge
                for d in directions[p]:
                    cfoot = 0
                    for j in count(i+d, d):
                        q = self.board[j]
                        if q.isspace():break
                        if cfoot == 0 and q == '. ':yield (i,j)
                        elif cfoot == 0 andq ! ='. ':cfoot += 1
                        elif cfoot == 1 and q.islower(): yield (i,j);break
                        elif cfoot == 1 and q.isupper(): break;
                continue
            for d in directions[p]:
                for j in count(i+d, d):
                    q = self.board[j]
                    # Stay inside the board, and off friendly pieces
                    if q.isspace() or q.isupper(): break
                    Only pawns crossing the river can walk sideways
                    if p == 'P' and d in (E, W) and i > 128: break
                    # j&15 is equivalent to j % 16 but faster, this line of code means that both shi and Shuai can only play inside the nine grids
                    elif p in ('Q'.'K') and (j < 160 or j & 15 > 8 or j & 15 < 6) :break
                    Elephants cannot cross the river
                    elif p == 'B' and j < 128: break
                    elif p == 'N':
                        n_diff_x = (j - i) & 15
                        if n_diff_x == 14 or n_diff_x == 2:
                            # NEE,SEE,NWW,SWW these four horse moves will enter this branch to determine the horse's leg
                            if self.board[i + (1 if n_diff_x == 2 else - 1)] != '. ': break
                        else:
                            # NNE,SSE,NNW,SSW The moves of these four horses will enter this branch to judge the legs
                            if j > i and self.board[i + 16] != '. ': break
                            elif j < i and self.board[i - 16] != '. ': break
                    # The eye cannot have children
                    elif p == 'B' and self.board[i + d / 2] != '. ':break
                    # Move it
                    yield (i, j)
                    # Stop crawlers from sliding, and sliding after captures
                    if p in 'PNBQK' or q.islower(): break
Copy the code

It may seem a little out of the blue to post a piece of code, but the purpose of Posting the code generator here is to make it clear that it takes only a very short piece of code to generate the code, which makes up nearly half of the 124 lines.

Search strategy

The code of the search strategy is also very short (less than 100 lines), but it is not easy to read compared to the algorithm generator. Elephantfish uses MTD(F) algorithm to search. If you want to understand this algorithm, take an extra hour or two to read the following articles in Basic Techniques of Chess Programs. You’ll find that the strategy search code in Sunfish/Elephantfish is almost exactly the same as the pseudo-code in these articles.

It is recommended to read the following articles to gain some knowledge of search strategies:

  1. Basic Search Method — “minimum-maximum” search (B.Moreland)
  2. Basic Search method — Alpha-beta search (B.Moreland)
  3. Basic Search Method — Iterative Deepening (B.Moreland)
  4. Basic Search Method — Transposition table (B.Moreland)
  5. Advanced Search Methods – Introduction (I)(D.Epstein)
  6. Advanced Search Methods – Introduction (II)(D.Epstein)
  7. Advanced Search Methods — Static Search (B.Moreland)
  8. Advanced Search Method — Null clipping (B.Moreland)
  9. Advanced Search Method — Major Variation Search (B.Moreland)

Afterword.

Generally speaking, Elephantfish’s implementation is very simple, using a lot of chess AI tricks. Elephantfish is not very good at chess, but it can beat some weak humans (like me). I think, or I hope, that Elephantfish can be a “benchmark code” and get some people interested in the chess engine for this project, and even do some of elephantfish’s own experiments. I’m going to provide some scripts for different AI to play against each other. Let you can easily do some experiments and quickly see the effect.