;;; chess-polyglot.el --- Polyglot chess book access for Emacs  -*- lexical-binding: t; -*-

;; Copyright (C) 2014  Free Software Foundation, Inc.

;; Author: Mario Lang <mlang@delysid.org>
;; Keywords: data, games

;; This program is free software; you can redistribute it and/or modify
;; it under the terms of the GNU General Public License as published by
;; the Free Software Foundation, either version 3 of the License, or
;; (at your option) any later version.

;; This program is distributed in the hope that it will be useful,
;; but WITHOUT ANY WARRANTY; without even the implied warranty of
;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
;; GNU General Public License for more details.

;; You should have received a copy of the GNU General Public License
;; along with this program.  If not, see <http://www.gnu.org/licenses/>.

;;; Commentary:

;; The polyglot book format uses a 64 bit zorbist hash to encode positions.
;; Since 2 bits are used for tagging in Emacs Lisp, 64 bit values can not be
;; represented as fixnums.  So we split the 64 bit value up into equally sized
;; chunks (16 bit fixnums).  781 predefined zorbist hash keys are
;; stored as constants (see `chess-polyglot-zorbist-keys') and used to calculate
;; zorbist hashes from positions.

;; Binary search is employed to quickly find all the moves from a certain
;; position.  These moves are converted to proper chess ply objects (see
;; chess-ply.el).

;; The most interesting functions provided by this file are
;; `chess-polyglot-book-open', `chess-polyglot-book-plies',
;; `chess-polyglot-book-ply' and `chess-polyglot-book-close'.

;; For a detailed description of the polyglot book format, see
;; <URL:http://hardy.uhasselt.be/Toga/book_format.html> or
;; <URL:http://hgm.nubati.net/book_format.html>.

;;; Code:

(require 'cl-lib)
(require 'chess-ply)
(require 'chess-pos)

(defgroup chess-polyglot ()
  "Polyglot opening book support."
  :group 'chess)

(defcustom chess-polyglot-book-strength 1.0
  "Influence random distribution when picking a ply from the book.

A value above 1.0 means to prefer known good moves while a value below
1.0 means to penalize known good moves.  0.0 will force uniform
distribution of move weights.  For reasons of numerical overflow,
this should be strictly less than 4.0."
  :group 'chess-polyglot
  :type '(float :match (lambda (widget value) (and (>= value 0) (< value 4)))))

(defvar chess-polyglot-book nil
  "The default polyglot book object.

This is automatically set if `chess-polyglot-book-file' points to a valid
polyglot book file.")

(defsubst chess-polyglot-read-octets (n)
  "Read N octets from the current buffer and advance point."
  (let ((val 0))
    (dotimes (_ n (progn (cl-assert (<= val most-positive-fixnum)) val))
      (setq val (logior (lsh val 8)
			(progn (forward-char 1) (preceding-char)))))))

(defsubst chess-polyglot-read-key ()
  "Read a polyglot position hash (a 64 bit value) from the current buffer.
A list with 16-bit values (most significant first) is returned."
  (list (chess-polyglot-read-octets 2) (chess-polyglot-read-octets 2)
	(chess-polyglot-read-octets 2) (chess-polyglot-read-octets 2)))

(defun chess-polyglot-read-move ()
  "Read a polyglot move (a 32 bit value) from the current buffer.
The result is a list of the form (FROM-INDEX TO-INDEX PROMOTION WEIGHT)."
  (let ((mask (chess-polyglot-read-octets 2)))
    (pcase (let (r)
	     (dotimes (_ 5 r)
	       (push (logand mask 7) r)
	       (setq mask (ash mask -3))))
      (`(,promotion ,from-rank ,from-file ,to-rank ,to-file)
       (list (chess-rf-to-index (- 7 from-rank) from-file)
	     (chess-rf-to-index (- 7 to-rank) to-file)
	     (nth promotion '(nil ?N ?B ?R ?Q))
	     (chess-polyglot-read-octets 2))))))

(defun chess-polyglot-move-to-ply (position from to promotion weight)
  "Convert a polyglot move for POSITION to a ply.
FROM and TO are integers indicating the square indices.
PROMOTION, if non-nil, indicates the piece to promote to.
WEIGHT (an integer) is the relative weight of the move."
  (cl-check-type position chess-pos)
  (cl-check-type from (integer 0 63))
  (cl-check-type to (integer 0 63))
  (cl-check-type promotion (member nil ?N ?B ?R ?Q))
  (cl-check-type weight integer)
  (let* ((color (chess-pos-side-to-move position))
	 (ply (apply #'chess-ply-create position nil
		     (if (and (= from (chess-rf-to-index (if color 7 0) 4))
			      (= from (chess-pos-king-index position color))
			      (= (chess-index-rank from) (chess-index-rank to))
			      (memq (chess-index-file to) '(0 7)))
			 (chess-ply-castling-changes
			  position (= (chess-index-file to) 0))
		       (nconc (list from to)
			      (when promotion (list :promote promotion)))))))
    (chess-ply-set-keyword ply :polyglot-book-weight weight)
    ply))

(defsubst chess-polyglot-skip-learn ()
  "Skip the (unused) 32 bit learn value."
  (forward-char 4))

(defconst chess-polyglot-record-size 16
  "The size (in bytes) of a polyglot book entry.")

(defsubst chess-polyglot-goto-record (record)
  "Set point to the beginning of RECORD, a number starting from 0."
  (goto-char (1+ (* record chess-polyglot-record-size))))

(defsubst chess-polyglot-forward-record (n)
  "Move point N book records forward (backward if N is negative).
On reaching end or beginning of buffer, stop and signal error."
  (forward-char (* n chess-polyglot-record-size)))

(defsubst chess-polyglot-key-<= (lhs rhs)
  "Non-nil if the polyglot key LHS is less than or equal to RHS."
  (while (and lhs rhs (= (car lhs) (car rhs)))
    (setq lhs (cdr lhs) rhs (cdr rhs)))
  (or (and (null lhs) (null rhs)) (<= (car lhs) (car rhs))))

(defun chess-polyglot-read-moves (key)
  "Read all moves associated with KEY from the current buffer."
  (cl-assert (zerop (% (buffer-size) chess-polyglot-record-size)))
  ;; Find leftmost entry.
  (let ((left 0) (right (1- (/ (buffer-size) chess-polyglot-record-size))))
    (while (< left right)
      (let ((middle (/ (+ left right) 2)))
	(if (chess-polyglot-key-<= key (progn (chess-polyglot-goto-record middle)
					      (chess-polyglot-read-key)))
	    (setq right middle)
	  (setq left (1+ middle)))))
    (cl-assert (= left right))
    (chess-polyglot-goto-record left))
  ;; Read all entries with equal keys.
  (let ((moves ()))
    (while (equal key (chess-polyglot-read-key))
      (setq moves (nconc moves (list (chess-polyglot-read-move))))
      (chess-polyglot-skip-learn))
    moves))

(defconst chess-polyglot-zorbist-keys
  [(40249 9342 13175 27969) (10999 14720 1450 42439) (17627 336 9314 13639)
   (39957 63294 25255 27362) (30083 17509 18588 3209) (12944 44090 8240 447)
   (4027 44319 24836 8825) (59450 37007 62203 24778) (3454 30301 22645 23568)
   (6664 14370 52911 57389) (38405 54768 57950 50096) (53281 65372 53562 11989)
   (16573 61789 19047 11826) (275 21780 28629 25493) (23988 33568 18163 55781)
   (9119 35629 32759 6604) (1489 41390 34228 39585) (26527 33935 28303 51569)
   (29769 48127 32799 60683) (32017 52657 50103 44528) (33479 28830 30750 47052)
   (62241 36636 38160 30828) (13076 30963 44881 48102) (19379 36325 59169 37955)
   (43620 40046 48381 20732) (36285 39075 21167 54283) (34770 1867 33239 37399)
   (6643 51025 54249 10977) (46251 12528 25265 39615) (31493 172 16900 31428)
   (51525 11432 6665 55389) (9386 27729 19874 29952) (19615 13378 29953 46151)
   (5286 36823 15505 2113) (42779 39811 17948 48531) (840 35733 45297 34063)
   (25467 11060 65427 49216) (2513 48282 15833 2708) (13685 26243 13473 56635)
   (29534 11159 42180 23075) (6258 28784 61885 16395) (8139 44242 22975 743)
   (54032 42946 52891 25941) (49048 16352 65117 33348) (40820 53583 29780 43044)
   (20971 56394 47546 12341) (23682 50437 56218 45306) (64759 65162 13360 45633)
   (12883 42793 47546 15838) (35956 50024 2075 12405) (47548 27783 5756 13287)
   (32500 36651 33538 20000) (4565 1492 50001 48511) (25960 64681 11382 41539)
   (19936 45300 3890 42936) (38614 37702 3267 32349) (17122 16587 25448 40751)
   (27947 56538 58001 38497) (17032 2818 14052 55633) (24335 19032 38935 7094)
   (14840 37109 31225 12168) (37829 46580 29526 14475) (25564 13725 36131 7032)
   (60438 51850 60056 44406) (21333 63744 49832 11719) (2043 40837 23193 28994)
   (20627 16762 43175 60766) (31691 50061 41562 32572) (6652 35446 36084 46804)
   (25466 30592 57039 49369) (33353 42106 60942 16887) (31149 26965 487 53736)
   (5292 47860 30589 22390) (61765 46782 52446 41365) (55999 10952 8215 21244)
   (9411 51533 63944 54262) (47982 10532 61497 4842) (3298 27659 38345 32985)
   (42140 53554 49087 31940) (59805 26154 62500 14649) (10214 44408 37142 23615)
   (34101 61504 47476 20465) (21683 62714 24384 55411) (29361 11314 4735 60715)
   (61077 19772 31553 8007) (39557 44176 39460 60065) (28844 19673 61519 8693)
   (63928 40254 39328 30146) (34739 58034 46537 1969) (41830 58808 50511 18616)
   (44618 37702 52287 31986) (6432 49229 18214 31677) (34751 710 46238 10985)
   (2338 14252 9087 14425) (65287 63054 63725 5328) (36328 56489 61500 50510)
   (39958 13094 19892 40073) (46066 11325 2827 14573) (14606 24500 19713 5195)
   (23550 42420 28967 26857) (7696 12945 8103 35204) (39540 44217 25831 36019)
   (20352 63392 13786 64260) (25348 53402 2871 14532) (8561 58950 33538 14856)
   (23451 25579 40175 63500) (20586 44276 35208 37698) (6273 45001 41895 470)
   (25859 2052 16501 1604) (57299 38195 40155 62631) (61330 32188 61452 8434)
   (31538 63441 57398 33004) (47613 30240 59185 25155) (1447 59557 32185 7031)
   (46472 40046 5475 2677) (19061 2569 52885 29687) (53062 19692 35226 12170)
   (62776 25500 59141 47140) (15481 41215 21888 61311) (60902 51327 33911 24733)
   (31134 33264 23497 16177) (34387 27532 62274 35468) (38871 14156 24584 31603)
   (41542 25468 65330 34098) (1087 51942 3264 60320) (37390 17557 13789 13726)
   (28907 2363 5554 37068) (29601 37401 5721 7357) (22083 27807 57761 43661)
   (61356 19312 25403 36737) (47905 22424 54365 63407) (17906 66 62031 5992)
   (37647 33012 59627 29794) (65383 4863 53207 24225) (44642 16342 29800 43632)
   (56620 23496 19400 55548) (32493 4621 21711 11737) (8958 21588 278 24348)
   (51480 233 36793 39209) (32907 54926 27329 869) (57028 26644 23414 1526)
   (7149 58275 44789 13058) (17235 38403 54981 22018) (43670 39772 26908 52090)
   (43128 13011 37615 61014) (26004 11387 15486 4526) (57042 54835 51920 1270)
   (8688 34160 62496 58725) (46101 37773 32169 20028) (37304 23013 40651 25424)
   (4303 62259 57581 32842) (10414 53568 48651 47069) (50636 7561 29263 42070)
   (22088 63104 61722 10049) (11557 20585 61623 55987) (39877 41870 63273 43988)
   (61231 1347 2294 41660) (44832 17141 52316 10328) (18436 4794 47093 48682)
   (44787 44874 22077 65091) (6575 58778 58449 18815) (21081 14339 57329 59456)
   (62704 30438 24364 59120) (4407 38437 29821 23283) (48357 53796 34434 49429)
   (40356 9277 59446 39247) (1647 28851 16352 36887) (19908 56856 39783 6684)
   (20739 39607 28964 22467) (49274 16256 49951 46260) (46190 59845 58954 28284)
   (45953 39490 44006 7303) (8608 1939 14930 10784) (11761 28534 5528 43599)
   (30268 18963 29107 26877) (63379 50279 736 34464) (55080 36353 10987 36145)
   (56883 27178 19393 50251) (3062 37555 36103 40739) (11360 19066 6003 9907)
   (18512 59198 1003 24676) (53188 18417 58684 36379) (45148 41973 25638 36249)
   (39649 33480 48276 29928) (42236 19412 64597 22730) (59221 6029 22780 20086)
   (27065 32177 42176 15870) (63925 47044 44230 31894) (64618 33494 19334 22011)
   (40040 19638 50386 17431) (36553 32041 5957 28368) (26371 57245 10532 59774)
   (50503 62846 17063 17486) (30947 30276 59338 53918) (65178 17641 13871 1530)
   (2237 13772 14387 26133) (37653 58859 14866 39630) (37894 7047 7684 57205)
   (57117 40861 30795 40976) (15290 22454 34929 46493) (53943 44526 57041 63295)
   (63394 21976 15299 29688) (55284 62020 35852 60289) (55643 59532 53776 65447)
   (13167 21240 65351 10471) (42816 18906 49938 44145) (41718 7094 58423 64949)
   (20266 23728 32618 13747) (34771 32957 42431 30809) (5817 63456 27717 14881)
   (31650 18508 35343 54606) (62374 30922 55714 58252) (14768 49021 56899 31650)
   (64687 21953 49034 17444) (6396 63104 22335 42388) (19461 25528 40777 23235)
   (16608 34707 6656 37645) (36095 43329 11958 17089) (26826 14597 12897 5791)
   (31262 59751 53877 31202) (40221 24805 1903 23407) (14352 58265 46838 23458)
   (12809 23405 19125 63921) (13770 46625 2525 906) (43275 9289 40911 44977)
   (30626 9632 31938 50877) (20798 24163 19568 58161) (17249 49354 16233 12050)
   (55617 44196 19232 42075) (21135 31878 709 32891) (21163 37566 47457 14729)
   (40221 64046 64597 32627) (29231 61813 62834 49992) (7442 24741 4359 65175)
   (31268 39511 60428 39842) (1056 36841 59639 62166) (23057 3168 22713 8352)
   (3289 42135 25994 22168) (22269 9160 63857 23116) (10316 33915 40328 31406)
   (1278 44027 48566 6603) (29742 7781 7264 47747) (39574 13030 22788 44348)
   (34843 33441 15185 47586) (20590 26436 52631 18724) (45080 15797 28668 27257)
   (3801 47381 50798 54142) (24081 59501 22643 54404) (63096 25726 13593 44142)
   (7045 54408 53490 3269) (55993 65125 9688 36897) (3349 7558 44471 13845)
   (43109 42318 56512 61465) (37828 9574 44793 36859) (39399 45034 48640 1841)
   (18635 65288 28127 10330) (32667 27377 60407 35759) (22626 32282 5275 47649)
   (11473 28202 48505 7731) (54115 61429 61591 31126) (3298 41868 13386 28397)
   (6784 19117 47567 42817) (36991 12354 7544 50654) (20511 26093 45827 19719)
   (14178 19173 42127 42729) (38267 44897 28684 65358) (14956 10131 20017 6282)
   (54421 851 27324 41797) (2190 1173 35268 13024) (63811 44775 65215 8632)
   (27707 36414 13153 14803) (13903 28666 17998 58670) (54799 28110 56369 16930)
   (22166 15117 51777 36800) (5877 3807 37349 5039) (61209 21905 19296 40851)
   (22102 448 13902 12840) (60597 14649 34942 33141) (47815 43425 34097 10571)
   (45892 50288 14715 47698) (26067 18772 56051 52925) (46264 6975 43381 4578)
   (46114 1553 37846 63143) (1813 33344 7224 17229) (31251 61835 48860 20469)
   (48192 38833 5829 9426) (22969 30853 58098 59944) (39191 2653 49937 21828)
   (28482 13143 59334 43513) (12889 10478 28271 34708) (53476 13922 10416 13123)
   (22108 12791 56969 59943) (12533 24852 33809 37908) (55411 56121 4754 60751)
   (31705 19997 36375 57020) (51161 61800 25767 28308) (38010 57427 61014 58940)
   (51401 14466 63815 24415) (15003 62811 43295 33226) (55713 8123 15768 2276)
   (4050 8291 60866 40906) (46066 22232 44192 45241) (45104 12712 46161 28292)
   (13789 14293 34580 18607) (59894 2091 1364 11854) (60410 64051 55077 19289)
   (37461 43957 3411 8832) (47531 19685 32557 13555) (26933 470 10281 30033)
   (50732 22777 32217 18879) (52549 20367 6597 4714) (48104 16206 52267 57035)
   (56452 11134 10265 57904) (47753 5166 117 952) (41916 37917 2640 25035)
   (59894 30222 13005 32801) (2503 58706 48246 18735) (34095 21651 19877 23753)
   (33031 64719 1615 53078) (2441 21717 8191 25984) (9143 3803 6485 50367)
   (49968 56898 25648 63133) (18197 60739 59556 23562) (43223 58586 46976 41101)
   (1394 47476 61500 57531) (46461 11928 24084 6599) (59609 60606 11507 55103)
   (12260 45425 28901 38736) (4401 31656 30981 59280) (32703 8684 35359 17900)
   (5925 51903 51972 23296) (38478 37212 54754 45575) (15915 35787 61462 54893)
   (48756 17635 37672 41132) (63579 11087 48350 17591) (18741 16362 14778 25521)
   (7632 6831 52563 18538) (8138 35474 64881 40837) (64636 38360 10037 31482)
   (6310 43408 51379 24253) (52427 28677 50873 49805) (15323 47404 17329 32550)
   (43632 46516 63638 38306) (59724 14757 19096 12415) (47008 45428 53238 62318)
   (54491 43079 10671 18605) (11800 48154 55664 19048) (11744 38509 44847 35612)
   (47553 7515 7747 41086) (25751 11624 57059 13152) (37986 36152 53442 1412)
   (56256 53942 43920 42329) (53875 15427 13766 42799) (32373 55709 38055 3917)
   (27885 6531 14191 42795) (38908 43723 61488 48164) (31607 18811 12880 15122)
   (34119 60895 47132 52116) (31129 40159 63241 715) (53246 6457 17294 39716)
   (33430 9955 35117 38359) (37626 57922 37362 46065) (25570 11284 31644 13315)
   (50808 46808 24616 18972) (22643 34952 20581 39655) (2433 56530 38568 29549)
   (40805 30874 25865 42048) (40947 36845 29417 1327) (58489 61019 39216 22412)
   (59378 36557 11593 61133) (22208 29861 33258 6142) (21828 63447 29873 19183)
   (31551 405 64623 10511) (4629 13877 45760 53079) (32593 9947 47710 3239)
   (31350 38252 16047 46099) (15703 29857 7473 43833) (35355 2104 8692 3252)
   (31562 14563 9527 57186) (38145 4964 27933 28163) (19880 38810 65 59561)
   (15299 28167 36725 5591) (23818 4850 31443 4305) (32669 6702 7870 4903)
   (55866 13851 7249 22449) (56541 32032 36925 3109) (13955 13110 53352 63239)
   (52840 13343 31113 13193) (43920 36886 36304 24372) (17301 19250 21212 9701)
   (46136 49846 32664 58857) (4316 55182 14417 42130) (56258 31413 17528 8895)
   (39740 56165 63532 41858) (46715 30870 5755 19588) (49102 53680 1166 44112)
   (43281 39776 13983 65213) (8191 31432 2308 48965) (44050 64279 6167 61159)
   (44808 55953 30685 43325) (6924 43923 28261 51012) (46425 60189 1253 59698)
   (50043 17843 63702 62138) (50089 56354 36010 51689) (62392 46695 23141 2047)
   (40900 30686 20182 33242) (26423 36238 52463 38603) (28120 22233 19749 37430)
   (41753 52757 45236 56113) (1849 29557 7954 56670) (35470 33950 45863 33189)
   (57746 23665 10322 31221) (29888 19441 30988 3838) (19930 18453 15508 37770)
   (40230 28010 7360 21548) (29760 64385 25864 50430) (4914 34051 57160 8863)
   (54975 31662 58428 44096) (18488 54879 28406 29839) (7701 9000 62257 36330)
   (36740 6563 18674 38591) (29384 33610 22871 46353) (55200 9127 12896 46172)
   (38123 51371 53173 28078) (40897 3343 39065 37856) (56936 41525 23443 51942)
   (42060 65145 44627 35774) (40221 34044 52791 5157) (20946 45483 11743 46646)
   (12247 58553 59180 54156) (26058 23446 46933 8720) (56681 41176 43835 21613)
   (24653 20914 24511 28898) (29610 35414 20407 44190) (6796 7833 11156 4424)
   (43716 2599 985 48800) (30285 48814 32676 62374) (7833 47470 28841 48779)
   (11358 40427 22511 18243) (14995 36846 13010 39297) (9958 56207 65013 44542)
   (18067 22213 1260 40861) (51318 15451 2257 37004) (16236 27384 23000 85)
   (32636 50068 8355 42309) (39931 8830 48628 50638) (35075 40313 55036 23644)
   (36840 35671 12382 10934) (41118 35980 13739 38622) (64126 14649 33586 22355)
   (54966 53484 50711 50841) (57322 8682 40565 22499) (46716 8100 33128 2808)
   (51742 14213 43495 9445) (7420 35821 3432 5689) (53645 34121 53568 51946)
   (20176 65150 40393 4917) (58587 61539 17523 62930) (5985 63802 17621 44798)
   (21385 36428 14608 55893) (29517 59416 8046 50074) (9856 45346 47778 36247)
   (10634 62001 51291 44971) (31107 61139 29704 18389) (26305 41633 42508 55433)
   (40471 58518 17059 58561) (60852 21735 47836 2053) (20663 1226 46594 49961)
   (19651 6139 40157 53283) (26292 33629 40623 59938) (8603 38882 28668 33213)
   (9758 20044 2611 15005) (8162 52391 25879 56208) (55120 19962 34838 60859)
   (47447 8096 19904 35272) (7644 805 9627 10206) (53055 18056 32798 47530)
   (62709 53340 4298 45635) (14518 21084 8612 11022) (14070 3627 42234 26624)
   (60213 37760 12659 57550) (40012 54821 31834 13827) (44812 12669 12973 43658)
   (9614 23168 50976 19531) (35720 40290 19780 34909) (62673 17815 58976 63573)
   (54324 32614 60553 16835) (59033 60805 45279 46093) (9330 63008 31789 1156)
   (49825 59317 46169 44725) (43855 25681 52253 17900) (25462 30066 44605 24948)
   (42398 3025 371 6696) (4461 22 52116 36617) (11513 51402 1327 28319)
   (2825 2677 24745 26851) (44014 56754 56800 28657) (22767 49419 1698 1677)
   (50917 31352 64473 34528) (11947 36006 15592 727) (5281 38244 278 62262)
   (31752 10461 25166 50064) (55115 48759 58897 27335) (32836 22191 4341 64339)
   (60393 59946 57155 8647) (801 39481 61016 31280) (18808 32751 6063 39204)
   (41449 12300 55378 1352) (23365 58658 58545 46319) (46236 15161 38153 6710)
   (54345 2773 9969 17457) (4776 61974 44948 6338) (31 33660 50997 1316)
   (6263 46366 22439 25813) (41605 15232 61823 22766) (39230 7655 11574 54032)
   (45913 32896 52836 42582) (9519 22991 3487 1211) (53820 36375 27921 13824)
   (7130 1170 59364 22638) (8672 48464 9926 6591) (15113 31450 61576 63822)
   (36116 57051 12478 33902) (63836 65442 15093 63220) (14449 28679 25011 63299)
   (51815 11153 59876 64022) (25800 58673 49141 15189) (9234 24813 19153 59517)
   (4204 2489 29394 59426) (32698 6484 4325 51760) (30852 55740 27829 27096)
   (1607 57325 52617 18985) (25431 16368 15906 18292) (20424 59734 3985 45347)
   (7609 22244 20519 22393) (47321 4724 47593 54523) (41707 60999 58107 64737)
   (55793 62220 52631 64265) (61421 21463 24534 20075) (11885 707 24599 63103)
   (43434 19744 56072 20123) (46667 59608 45651 38593) (28875 27383 49877 48368)
   (39152 30372 63394 12846) (49028 18184 1510 39775) (38083 9503 1785 3315)
   (15872 15969 27237 37353) (47397 42701 1057 45043) (25021 53552 31846 58112)
   (49037 20744 57982 3400) (9226 46458 35720 35616) (64647 24907 44840 32263)
   (61186 52688 28669 46130) (41224 11268 26335 27658) (33301 58743 19 13000)
   (54171 47555 42125 46799) (10040 9622 13360 23572) (25039 20372 51581 63805)
   (7019 44194 44622 4699) (30095 17676 34903 11787) (38303 22653 20602 33625)
   (45155 59746 57413 62797) (24808 60786 49375 62929) (31588 38789 21810 28575)
   (64776 3363 28072 5306) (35984 64923 2111 17752) (4207 29438 33250 50576)
   (31094 826 14839 55634) (42220 306 30284 41035) (29502 42757 64228 64119)
   (46296 63355 50149 24935) (40481 62713 947 16345) (40310 24129 40886 40813)
   (54028 2187 42526 42479) (23956 13183 49071 32603) (6734 18466 60237 31321)
   (28670 29672 7011 32691) (56825 22460 14040 47562) (25808 58014 60040 14515)
   (2269 39903 55659 40803) (2174 31205 42365 7443) (58152 57904 58338 46075)
   (7205 23011 3849 18110) (29195 62962 28493 11946) (45175 19750 7366 2523)
   (17471 25836 23095 4501) (16658 53096 25754 9742) (55315 62202 47093 50634)
   (26125 12887 14344 16878) (22956 11384 29689 4259) (59462 38456 30567 6679)
   (37814 13227 64052 27128) (49344 62886 3828 52687) (51954 7885 17271 45708)
   (22311 30471 6555 33141) (20588 4537 55566 35613) (55356 49768 31257 9567)
   (18985 50758 23089 19665) (60717 61970 5667 20631) (46435 23701 65394 38626)
   (8879 58 46706 59409) (21223 25177 27638 33333) (39659 41786 50924 50864)
   (37967 28128 37172 57270) (27719 48840 33703 56889) (27344 18372 12449 8452)
   (42417 53211 41131 16487) (31813 55347 45040 30818) (20626 61333 2582 55819)
   (37688 59036 1323 36475) (17754 19276 65072 58357) (27394 58929 38317 3320)
   (27415 45604 47830 48935) (53728 52434 23481 49513) (56844 35237 22201 44656)
   (20486 24147 23073 15606) (39953 27130 10103 47220) (30957 61398 38063 7917)
   (28105 15765 9893 3688) (61079 62547 61543 37357) (12971 3803 26983 979)
   (14952 21447 59143 22439) (12678 23789 24864 62333) (26622 63837 37472 30864)
   (7979 7455 5622 56476) (46750 14504 38492 27493) (43665 6655 6220 52468)
   (62524 29480 29682 19475) (64330 15737 19098 32978) (13648 49714 8150 4252)
   (14111 30695 27576 16766) (27642 39598 24256 22393) (52484 62463 26 18296)
   (58151 13602 1604 32970) (40849 20619 65487 49482) (1178 32577 1562 40544)
   (64694 48707 43506 65179) (2270 35356 30615 55963) (36760 34790 1927 13729)
   (46516 1821 49095 14950) (8974 13373 64416 36147) (17389 32602 4014 25981)
   (14984 41211 48304 23651) (8583 19339 19757 48207) (7134 41262 13814 43209)
   (21440 26054 51430 13608) (58186 7461 3706 36203) (54960 19771 30289 56702)
   (24208 10110 31923 40493) (11268 28450 1581 50813) (45323 46169 4909 2598)
   (16297 56827 26594 61849) (3593 47246 6420 63407) (4328 45914 62446 43831)
   (40685 60584 57970 47411) (54471 6332 19176 44639) (33107 28000 4464 64544)
   (37301 13560 34177 35334) (60545 30712 16272 2424) (6414 29007 44453 5486)
   (46482 48953 45110 18787) (35267 20680 37806 32193) (44036 11888 63667 33778)
   (46235 21221 34721 61024) (64277 12259 65318 55945) (15974 28271 27054 11285)
   (15188 20158 21580 6649) (59397 41442 37071 9302) (9395 15517 32466 20759)
   (59207 13122 31602 61633) (2688 19736 46857 29813) (22499 12397 34846 56143)
   (19175 54947 28341 56267) (11661 21554 5488 25800) (53734 18910 7807 9867)
   (35378 35356 60926 21804) (1955 44743 38436 51162) (33876 32220 15904 15508)
   (39178 39165 20593 53859) (6735 61734 5870 64649) (63223 64788 12657 16896)
   (12480 23323 41778 62492) (36134 14008 5461 42886) (18121 65205 23826 2306)
   (52460 2675 46236 39201) (20125 10279 13663 50322) (6635 45097 17245 51983)
   (18009 53943 17284 35372) (38462 62153 27443 48689) (29944 20888 45146 11901)
   (23055 21581 53937 64280) (882 28787 49889 13489) (51190 43565 58778 60001)
   (13607 34746 41175 49711) (38995 60086 15198 2869) (43965 52695 60764 2144)
   (52997 56053 44173 30640) (18890 54412 60404 42782) (31308 4332 8536 50342)
   (55785 10914 18111 29086) (5038 38797 2558 21847) (29444 39343 37397 18943)
   (20043 28763 37520 15268) (65367 29218 49487 2618) (21942 13388 63866 44974)
   (47202 8795 1371 26976) (51904 39675 56786 52660) (56056 59778 40937 27487)
   (46589 64605 12594 50328) (12556 45952 56175 29955) (59519 47942 8570 13838)
   (8450 44614 28347 4424) (63572 40474 15013 57357) (1958 39677 52290 9754)
   (50369 6335 59279 60078) (63988 35118 55659 54328) (6899 56290 23951 17882)
   (62900 45232 53982 61108) (38442 52975 43054 7300) (1134 16074 44869 15593)
   (61533 4758 33172 39500) (38471 33230 29515 15492) (39982 54336 33230 24509)
   (21038 9203 37470 12702) (6014 249 64562 63377) (11206 2659 42739 46066)
   (8747 49070 24946 22022) (18530 35293 52285 26496) (32199 30811 36605 64640)
   (35571 34609 49195 43392) (8107 25834 10658 56823) (58585 17043 8909 1626)
   (40352 22726 30788 61964) (9408 58162 46848 6576) (9008 949 42703 59053)
   (54662 48385 50626 6134) (24150 14216 24361 48171) (32442 29293 35988 2379)
   (2646 42480 49123 37490) (55188 30376 20194 3334) (40524 4713 47780 48951)
   (6127 60997 45278 58944) (7573 45221 64761 3014) (37835 57526 39362 22621)
   (26106 20258 31275 28025) (54777 59480 10533 1237) (49845 41023 28999 6767)
   (22832 546 46166 7680) (52783 34370 51719 4828) (31913 29247 47918 35208)
   (10117 13187 18418 47624) (50715 45985 16869 3724) (5391 13853 43933 60454)
   (40810 16797 14373 38388) (25765 15817 9470 31433) (5165 58527 65402 31805)
   (3123 21064 34175 43495) (2716 13013 60132 21253) (59076 8568 50363 47406)
   (29169 52772 37074 2823) (61884 50130 30127 58650) (59176 59592 15411 16500)
   (38651 63546 4744 17956) (33185 21663 54871 15781) (24487 34428 44853 57673)
   (22168 28206 62445 2331) (37247 7637 63624 27745) (53773 35976 51455 58975)
   (12759 7630 25778 49936) (61797 46471 57225 33168) (42366 25401 56620 62368)
   (7926 59099 45462 7881) (28876 29657 3010 28196) (57882 27445 57100 15063)
   (58 37848 45696 26978) (7321 57043 15544 37025) (53041 17886 2781 17033)
   (53476 17018 21780 64370) (30662 8652 40883 42115) (26531 19884 17238 21771)
   (63702 9898 44839 34057)]
  "Zorbist hashes for polyglot.")

(defconst chess-polyglot-zorbist-piece-type '(?p ?P ?n ?N ?b ?B ?r ?R ?q ?Q ?k ?K)
  "Map chess pieces to zorbist hash indexes.")

(defun chess-polyglot-pos-to-key (position)
  "Calculate the polyglot zorbist hash for POSITION.
Uses 781 predefined hash values from `chess-polyglot-zorbist-keys'."
  (declare (side-effect-free t))
  (cl-check-type position chess-pos)
  (let ((a16 0) (b16 0) (c16 0) (d16 0))
    (dotimes (index 64)
      (let ((piece (cl-position (chess-pos-piece position index)
				chess-polyglot-zorbist-piece-type)))
	(when piece
	  (let ((piece-key (aref chess-polyglot-zorbist-keys
				 (+ (* 64 piece) (logxor index #o70)))))
	    (setq a16 (logxor a16 (nth 0 piece-key))
		  b16 (logxor b16 (nth 1 piece-key))
		  c16 (logxor c16 (nth 2 piece-key))
		  d16 (logxor d16 (nth 3 piece-key)))))))
    (let ((sides '(?K ?Q ?k ?q)))
      (dolist (side sides)
	(when (chess-pos-can-castle position side)
	  (let ((castle-key (aref chess-polyglot-zorbist-keys
				  (+ 768 (cl-position side sides)))))
	    (setq a16 (logxor a16 (nth 0 castle-key))
		  b16 (logxor b16 (nth 1 castle-key))
		  c16 (logxor c16 (nth 2 castle-key))
		  d16 (logxor d16 (nth 3 castle-key)))))))
    ;; TODO: en passant
    (when (chess-pos-side-to-move position)
      (let ((turn-key (aref chess-polyglot-zorbist-keys 780)))
	(setq a16 (logxor a16 (nth 0 turn-key))
	      b16 (logxor b16 (nth 1 turn-key))
	      c16 (logxor c16 (nth 2 turn-key))
	      d16 (logxor d16 (nth 3 turn-key)))))
    (list a16 b16 c16 d16)))

;;; Public interface:

(defun chess-polyglot-book-open (file)
  "Open a polyglot book FILE.
Returns a buffer object which contains the binary data."
  (when (file-exists-p file)
    (with-current-buffer (get-buffer-create (concat " *chess-polyglot " file "*"))
      (erase-buffer)
      (set-buffer-multibyte nil)
      (insert-file-contents-literally file)
      (when (and (fboundp 'zlib-decompress-region)
		 (goto-char (point-min))
		 (re-search-forward "\\`\037\213\\(.\\)\\(.\\)\\(.\\)\\(.\\)\\(.\\)\\(.\\)\\(.\\)\\(.\\)" nil t)
		 (pcase (list (aref (match-string 1) 0)
			      (aref (match-string 2) 0)
			      (logior (aref (match-string 3) 0)
				      (lsh (aref (match-string 4) 0) 8)
				      (lsh (aref (match-string 5) 0) 16)
				      (lsh (aref (match-string 6) 0) 24))
			      (aref (match-string 7) 0)
			      (aref (match-string 8) 0))
		   (`(,method ,_ ,modified-epoch ,_ ,from-fs)
		    (and (= method 8) (> modified-epoch 0) (< from-fs 16)))))
	(zlib-decompress-region (point-min) (point-max)))
      (cl-assert (zerop (% (buffer-size) chess-polyglot-record-size)))
      (current-buffer))))

(defun chess-polyglot-book-plies (book position)
  "Return a list of plies found in BOOK for POSITION.
The resulting list is ordered, most interesting plies come first.
The :polyglot-book-weight ply keyword is used to store the actual move weights.
Use `chess-ply-keyword' on elements of the returned list to retrieve them."
  (cl-check-type book buffer)
  (cl-check-type position chess-pos)
  (let (plies)
    (dolist (move
	     (with-current-buffer book
	       (chess-polyglot-read-moves (chess-polyglot-pos-to-key position)))
	     plies)
      (let ((ply (apply #'chess-polyglot-move-to-ply position move)))
	(when ply
	  (setq plies (nconc plies (list ply))))))))

(defun chess-polyglot-book-ply (book position &optional strength)
  "If non-nil a (randomly picked) ply from plies in BOOK for POSITION.
Random distribution is defined by the relative weights of the found plies.
If non-nil, STRENGTH defines the bias towards better moves.
A value below 1.0 will penalize known good moves while a value
above 1.0 will prefer known good moves.  The default is the value
of `chess-polyglot-book-strength'.
A strength value of 0.0 will completely ignore move weights and evenly
distribute the probability that a move gets picked."
  (unless strength (setq strength chess-polyglot-book-strength))
  (cl-assert (and (>= strength 0) (< strength 4)))
  (cl-flet ((ply-weight (ply)
	      (round (expt (chess-ply-keyword ply :polyglot-book-weight)
			   strength))))
    (let ((plies (chess-polyglot-book-plies book position)))
      (when plies
	(let ((random-value (random (cl-reduce #'+ (mapcar #'ply-weight plies))))
	      (max 0) ply)
	  (while plies
	    (if (< random-value (cl-incf max (ply-weight (car plies))))
		(setq ply (car plies) plies nil)
	      (setq plies (cdr plies))))
	  (cl-assert ply)
	  ply)))))

(defalias 'chess-polyglot-book-close 'kill-buffer
  "Close a polyglot book.")

(defun chess-polyglot-book-reload (symbol value)
  (set symbol value)
  (setq chess-polyglot-book
        (when value (chess-polyglot-book-open value))))

(defcustom chess-polyglot-book-file (expand-file-name "chess-polyglot.bin"
						      (file-name-directory
						       (or load-file-name
							   buffer-file-name)))
  "Path to default polyglot book file.

This is used by UCI based engines as well as the internal AI."
  :group 'chess-polyglot
  :set 'chess-polyglot-book-reload
  :type '(file :must-match t))

(provide 'chess-polyglot)
;;; chess-polyglot.el ends here