; ------------------------------------------------------------------ gen
; The legal plays from a board, each position once, in a fixed order: a
; depth-first search over single steps, from the bar and the highest point
; down (a double's steps never from above the last). It first measures how
; many dice can be played, then calls the handler for each play of that
; many (with only one die, the larger if it can be), with the position in
; W, its steps in STEPS and their dice in GDIE. Two plays of a non-double
; can give one position; those are told apart by a hash of their changes.

; step: a checker from point B by die E on W. Carry if illegal; else
; played, A = 1 if it hit. Keeps B, D, E.
step:
        ld h,high W
        ld l,b
        ld a,(hl)
        or a
        scf
        ret z                   ; no checker there
        ld a,b
        sub e
        jr c,.off
        ld c,a                  ; the point it lands on
        ld a,OPPOFF+23
        sub c
        ld l,a                  ; the same point, the opponent's
        ld a,(hl)
        cp 2
        ccf
        ret c                   ; held
        dec a
        jr nz,.move
        ld (hl),a               ; a blot: to the bar
        ld l,OPPOFF+24
        inc (hl)
        ld a,1
        jr .moved
.move:  xor a
.moved: ld l,b
        dec (hl)
        ld l,c
        inc (hl)
        or a
        ret
.off:   ; bearing off: all home, and by the exact number or from the top
        ld l,24
.hi:    ld a,(hl)
        or a
        jr nz,.top
        dec l
        jr .hi
.top:   ld a,l
        cp 6
        ccf
        ret c
        ld a,b
        inc a
        cp e
        jr z,.bear
        ld a,l
        cp b
        scf
        ret nz
.bear:  ld l,b
        dec (hl)
        xor a
        ret

; unstep: takes back the step from B by E, which hit if A = 1.
unstep:
        ld h,high W
        ld l,b
        inc (hl)
        ld c,a
        ld a,b
        sub e
        ret c
        ld l,a
        dec (hl)
        dec c
        ret nz
        ld a,OPPOFF+23
        sub l
        ld l,a
        ld (hl),1
        ld l,OPPOFF+24
        dec (hl)
        ret

; dfs: C = steps taken, B = the highest point to step from.
dfs:
        ld a,(GMAX)
        cp c
        jr nc,.seen
        ld a,c
        ld (GMAX),a
.seen:  ld a,(GTARGET)
        cp c
        jr nz,.more
        ld a,(GEMIT)
        or a
        jr z,gabort
        ld hl,(LEAFFN)
        jp (hl)
.more:  ld h,high GDIE
        ld a,low GDIE
        add a,c
        ld l,a
        ld e,(hl)               ; the die
        ld d,0                  ; the lowest point to step from
        ld a,(W+24)
        or a
        jr z,.loop
        ld d,24                 ; the bar first
.loop:  ld h,high W
        ld l,b
        ld a,(hl)
        or a
        jr z,.next              ; no checker there
        ld a,(GPRUNE)
        and c
        jr z,.try
        call prune
        jr z,.next
.try:   push bc
        call step
        pop bc
        jr c,.next
        push af
        ld h,high STEPS
        ld l,c
        sla l
        ld (hl),b
        inc l
        ld (hl),a
        ld hl,(FSCORE)
        push hl
        call fdelta
        ld hl,(KEY)
        push hl
        ld hl,(KEY+2)
        push hl
        ld a,(GKEYED)
        or a
        call nz,kstep
        push bc
        push de
        inc c
        ld a,(GDOUBLE)
        or a
        jr nz,.same
        ld b,24
.same:  call dfs
        pop de
        pop bc
        pop hl
        ld (KEY+2),hl
        pop hl
        ld (KEY),hl
        pop hl
        ld (FSCORE),hl
        pop af
        push bc
        call unstep
        pop bc
.next:  ld a,b
        cp d
        ret z
        dec b
        jr .loop

; The target reached while measuring: out of the search at once.
gabort:
        ld sp,(GSP)
        ld a,(GTARGET)
        ld (GMAX),a
        ld hl,(GROOT)
        ld de,W
        ld bc,64
        ldir
        ret

; rundfs: A = the steps to reach.
rundfs:
        ld (GTARGET),a
        xor a
        ld (GMAX),a
        ld (GSP),sp
        ld bc,24*256
        jp dfs

; gen: HL -> the board, DHI >= DLO the dice, USERFN the handler. Plays
; counted in GCOUNT.
gen:
        ld (GROOT),hl
        ld de,W
        ld bc,64
        ldir
        ld hl,0
        ld (GCOUNT),hl
        xor a
        ld (GKEYED),a
        ld (GPRUNE),a
        ; a new number for the hash table's entries (clearing it on wrapping)
        ld hl,GENID
        inc (hl)
        jr nz,.id
        inc (hl)
        ld hl,HSTAMP
        ld de,HSTAMP+1
        ld bc,255
        ld (hl),b
        ldir
.id:    ld a,(DHI)
        ld b,a
        ld a,(DLO)
        cp b
        jr nz,.nd
        ld hl,GDIE
        ld (hl),a
        inc l
        ld (hl),a
        inc l
        ld (hl),a
        inc l
        ld (hl),a
        ld (GDOUBLE),a
        ld a,4
        call measure
        or a
        ret z
        ld hl,leaf
        jr emit
.nd:    xor a
        ld (GDOUBLE),a
        call order_a
        call measure2
        ld (GMAXA),a
        cp 2
        jr z,.two
        call order_b
        call measure2
        cp 2
        jr z,.two
        ld b,a
        ld a,(GMAXA)
        or a
        jr nz,.a1
        or b
        ret z
        jr .one                 ; the smaller die only
.a1:    call order_a
.one:   ld a,1
        ld hl,leaf
        jr emit
.two:   ld a,1
        ld (GKEYED),a
        call order_a
        ld a,2
        ld hl,leafk
        call emit
        ld a,(W+24)
        or a
        jr nz,.bar
        inc a
        ld (GPRUNE),a
.bar:   call order_b
        ld a,2
        ld hl,leafk
emit:   ld (LEAFFN),hl
        ld hl,0
        ld (KEY),hl
        ld (KEY+2),hl
        ld hl,GEMIT
        ld (hl),1
        jp rundfs
measure2:
        ld a,2
measure:
        ld hl,GEMIT
        ld (hl),0
        call rundfs
        ld a,(GMAX)
        ret
order_a:
        ld a,(DHI)
        ld (GDIE),a
        ld a,(DLO)
        ld (GDIE+1),a
        ret
order_b:
        ld a,(DLO)
        ld (GDIE),a
        ld a,(DHI)
        ld (GDIE+1),a
        ret

; A play of a non-double: dropped if its hash (the sum over its steps of
; the values of the points it adds a checker to, less those it takes one
; from, kept in KEY as the search goes) is one seen already.
leafk:
        ; into a table of 256 by the hash's first byte, the next free
        ; entry on; an entry is in use if stamped with this search's number
        ld a,(KEY)
        ld l,a
.p:     ld h,high HSTAMP
        ld a,(GENID)
        cp (hl)
        jr nz,.new
        ld de,KEY
        ld b,4
.c:     inc h
        ld a,(de)
        cp (hl)
        jr nz,.nx
        inc de
        djnz .c
        ret                     ; seen
.nx:    inc l
        jr .p
.new:   ld (hl),a
        ld de,KEY
        ld b,4
.w:     inc h
        ld a,(de)
        ld (hl),a
        inc de
        djnz .w
leaf:
        ld hl,(GCOUNT)
        inc hl
        ld (GCOUNT),hl
        ld hl,(USERFN)
        jp (hl)

; prune: in the second order (low die first), from no bar, the second
; step from B by E: Z if the first order has made the same play, as it
; has unless a checker is borne off, or B is the point the first step
; reached and the root had no checker there.
prune:
        ld a,b
        sub e
        jr c,.no
        ld a,(STEPS)
        ld hl,GDIE
        sub (hl)
        jr c,.no
        cp b
        jr nz,.yes
        ld hl,(GROOT)
        call index
        or a
        jr z,.no
.yes:   xor a
        ret
.no:    or 1
        ret

; kstep: KEY updated for the step from B by E (C the steps before it).
; Keeps BC, DE.
kstep:
        push bc
        push de
        ld h,high STEPS
        ld l,c
        sla l
        inc l
        ld c,(hl)
        ld a,b
        push bc
        push de
        call ksub
        pop de
        pop bc
        ld a,b
        sub e
        jr nc,.on
        ld a,25                 ; borne off
.on:    push af
        push bc
        call kadd
        pop bc
        pop af
        dec c
        jr nz,.x
        cpl
        add a,26+24             ; the opponent's point hit: 26 + 23 - to
        call ksub
        ld a,26+24              ; and their bar
        call kadd
.x:     pop de
        pop bc
        ret

; KEY += RTAB[A], KEY -= RTAB[A].
kadd:
        call rptr
        ld de,KEY
        ld b,4
        or a
.l:     ld a,(de)
        adc a,(hl)
        ld (de),a
        inc hl
        inc de
        djnz .l
        ret
ksub:
        call rptr
        ld de,KEY
        ld b,4
        or a
.l:     ld a,(de)
        sbc a,(hl)
        ld (de),a
        inc hl
        inc de
        djnz .l
        ret
rptr:
        ld l,a
        ld h,0
        add hl,hl
        add hl,hl
        ld de,RTAB
        add hl,de
        ret

; fdelta: after a step from B by E (A = 1 if it hit), FSCORE += the change
; to the filter's score of W turned (the other side on roll): the checker
; taken off its point, put on another or borne off, and a checker hit to
; the bar. Adding a checker to a point of n adds its weight for one
; checker (n = 0), for two less that for one (1), for three (2), or for
; each beyond three (3 or more). Keeps BC, DE.
fdelta:
        push bc
        push de
        ld (FHIT),a
        ld a,e
        ld (FDIE),a
        ld h,high W
        ld l,b
        ld c,(hl)
        ld a,b
        ld d,101
        call frow
        ld a,c
        call dplus
        ld hl,(FSCORE)
        or a
        sbc hl,de
        ld (FSCORE),hl
        ld a,b
        ld hl,FDIE
        sub (hl)
        jr c,.off
        ld c,a
        ld h,high W
        ld l,a
        ld a,(hl)
        dec a
        push af
        ld a,c
        ld d,101
        call frow
        pop af
        call dplus
        call .add
        ld a,(FHIT)
        or a
        jr z,.done
        ld a,23
        sub c
        ld d,0
        call frow
        xor a
        call dplus
        ld hl,(FSCORE)
        or a
        sbc hl,de
        ld (FSCORE),hl
        ld a,(W+OPPOFF+24)
        dec a
        push af
        ld a,24
        ld d,0
        call frow
        pop af
        call dplus
        call .add
.done:  pop de
        pop bc
        ret
.off:   ld a,(FILT_W+201)
        xor $80
        call sext
        call .add
        jr .done
.add:   ld hl,(FSCORE)
        add hl,de
        ld (FSCORE),hl
        ret

; frow: A = a point, D = 0 or 101 (the side on roll, or the other) -> HL
; -> the filter's weights for it. Keeps C.
frow:   add a,a
        add a,a
        add a,d
        ld l,a
        ld h,0
        ld de,FILT_W
        add hl,de
        ret

; dplus: HL -> a point's filter weights (plus 128), A = its checkers -> DE
; = the change adding one.
dplus:  or a
        jr z,.one
        dec a
        jr z,.two
        inc hl
        inc hl
        dec a
        jr z,.one
        inc hl
.one:   ld a,(hl)
        xor $80
        jr sext
.two:   ld e,(hl)
        inc hl
        ld a,(hl)
        sub e
        ld e,a
        sbc a,a
        ld d,a
        ret
; sext: DE = A sign-extended.
sext:   ld e,a
        rla
        sbc a,a
        ld d,a
        ret