CIL Toolkit: code snippets: move generation

Discussion of chess software programming and technical issues.

Moderator: Ras

User avatar
sje
Posts: 4675
Joined: Mon Mar 13, 2006 7:43 pm

CIL Toolkit: code snippets: UCI/xboard command processors

Post by sje »

The new CIL Toolkit's command processor main lines for the UCI and xboard interfaces are almost the same:

Code: Select all

;;; Universal Chess Interface command processor

(defun uci (&rest my-args)
  "Universal Chess Interface command processor for the Chess In Lisp Toolkit."
  (let ((cpc (mk-cpc cpid-uci as-uci-cmd-vec my-args)))
    (uci-init cpc)
    (dowhile (not (cpc-is-done cpc))
      (command-line-cpc (read-line (cpc-stin cpc) nil nil) cpc)
      (unless (or (cpc-is-done cpc) (cpc-is-pass cpc))
        (if (cpc-cmdord cpc)
          (eval (list (svref uci-dispatch-vec (cpc-cmdord cpc)) cpc))
          (warn "Unrecognized input")))
      (finish-output (cpc-stout cpc)))
    (uci-term cpc))
  (values))

Code: Select all

;;; xboard command processor

(defun xboard (&rest my-args)
  "The xboard command processor for the Chess In Lisp Toolkit."
  (let ((cpc (mk-cpc cpid-xboard as-xboard-cmd-vec my-args)))
    (xboard-init cpc)
    (dowhile (not (cpc-is-done cpc))
      (command-line-cpc (read-line (cpc-stin cpc) nil nil) cpc)
      (unless (or (cpc-is-done cpc) (cpc-is-pass cpc))
        (if (cpc-cmdord cpc)
          (eval (list (svref xboard-dispatch-vec (cpc-cmdord cpc)) cpc))
          (warn "Unrecognized input")))
      (finish-output (cpc-stout cpc)))
    (xboard-term cpc))
  (values))
As mentioned earlier, these don't have either prompting or banners for greetings/goodbyes. But both do have a call to the finish-output routine that flushes the output stream just in case.

All three command processors will exit on an EOF, and all three will ignore an input consisting only of whitespace characters. Each processor also has a defined exit or quit command that will cause an exit.

When running the toolkit with the console interactive command processor, a user types:

Code: Select all

(icp)
Not too complicated, eh?

Similar invocations are used for UCI and xboard instances. All calls allow for optional parameters that appear on the program invocation command line; at the moment I think these will be used for specifying log and dribble files.

The exact details of topmost level invocation are dependent upon the Lisp in use. Some configurations might need start up files or some other assistance. Others might be able to call a compiled file directly.
David Hotham

Re: CIL Toolkit: code snippets: UCI/xboard command processor

Post by David Hotham »

What is this thread for, please?

I guess that you are trying to stir up some enthusiasm for Lisp in this forum. If so may I respectfully suggest that while the attempt has been valiant, it's time to let it go - I believe you've now made over 100 posts and only managed to provoke a single reply...
User avatar
sje
Posts: 4675
Joined: Mon Mar 13, 2006 7:43 pm

Re: CIL Toolkit: code snippets: UCI/xboard command processor

Post by sje »

David Hotham wrote:What is this thread for, please?

I guess that you are trying to stir up some enthusiasm for Lisp in this forum. If so may I respectfully suggest that while the attempt has been valiant, it's time to let it go - I believe you've now made over 100 posts and only managed to provoke a single reply...
Let's see ...

32,300 page views

That's four times the next highest count on the current index page.

Obviously, there is some interest, plus it's better to keep all the related information under the same topic. I agree that not all are interested and I won't mind if some don't read the thread.
User avatar
sje
Posts: 4675
Joined: Mon Mar 13, 2006 7:43 pm

CIL Toolkit: code snippets: speed report

Post by sje »

So, how fast does this thing run?

Movepath enumeration to ply four from the initial array produces the expected 197,281 path count. The benchmark code for this runs a full generate / execute / retract cycle on each interior and terminal node. Furthermore, at each node a full bitboard database, the material balance, a color/piece census, the pin/frozen bitboards, the target tracker, and other fully updated structures are presented.

With a single thread active on my 2.66 GHz machine, the clisp bytecode interpreter:

Code: Select all

Total path count for depth four: 197281
F/P: 8.449417 KHz / 118.351364 usec
With a single thread active on my 2.66 GHz machine, the CMU CL compiler:

Code: Select all

Total path count for depth four: 197281
F/P: 57.017628 KHz / 17.538435 usec
The numbers vary slightly from test to otherwise identical test due to randomness in memory/object conditions, but the rates are surprisingly similar for different positions.
User avatar
sje
Posts: 4675
Joined: Mon Mar 13, 2006 7:43 pm

CIL Toolkit: code snippets: en passant playability

Post by sje »

One of the challenges of writing a move generator with legal-only output is handling en passant captures. One way of doing this is to actually execute, test, and retract a proposed en passant capture within the generator routine. Although simple, this cycle approach is slow and less than elegant.

Until today, the new CIL Toolkit used the en passant capture execute/test/retract cycle technique. But I was annoyed at having this exception to the otherwise clean generation code, so I wrote a lower level routine that calculated en passant legality status without the program having to perform the alternative time consuming full update cycle.

Only the bitboard database is accessed here; all the other structures that are normally saved/updated/restored are left untouched.

Code: Select all

(defun is-en-passant-move-playable? (my-ep-move my-pos)
  "Return t if the en passant move does not leave the moving color's king in check."
  (let*
    (
      (result      nil)
      (act-color  (pos-act-color my-pos))
      (pas-color  (pos-pas-color my-pos))
      (bbdb       (pos-bbdb      my-pos))
      (fr-sq      (move-fr-sq  my-ep-move))
      (to-sq      (move-to-sq  my-ep-move))
      (fr-man     (move-fr-man my-ep-move))
      (victim-sq  (+ to-sq (the fixnum (svref pawn-retreat-delta-vec act-color))))
      (victim-man (synth-man pas-color piece-pawn))
    )
    (del-man-bbdb victim-man victim-sq bbdb)
    (move-man-bbdb fr-man fr-sq to-sq bbdb)
    (unless (in-check? my-pos)
      (setf result t))
    (move-man-bbdb fr-man to-sq fr-sq bbdb)
    (add-man-bbdb victim-man victim-sq bbdb)
    result))
A similar route called only by the checking move generator does the above plus tests for a check as well.

Is it faster? Certainly so; the only real work being done is attack cut and attack propagation through the three changed squares. And that's the only real work needed to determine legality and checking status.

Does it make a difference? Yes, but not very much because en passant captures are relatively rare. The real world overall speed improvement figure is probably less than one tenth of one percent.
User avatar
sje
Posts: 4675
Joined: Mon Mar 13, 2006 7:43 pm

Re: CIL Toolkit: code snippets: speed report

Post by sje »

Here are some more benchmark results, this time counting distinct movepaths to depth six. The counting of the last ply is done at the precursor ply instead of executing each terminal node separately. No transposition tables are in use.

With a single thread active on my 2.66 GHz machine, the clisp bytecode interpreter:

Code: Select all

Total path count for depth six: 119060324
F/P: 139.3924 KHz / 7.1739926 usec
With a single thread active on my 2.66 GHz machine, the CMU CL compiler:

Code: Select all

Total path count for depth six: 119060324
F/P: 922.0905 KHz / 1.0844923 usec
jfranrivera

Re: CIL Toolkit: code snippets: UCI/xboard command processor

Post by jfranrivera »

This a long work, please, do not interrupt this thread.
User avatar
michiguel
Posts: 6401
Joined: Thu Mar 09, 2006 8:30 pm
Location: Chicago, Illinois, USA

Re: CIL Toolkit: code snippets: en passant playability

Post by michiguel »

sje wrote:One of the challenges of writing a move generator with legal-only output is handling en passant captures. One way of doing this is to actually execute, test, and retract a proposed en passant capture within the generator routine. Although simple, this cycle approach is slow and less than elegant.

Until today, the new CIL Toolkit used the en passant capture execute/test/retract cycle technique. But I was annoyed at having this exception to the otherwise clean generation code, so I wrote a lower level routine that calculated en passant legality status without the program having to perform the alternative time consuming full update cycle.

Only the bitboard database is accessed here; all the other structures that are normally saved/updated/restored are left untouched.

Code: Select all

(defun is-en-passant-move-playable? (my-ep-move my-pos)
  "Return t if the en passant move does not leave the moving color's king in check."
  (let*
    (
      (result      nil)
      (act-color  (pos-act-color my-pos))
      (pas-color  (pos-pas-color my-pos))
      (bbdb       (pos-bbdb      my-pos))
      (fr-sq      (move-fr-sq  my-ep-move))
      (to-sq      (move-to-sq  my-ep-move))
      (fr-man     (move-fr-man my-ep-move))
      (victim-sq  (+ to-sq (the fixnum (svref pawn-retreat-delta-vec act-color))))
      (victim-man (synth-man pas-color piece-pawn))
    )
    (del-man-bbdb victim-man victim-sq bbdb)
    (move-man-bbdb fr-man fr-sq to-sq bbdb)
    (unless (in-check? my-pos)
      (setf result t))
    (move-man-bbdb fr-man to-sq fr-sq bbdb)
    (add-man-bbdb victim-man victim-sq bbdb)
    result))
A similar route called only by the checking move generator does the above plus tests for a check as well.

Is it faster? Certainly so; the only real work being done is attack cut and attack propagation through the three changed squares. And that's the only real work needed to determine legality and checking status.

Does it make a difference? Yes, but not very much because en passant captures are relatively rare. The real world overall speed improvement figure is probably less than one tenth of one percent.
I do not believe slow en passant code is a problem. It is very rarely executed. It is better to have the most compact and readable code posible at this point. It does not slow down the search at all.

Miguel
User avatar
sje
Posts: 4675
Joined: Mon Mar 13, 2006 7:43 pm

Re: CIL Toolkit: code snippets: en passant playability

Post by sje »

michiguel wrote:I do not believe slow en passant code is a problem. It is very rarely executed. It is better to have the most compact and readable code posible at this point. It does not slow down the search at all.
It's not the relative speed that's an issue here. Nor is it the compactness of code, as compactness should never be a goal but rather a natural side effect of good engineering. (Exception: very small embedded systems.)

What is important is program correctness and the internal design firewalls that reduce bug magnet dependencies.

First, the bitboard database routines were designed from the start for minimal dependencies. They do not rely on any board variables or accessing routines. They do not rely on generation, nor on execute/retract, the tracker, the hashes, the census, nor on any the program's data structures (outside of the seven elements of each bitboard database instance). That's what's enabled the en passant code above to be written without any concern about all of the non-bitboard database items that change with execute/retract. Having no global variables helps with this as well.

Second, the above code can be used at a model for other functions. An example: a search that can find combinations directly might like to see what a position looks like if some opponent piece can be decoyed and if the decoy is worth a sacrifice. To help with this, a limited update routine like the above could be used to temporarily remove an opponent piece to check some condition.
User avatar
sje
Posts: 4675
Joined: Mon Mar 13, 2006 7:43 pm

CIL Toolkit: code snippets: UCI move notation generation

Post by sje »

More simple stuff:

Code: Select all

;;; UCI algebraic notation encoding

(defun encode-uan (my-stream my-move)
  "Encode a move in UCI algebraic notation; hopefully they will switch to SAN someday."
  (if (is-move-null? my-move)
    (put-string my-stream "0000")
    (progn
      (put-string my-stream (svref as-sq-vec (move-fr-sq my-move)))
      (put-string my-stream (svref as-sq-vec (move-to-sq my-move)))
      (when (is-move-promotion? my-move)
        (put-char my-stream
          (svref ac-piece-vec (svref mc-msc-to-piece-vec (move-msc my-move)))))))
  (values))

(defun uan-string (my-move)
  "Encode a UCI algebraic notation move on a string."
  (let ((result nil) (stream (make-string-output-stream)))
    (encode-uan stream my-move)
    (setf result (get-output-stream-string stream))
    (close stream)
  result))