Chess

+Andrew Davie · April 6, 2020

1 minute ago, devwebcl said:

Right, I was playing, and my rook checked its king, but instead of avoiding the check (capturing my rook), the CPU moved its rook and checked my king.

So, I am in an inconsistent chess game. Then later, I captured its king, and the CPU is still playing.

You should consider you have won the game when you put his king in checkmate

I'll put the endgame checking in soon. Things to do...

1) quiescence. This is where it doesn't finish searching until there are no captures happening. It is supposed to give a better evaluation of the position, and definitely stops the computer pushing the "worst case" off the search and thus thinking moves like the above are reasonable.
2) staggered/incremental depth searching, with sorting. Do a 2 ply search, giving a score to each move on the first ply. Then sort, best to worst, then do a 3 ply search, then sort, best to worst, then a 4-ply. If a "normal" 2ply takes 1s, and a 3 ply takes 15s, and a 4ply takes 100s then you would think this would result in a (100+15+1) = 116 s search. But in fact what should happen is that the sorting should make the alpha-beta much more efficient (many more beta prunes) and thus less to search. I would expect this to reduce the 4-ply from 100s down to 10s or so. We shall see.

3) Detection of end-game situations a) checkmate, b) stalemate, c) draw ... maybe ... not sure how efficient it will be to try and do c).

4) en passant moves. Very low priority and besides has given me hours of grief so it's on the backburner.

Anyway, thanks for the feedback. Did you enjoy your game?

+Andrew Davie · April 6, 2020

I should note that with (2) this actually occurs on all levels.

That is, once the tree starts to get deeper (say, 4 ply), then the 2nd ply can do a 2-ply look-ahead search so that it can sort the moves (on the 2nd ply) to make a deeper search more efficient from that ply onwards. Sort of recursive. We'll see how that works.

+Andrew Davie · April 6, 2020

13 minutes ago, devwebcl said:

Right, I was playing, and my rook checked its king, but instead of avoiding the check (capturing my rook), the CPU moved its rook and checked my king.

So, I am in an inconsistent chess game. Then later, I captured its king, and the CPU is still playing.

In this situation, it seemed it could swap ROOK/KING for ROOK/KING and end up in a better position.

Seems reasonable to me

+Andrew Davie · April 6, 2020

One last-resort kludge to improve speed is... after sorting, keep only N moves for checking.

The logic being, hopefully the best move will be in the first highest-scoring N moves, based on a 2-ply lookahead.

This could be used to reduce # moves on each ply from (average 33) down to something like (average 10) with consequent massive speedup in searching, and increased depth. It's all a bit of a balance, which I will try to fine tune once the fundamentals are complete.

devwebcl · April 6, 2020

13 minutes ago, Andrew Davie said:

You should consider you have won the game when you put his king in checkmate

I'll put the endgame checking in soon. Things to do...

1) quiescence. This is where it doesn't finish searching until there are no captures happening. It is supposed to give a better evaluation of the position, and definitely stops the computer pushing the "worst case" off the search and thus thinking moves like the above are reasonable.
2) staggered/incremental depth searching, with sorting. Do a 2 ply search, giving a score to each move on the first ply. Then sort, best to worst, then do a 3 ply search, then sort, best to worst, then a 4-ply. If a "normal" 2ply takes 1s, and a 3 ply takes 15s, and a 4ply takes 100s then you would think this would result in a (100+15+1) = 116 s search. But in fact what should happen is that the sorting should make the alpha-beta much more efficient (many more beta prunes) and thus less to search. I would expect this to reduce the 4-ply from 100s down to 10s or so. We shall see.

3) Detection of end-game situations a) checkmate, b) stalemate, c) draw ... maybe ... not sure how efficient it will be to try and do c).

4) en passant moves. Very low priority and besides has given me hours of grief so it's on the backburner.

Anyway, thanks for the feedback. Did you enjoy your game?

Yes, it was a good game. The CPU defended their pieces and try to capture some of the mines smartly.
Besides, it is swift... assuming this is a 2600.

I reckon the UI is the best.

+Andrew Davie · April 6, 2020

1 minute ago, devwebcl said:

Yes, it was a good game. The CPU defended their pieces and try to capture some of the mines smartly.
Besides, it is swift... assuming this is a 2600.

I reckon the UI is the best.

Great! It's definitely a '2600

TY for reviewing and kind comments.

+Andrew Davie · April 6, 2020

BTW, in this implementation I've been rabbiting on about minimax search, and alpha-beta search/pruning but in fact the implementation is what's now known as a "negamax" search. I wasn't previously aware of the term, and this is quite new to me. Anyway, it makes the code sweet and neat, and has contributed to the speed.

+Andrew Davie · April 6, 2020

Here's the full source code in case anyone wants a look-see.

The alphaBeta function is in BANK_FIXED.asm

Actually it's not that big, so here it is...

    SUBROUTINE

.terminal           ;jsr QuiesceStart                ; with alpha, beta already setup
;                    rts


                    lda Evaluation
                    sta __bestScore
                    lda Evaluation+1
                    sta __bestScore+1
                    rts


.returnScore

    ; we've iterated the moves, so 'bestMove' and 'bestScore' are the result

                    lda bestScore
                    sta __bestScore
                    lda bestScore+1
                    sta __bestScore+1               ; value of the best move found

                    lda bestMove
                    sta __bestMove                  ; moveIndex of the best move found
                    rts


    DEF alphaBeta

    ; Performs an alpha-beta search.
    ; The current 'level' is always considered in terms of maximising the evaluation
    ; To achieve minimisation for the opponent when being considered, the alpha/beta are negated
    ; and which is which is swapped between each ply

    ; pass...
    ; x = depthleft
    ; SET_BANK_RAM      --> current ply
    ; __alpha[2] = -alpha
    ; __beta[2] = -beta


        COMMON_VARS_ALPHABETA
        REFER selectmove
        VEND alphaBeta


    ;def alphabeta( alpha, beta, depthleft ):
    ;    bestscore = -9999
    ;    if( depthleft == 0 ):
    ;        return quiesce( alpha, beta )
    ;    for move in board.legal_moves:
    ;        make_move(move)
    ;        score = -alphabeta( -beta, -alpha, depthleft - 1 )
    ;        unmake_move()
    ;        if( score >= beta ):
    ;            return score
    ;        if( score > bestscore ):
    ;            bestscore = score
    ;        if( score > alpha ):
    ;            alpha = score
    ;    return bestscore

                    stx@RAM depthLeft


    ; setup parameters
    ; beta = -alpha, alpha = -beta
    ; we want to maximise alpha
    ;  and if score > beta then abort (cutoff)

                    lda __beta
                    sta@RAM alpha
                    lda __beta+1
                    sta@RAM alpha+1

                    lda __alpha
                    sta@RAM beta
                    lda __alpha+1
                    sta@RAM beta+1

    ; on 1st call this becomes alpha = -INF and beta = INF
    ; we're trying to maximise alpha

                    cpx #0
                    beq .terminal                   ; --> quiesce

                    lda #<-(INFINITY-1)
                    sta@RAM bestScore
                    lda #>-(INFINITY-1)
                    sta@RAM bestScore+1



    ; The evaluation of the current position is a signed 16-bit number
    ; +ve is good for the current side.
    ; This is used during the alpha-beta search for finding best position
    ; Note, this is not the same as the 'Evaluation' which is the current value at ply -- it is the
    ; alphabeta best/worst value of the node!!


                    ;lda currentPly
                    ;sta savedBank

                    jsr NewPlyInitialise
                    jsr GenerateAllMoves

    ; Now iterate the moves one-by-one

                    lda moveIndex
                    sta@RAM movePtr


.loopMoves          ldx movePtr
                    bmi .returnScore



                    jsr MakeMove

    ; "score = -alphabeta( -beta, -alpha, depthleft - 1 )"
    ; set pareameters for next level --> __alpha, __beta
    
                    sec
                    lda #0
                    sbc alpha
                    sta __alpha
                    lda #0
                    sbc alpha+1
                    sta __alpha+1                   ; -alpha

                    sec
                    lda #0
                    sbc beta
                    sta __beta
                    lda #0
                    sbc beta+1
                    sta __beta+1                    ; -beta

                    ldx depthLeft
                    dex

                    inc currentPly
                    lda currentPly
                    sta SET_BANK_RAM                ; self-switch

                    jsr alphaBeta                   ; recurse!

                    dec currentPly
                    lda currentPly
                    sta SET_BANK_RAM

                    sec
                    lda #0
                    sbc __bestScore
                    sta __bestScore
                    lda #0
                    sbc __bestScore+1
                    sta __bestScore+1               ; "-alphabeta....""

                    jsr unmake_move

    ;        if( score >= beta ):
    ;            return score

    ; an alpha-beta cutoff?
    ; aborts searching any more moves because the opponent score improves

                    sec                             ; drop for extra speed
                    lda __bestScore
                    sbc beta
                    lda __bestScore+1
                    sbc beta+1
                    bvc .lab2                       ; if V is 0, N eor V = N, otherwise N eor V = N eor 1
                    eor #$80                        ; A = A eor $80, and N= N eor 1
.lab2               bmi .notScoreGteBeta

;If the N flag is 1, then A (signed) < NUM (signed) and BMI will branch
;If the N flag is 0, then A (signed) >= NUM (signed) and BPL will branch
;One way to remember which is which is to remember that minus (BMI) is less than, and plus (BPL) is greater than or equal to.

                    ;lda __score
                    ;sta __bestScore
                    ;lda __score+1
                    ;sta __bestScore+1              // already has correct value

                    lda bestMove       ; //??
                    sta __bestMove                  ; this move!
                    rts

.notScoreGteBeta

    ;        if( score > bestscore ):
    ;            bestscore = score

                    clc                     ; !! OK. Could be dropped for a bit of speed
                    lda __bestScore
                    sbc bestScore
                    lda __bestScore+1
                    sbc bestScore+1
                    bvc .lab3                       ; if V is 0, N eor V = N, otherwise N eor V = N eor 1
                    eor #$80                        ; A = A eor $80, and N= N eor 1
.lab3               bmi .notScoreGtBestScore

                    lda __bestScore
                    sta@RAM bestScore
                    lda __bestScore+1
                    sta@RAM bestScore+1

                    lda movePtr
                    sta@RAM bestMove

.notScoreGtBestScore


    ;        if( score > alpha ):
    ;            alpha = score



;As stated above, after a CMP instruction, the N flag is NOT the signed
;comparison result.  A signed comparison works by performing a subtraction,
;but the signed comparison result is the exclusive-or (eor) of the N and V
;flags.  Specifically, to compare the signed numbers NUM1 and NUM2, the
;subtraction NUM1-NUM2 is performed, and NUM1 &lt; NUM2 when N eor V is 1, and
;NUM1 &gt;= NUM2 when N eor V is 0.  (A program that proves this is given in
;Appendix A.)

    ; We've found a higher scoring move than currently known, so record it

                    clc                     ; !! OK. Could be dropped for a bit of speed
                    lda alpha
                    sbc __bestScore
                    lda alpha+1
                    sbc __bestScore+1
                    bvc .lab                ; if V is 0, N eor V = N, otherwise N eor V = N eor 1
                    eor #$80                ; A = A eor $80, and N= N eor 1
.lab                bpl .notScoreGtAlpha

;If the N flag is 1, then A (signed) < NUM (signed) and BMI will branch
;If the N flag is 0, then A (signed) >= NUM (signed) and BPL will branch
;One way to remember which is which is to remember that minus (BMI) is less than, and plus (BPL) is greater than or equal to.


                    lda __bestScore
                    sta@RAM alpha
                    lda __bestScore+1
                    sta@RAM alpha+1

                    ;lda movePtr             ; //??
                    ;sta@RAM bestMove

.notScoreGtAlpha    ldx movePtr
                    dex
                    stx@RAM movePtr
                    jmp .loopMoves

chess20200406_source_code.zip

Edited April 6, 2020 by Andrew Davie

Mr SQL · April 6, 2020

1 hour ago, Andrew Davie said:

BTW, in this implementation I've been rabbiting on about minimax search, and alpha-beta search/pruning but in fact the implementation is what's now known as a "negamax" search. I wasn't previously aware of the term, and this is quite new to me. Anyway, it makes the code sweet and neat, and has contributed to the speed.

Awesome implementation Andrew! The 4-ply engine beats Video Chess engine hands down, which is also impressive. This is a challenging game -

love the black screen between moves.

Can you make this even more powerful with a 5 or 6 ply?? (don't mind waiting up to 7 minutes between moves).

I tried to play this on CRT with the Harmony flashcart but the screen went blank - do I need to upgrade the BIOS or get a new flashcart?

CapitanClassic · April 6, 2020

2 hours ago, Andrew Davie said:

Great! It's definitely a '2600

TY for reviewing and kind comments.

I think the implication is that they weren’t sure if this game was ARM assisted. If the ARM was performing the move selection, it wouldn’t be as impressive that the move search was so swift.

Voxel · April 6, 2020

3 hours ago, Andrew Davie said:

Here's the full source code in case anyone wants a look-see.

I guess it's old and on the Z80, but the old Sargon code may hold inspiration for the parts you've not yet reached:

http://web.archive.org/web/20070614114334/http://madscientistroom.org/chm/Sargon.html

+Andrew Davie · April 6, 2020

1 hour ago, CapitanClassic said:

I think the implication is that they weren’t sure if this game was ARM assisted. If the ARM was performing the move selection, it wouldn’t be as impressive that the move search was so swift.

Yes, well to be super-clear -- it is pure 6507 code.

+Andrew Davie · April 6, 2020

1 hour ago, Mr SQL said:

Awesome implementation Andrew! The 4-ply engine beats Video Chess engine hands down, which is also impressive. This is a challenging game -

love the black screen between moves.

Can you make this even more powerful with a 5 or 6 ply?? (don't mind waiting up to 7 minutes between moves).

I tried to play this on CRT with the Harmony flashcart but the screen went blank - do I need to upgrade the BIOS or get a new flashcart?

Yes, I can up the #plys to many. How long can you wait?

I currently have the limit set to 10, but would be able to do 20 or more if the universe survived long enough.

I think it's not Harmony compatible... probably RAM requirement...?

+Andrew Davie · April 6, 2020

1 hour ago, Mr SQL said:

Awesome implementation Andrew! The 4-ply engine beats Video Chess engine hands down, which is also impressive. This is a challenging game -

That's interesting. Beating Video Chess was one of my goals. I just haven't tested it yet.

How's the 3 ply version go?

+Andrew Davie · April 6, 2020

8 minutes ago, Voxel said:

I guess it's old and on the Z80, but the old Sargon code may hold inspiration for the parts you've not yet reached:

http://web.archive.org/web/20070614114334/http://madscientistroom.org/chm/Sargon.html

Thanks for that. Actually at the start I searched long and hard for the 6502 Sargon code, and would have gone with that had I found it. But now I'm where I'm at, I don't regret the work involved - it's been interesting. Chess programming has moved a long way from the Sargon days and besides - now I have something I can call my own!

Voxel · April 6, 2020

It certainly is yours.

Reminds me a little of Superquerg Chess on the A8, looks really basic but it's got attitude.

+Andrew Davie · April 6, 2020

Given I have not looked at the Sargon chess code, but made my decisions as to format/implementation seperately, it's quite interesting to see some overlap on my initial peek at the source...

; BOARD	-- Board Array. Used to hold the current position 
; of the board during play. The board itself
; looks like: 
; 	FFFFFFFFFFFFFFFFFFFF 
; 	FFFFFFFFFFFFFFFFFFFF 
; 	FF0402030506030204FF 
; 	FF0101010101010101FF 
; 	FF0000000000000000FF 
; 	FF0000000000000000FF 
; 	FF0000000000000060FF 
; 	FF0000000000000000FF 
; 	FF8181818181818181FF 
; 	FF8482838586838284FF 
; 	FFFFFFFFFFFFFFFFFFFF 
; 	FFFFFFFFFFFFFFFFFFFF 
; The values of FF form the border of the 
; board, and are used to indicate when a piece 
; moves off the board. The individual bits of 
; the other bytes in the board array are as
; follows:
; 	Bit 7 -- Color of the piece
; 	1 -- Black 
; 	0 -- White 
; 	Bit 6 -- Not used 
; 	Bit 5 -- Not used 
; 	Bit 4 --Castle flag for Kings only
; 	Bit 3 -- Piece has moved flag
; 	Bits 2-0 Piece type 
; 		1 -- Pawn 
; 		2 -- Knight
; 		3 -- Bishop 
; 		4 -- Rook 
; 		5 -- Queen 
; 		6 -- King
; 		7 -- Not used
; 		0 -- Empty Square

That's Sargon code.

It is clearly using a 10x12 board with -1 as the border. This is identical to how I implemented it.

Bit usage - bit 7 is colour in both. Bit 4 is also castle flag for both (!!). I used bit 6 for a "piece has moved" flag.

I also use bits 2-0 for piece type, but I have both a white pawn (1) and black pawn (2) with 0 as an empty square.

So I don't have a 7-- not used.

But still, a LOT of similarities!

+Andrew Davie · April 6, 2020

More Sargon code review - it is quite different in the implementation, though. Lots different.

The evaluation routine was interesting. It's trying to put a lot of chess knowledge into a score, so to speak...

; *************************************************************
; 	POINT EVALUATION ROUTINE
; *************************************************************
; FUNCTION:	--	To perform a static board evaluation and
; 				derive a score for a given board position
; 	CALLED BY:		--		FNDMOV
; 					EVAL
; 	CALLS:		--		ATTACK
; 					XCHNG
; 					LIMIT
; 	ARGUMENTS:		-- 		None
; *************************************************************
POINTS:	XRA	A	; Zero out variables
	STA	MTRL
	STA	BRDC
	STA	PTSL
	STA	PTSWI
	STA	PTSW2
	STA	PTSCK
	LXI	H,T1	; Set attacker flag
	MVI	M,7
	MVI	A,21	; Init to first square on board
PT5:	STA	M3	; Save as board index
	LIXD	M3	; Load board index
	MOV	A,BOARD(X)	; Get piece from board
	CPI	-1	,Off board edge ?
	JZ	PT25	; Yes - jump
	LXI	H,P1	; Save piece, if any
	MOV	M,A
	ANI	7	; Save piece type, if any
	STA	T3
	CPI	KNIGHT	; Less than a Knight (Pawn) ?
	JRC	PT6X	; Yes - Jump
	CPI	ROOK	; Rook, Queen or King ?
	JRC	PT6.B	; No - jump
	CPI	KING	; Is it a King ?
	JRZ	PT6AA	; Yes - jump
	LDA	MOVENO	; Get move number
	CPI	7	; Less than 7 ?
	JRC	PT6A	; Yes - Jump
	JMP	PT6X	; Jump
PT6AA:	BIT	4,M	; Castled yet ?
	JRZ	PT6A	; No - jump
	MVI	A,+6	; Bonus for castling
	BIT	7,M	; Check piece color
	JRZ	PT6D	; Jump if white
	MVI	A,-6	; Bonus for black castling




Image of page 50 for reference


	JMP	PT6D	; Jump
PT6A:	BIT	3,M	; Has piece moved yet ?
	JRZ	PT6X	; No - jump
	JMP	PT6C	; Jump
PT6B:	BIT	3,M	; Has piece moved yet ?
	JRNZ	PT6X	; Yes - jump
PT6C:	MVI	A,-2	; Two point penalty for white
	BIT	7,M	; Check piece color
	JRZ	.+4	; Jump if white
	MVI	A,+2	; Two point penalty for black
PT6D:	LXI	H,BRDC	; Get address of board control
	ADD	M	; Add on penalty/bonus points
	MOV	M,A	; Save
PT6X:	XRA	A	; Zero out attack list
	MVI	B,14
	LXI	H,ATKLST
	MOV	M,A
	INX 	H
	DJNZ	.-2
	CALL	ATTACK	; Build attack list for square
	LXI	H,BACT	; Get black attacker count addr
	LDA	WACT	; Get white attacker count
	SUB	M	; Compute count difference
	LXI	H,BRDC	; Address of board control
	ADD	M	; Accum board control score
	MOV	M,A	; Save
	LDA	P1	; Get piece on current square
	ANA	A	; Is it empty ?
	JZ	PT25	; Yes - jump
	CALL	XCHNG	; Evaluate exchange, if any
	XRA	A	; Check for a loss
	CMP	E	; Points lost ?
	JRZ	PT23	; No - Jump
	DCR	D	; Deduct half a Pawn value
	LDA	P1	; Get piece under attack
	LXI	H,COLOR	; Color of side just moved
	XRA	M	; Compare with piece
	BIT	7,A	; Do colors match ?
	MOV	A,E	; Points lost
	JRNZ	PT20	; Jump if no match
	LXI	H,PTSL	; Previous max points lost
	CMP	M	; Compare to current value
	JRC	PT23	; Jump if greater than
	MOV	M,E	; Store new value as max lost
	LIXD	MLPTRJ	; Load pointer to this move
	LDA	M3	; Get position of lost piece
	CMP	MLTOP(X)	; Is it the one moving ?
	JRNZ	PT23	; No - jump
	STA	PTSCK	; Save position as a flag
	JMP	PT23	; Jump

PT20:	LXI	H,PTSW1 ;	Previous maximum points won
	CMP	M ;	Compare to current value
	JRC	.+4 ;	Jump if greater than
	MOV	A,M ;	Load previous max value
	MOV	M,E ;	Store new value as max won
	LXI	H,PTSW2 ;	Previous 2nd max points won
	CMP	M ;	Compare to current value
	JRC	PT23 ;	Jump if greater than
	MOV	M,A ;	Store as new 2nd max lost
PT23:	LXI	H,Pl ;	Get piece
	BIT	7,M ;	Test color
	MOV	A,D ;	Value of piece
	JRZ	.+4 ;	Jump if white
	NEG ;		Negate for black
	LXI	H,MTRL ;	Get addrs of material total
	ADD	M ;	Add new value
	MOV	M,A ;	Store
PT25:	LDA	M3 ;	Get current board position
	INR	A ;	Increment
	CPI	99 ;	At end of board ?
	JNZ	PT5 ;	No - jump
	LDA	PTSCK ;	Moving piece lost flag
	ANA	A ;	Was it lost ?
	JRZ	PT25A ;	No - jump
	LDA	PTSW2 ;	2nd max points won
	STA	PTSW1 ;	Store as max points won
	XRA	A ;	Zero out 2nd max points won
	STA	PTSW2
PT25A:	LDA	PTSL ;	Get max points lost
	ANA	A ;	Is it zero ?
	JRZ	.+3 ;	Yes - jump
	DCR	A ;	Decrement it
	MOV	B,A ;	Save it
	LDA	PTSW1 ;	Max,points won
	ANA	A ;	Is it zero ?
	JRZ	.+11. ;	Yes - jump
	LDA	PTSW2 ;	2nd max points won
	ANA	A ;	Is it zero ?
	JRZ	.+5 ;	Yes - jump
	DCR	A ;	Decrement it
	SRLR	A ;	Divide it by 2
	SUB	B ;	Subtract points lost
	LXT	9,COLOR ;	Color of side just moved
	BIT	7,M ;	Is it white ?
	JRZ	.+4 ;	Yes - jump
	NEG ;		Negate for black
	LXI	H,MTRL ;	Net material on board
	ADD	M ;	Add exchange adjustments
	LXI	H,MVO ;	Material at ply 0

	SUB	M ;	Subtract from current
	MOV	B,A ;	Save
	MVI	A,30 ;	Load material limit
	CALL	LIMIT ;	Limit to plus or minus value
	MOV	E,A ;	Save limited value
	LDA	BRDC ;	Get board control points
	LXI	H,BCO ;	Board control at ply zero
	SUB	M ;	Get difference
	MOV	B,A ;	Save
	LDA	PTSCK ;	Moving piece lost flag
	ANA	A ;	Is it zero ?
	JRZ	.+4 ;	Yes - jump
	MVI	B,0 ;	Zero board control points
	MVI	A,6 ;	Load board control limit
	CALL	LIMIT ;	Limit to plus or minus value
	MOV	D,A ;	Save limited value
	MOV	A,E ;	Get material points
	ADD	A ;	Multiply by 4
	ADD 	A
	ADD	D ;	Add board control
	LXI	H,COLOR ;	Color of side just moved
	BIT	7,M ;	Is it white ?
	JRNZ	.+4 ;	No - jump
	NEG ;		Negate for white
	ADI	80H ;	Rescale score (neutral = 80H
	STA	VALM ;	Save score
	LIXD	MLPTRJ ;	Load move list pointer
	MOV	MLVAL(X),A ;	Save score in move list
	RET ; 		Return

My game has none of that.

All I do (so far) is keep a track of relative material value, and the position value of each piece. That's it.

I do this incrementally as pieces move, so there isn't actually a "score" function per-se. The score is "evaluated" pretty much as part of making a move. So it's quite, quite different.

Anyway, I'm sure things will evolve.

+Andrew Davie · April 6, 2020

2 hours ago, Mr SQL said:

Can you make this even more powerful with a 5 or 6 ply?? (don't mind waiting up to 7 minutes between moves).

Here's a 5 ply version. I have also slightly tweaked the position value tables, so it will play quite differently. Maybe.

I don't really know how long it will take to do moves. 10-30 minutes is my guess.

chess_20200407_5ply.bin

+fdr4prez · April 6, 2020

How does your AI engine determine if the pawn moves one spot or two? Are they equal priority?

Mr SQL · April 6, 2020

1 hour ago, Andrew Davie said:

That's interesting. Beating Video Chess was one of my goals. I just haven't tested it yet.

How's the 3 ply version go?

1 hour ago, Andrew Davie said:

Yes, I can up the #plys to many. How long can you wait?

I currently have the limit set to 10, but would be able to do 20 or more if the universe survived long enough.

I think it's not Harmony compatible... probably RAM requirement...?

46 minutes ago, Andrew Davie said:

Here's a 5 ply version. I have also slightly tweaked the position value tables, so it will play quite differently. Maybe.

I don't really know how long it will take to do moves. 10-30 minutes is my guess.

chess_20200407_5ply.bin 32 kB · 1 download

I haven't tried the 3 ply version yet but I will try it after the 5 ply which I am about to play - thank you!

I usually play Video Chess on the setting where it takes up to 10 minutes to move, level 4 or 6 I think. Taking longer for Video Chess doesn't seem to improve it's Chess game further and I start to lose continuity.I rate Video Chess at 1400 which is a good player similar to the 1977 Fidelity Chess Challenger; I move in about 10 seconds or less when letting Video Chess wait 10 minutes for a challenging game. I have to take my time with your engine which is awesome - I need to play many more games to let you know the rating

This game is a good reason to get an upgraded Flashcart - I'm guessing it will run on both the Encore and the UNO since it is pure 6502?

+Andrew Davie · April 7, 2020

7 hours ago, fdr4prez said:

How does your AI engine determine if the pawn moves one spot or two? Are they equal priority?

It's all very complicated.

Consider a search tree. That is, list all the moves, choose one of them, "make" the move so we are now the opponent. Now list all the moves, choose one of them, "make" the move, so now we're two levels "deep" in a search tree, and now we're the player again. Repeat until we're some particular depth - let's say 4 levels down. That's the reply to the reply to the reply to a move that the player could have made.
Now we're down at the very bottom of one possible branch (of hundreds of thousands, or even millions), we need to give this "leaf node" a score. We need a numerical score so that we can figure out which of those possible moves at the very bottom of our (upside down) tree is the best one.
Now in particular answer to your question, I have an "evaluation" score which is updated as you go down the tree of possibilities. It has only two components at the moment - the first being the sum of the value of the material. Pawns are worth 100, knight is 325, bishop 350, etc. So +white pieces and - black pieces gives a material value. And secondly, the square each piece is on is rated as to its value. But its value depends on the piece type. So I have tables that give me the value of, say, a white pawn being on square E4, or on E3, or on A8... all the possibilities for all the pieces. These position values are added to the evaluation score.
So, now we're at a leaf node and have a score for that node, we can compare that score against all the other possible moves that could have been made on the level just before that leaf node, given that the goal is to maixmise the score. So, of the (say) 30 possible moves, we find the maximum score, and say "well, given a choice, the move that lead to that maximum score is the one to choose".
Now it gets more complex. We backtrack one of those levels, to the one higher above. Now we've just completed looking at a single move on that level (of, say, 30) and we know that if we make that move it will lead to a maximum possible score just determined. Great. So let's repeat for all the other moves. That is, make the move, then look at all moves possible from that point, and score them. We get another "best possible score is..." which we can compare to the first one we had. In other words, the same process as describe before, but one level "higher" in the (upside-down) tree.
In this way, on every level, and for all possible move combinations, we end up finding the best possible move (from the perspective of player about to move on each level). Eventually, after a gazillion move/move/move/score sort of traversal of the "move tree", we are back at the first level and we know the best move.
Now, back to your question. The determination as to if to move one spot or two is based on the above process. Given any board position, the decision on how to make ANY move is based on the idea that my opponent will choose the worst move for me, and that is based on me choosing the worst move for him, which is based on him choosing the worst move for me. And so on, down the tree. Any move that is selected at the root of the tree is thus the best of the worst of the best of the worst..... right down to the leaf nodes. IN other words, it's complex. And at any point it's hard to say WHY a particular move is chosen unless you are very good at understanding the process.

The short answer to your question; all things being equal, the E4 square is given a slightly higher score than the E3 square, for example. That tends, in the long run, to advantage moving two squares. But it does depend on the opponent's position. Greatly.

Edited April 7, 2020 by Andrew Davie

+fdr4prez · April 7, 2020

So you do not want to tell us you secret, eh?

I get it, thanks. quite detailed explanation.

Does it fall for the three move checkmate?

+Andrew Davie · April 7, 2020

Just now, fdr4prez said:

So you do not want to tell us you secret, eh?

I get it, thanks. quite detailed explanation.

Does it fall for the three move checkmate?

Again, complex.

There is something called "quiescence" which is not yet fully working.

That is a process where, at the very bottom of the search tree... if the last move was a capture, then it goes even deeper. Since checkmates are usually preceeded by some capture moves, the quiescence will generally allow it to "see" impending checkmates - and thus, avoid them if possible. The longer answer is - it will be doing everything possible to maximise its score - so that includes not getting into a positoin where three move checkmate is possible.
The short answer - if you have overwhelmed it and hold significant material advantage, then you can checkmate it.

But it will not "fall" for three move checkmate. That's unlikely.

+Andrew Davie · April 8, 2020

I've been brushing up a little on modern chess programming techniques. Quite a lot has changed, really. Particularly with negamax search, and windows for alpha-beta pruning. I am not sure I will get into that much depth once it's playing "well" but in any case it's all interesting stuff. A bit hard to understand, sometimes. I've also been playing with a few things, such as sorting the moves (a big failure, but will revisit), and adding stuff to the evaluation. In the attached binary, it is adding the "mobility" to the score. Or more particularly, subtracting the mobility of the opponent. It does make it play differently, at a bit of time cost. Everything is going to be related to time cost from hereon-in. My earlier comments about avoiding mate-in-3 were probably incorrect. The more I play the more I find ways to beat this current engine easily. You just have to understand what it's doing. For example, if I attack its queen with a pawn, it is more likely to do a piece sacrifice than just move the queen away. Why? Because it doesn't see that the piece sacrifice is just that - losing a piece. It just sees the "win" of the piece it takes when doing the sacrifice. This will all be "totally" resolved when I get the quiescence search functional. It's written, I'm just having an "impossible task" moment with that code. I can't bring myself to spend time getting it properly integrated. But I can see now, how much of a difference it will make to gameplay (absolutely huge). So, I guess... that's next.
Anyway, here's that binary... the one that uses mobility as part of evaluating the positions...

chess20200407_mobility.bin

Chess

Recommended Posts

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Join the conversation

Recently Browsing 0 members