Chess

[+Al_Nafuur]

1 hour ago, Andrew Davie said:

But the AtriVox doesn't talk. I don't understand it. It's almost as like there's a hardware bug in the 3E+... I'm that paranoid.

Which hardware are you using?

Unfortunately i don't have an AtariVox to test your build on the PlusCart.

 

Just because you're paranoid doesn't mean they aren't after you..
(Joseph Heller)

Edited July 17, 2020 by Al_Nafuur

[+Andrew Davie]

1 minute ago, Al_Nafuur said:

Which hardware are you using?

Unfortunately i don't have an AtariVox to test your build on the PlusCart.

Sorry, that was muddy thinking from me. I meant a software bug in the Stella 3E+ implementation.

I will test the non-working code on hardware shortly - it didn't occur to me that this might be software-only bug until a short while ago.

 

[+Andrew Davie]

Now that the bugs I knew about are (mostly) gone, I'm going to try a bit of an experiment with the move ordering. Basically, when you generate a list of moves, the moves are in some fairly un-sorted state.  That is, they are most likely - almost certainly - not ordered best to worst. That's the order you want, because this enables the alpha-beta cutoffs in the search to perform efficiently and discard most branches of the search tree. One optimisation the current code does is to put capture moves first in the list of moves. That is, after the moves are generated by "GenerateAllMoves", a simple scan is made to find any moves that involve a capture, and put these at the head of the movelist.

So, when you see "obvious" moves for the computer involving a capture, generally these moves are made very quickly. That's because the alpha-beta pruning is pretty much discarding every other move relatively quickly. Only when we have a complex position, where the actual best move is not early on, does the search have to do lots of work visiting thousands of possible nodes to try and find the best move.

 

So, for this reason, having those moves in a sorted state is pretty useful.  In fact, it's worth spending a fair amount of time just sorting. I've touched on this before - how can you sort based on position value, when you don't know the position value until you've searched. And the answer is... search.  But, not quite as deeply as when you're "actually" searching.

So, as a prelude to this, my next experiment is to put in a single-ply search in.  That is, "GenerateAllMoves", and then make each move, evaluate, unmake-the move. I already have the "score" for each move stored, so I just need to do a 1-ply search (with quiescence, I'm thinking), and then sort the moves based on the score. And then finally do the original search that was planned (say, 3-ply).  I am predicting, well fairly certain, that the 1-ply search + sort + 3-ply search will be much, much faster than just the 3-ply search by itself.  In fact, let's toss a figure into the ring - my crystal ball tells me that I'll be able to do a 4-ply search as quickly as I currently do a 3-ply search.  So, that's about 30 times faster.
 

Something to aim for, anyway.  So, that's the plan.

 

[Prizrak]

Which hardware are you using?
Unfortunately i don't have an AtariVox to test your build on the PlusCart.
 
Just because you're paranoid doesn't mean they aren't after you..
(Joseph Heller)

I have an Atarivox but the box only talks when the Atari turns on, after pluscart loads there is no further talking unless the game sends code to the Atarivox to talk.

Sent from my SM-N960U using Tapatalk

[+Andrew Davie]

Tomorrow I will build a 3E+ test version of the AtariVox demo/test program.

I'll make it conditionally compiled so it can either be a 4K or 3E+ binary, and then test it runs on Stella and on hardware.

Will report back ASAP.

 

[+Pat Brady]

17 hours ago, Andrew Davie said:

So, when you see "obvious" moves for the computer involving a capture, generally these moves are made very quickly. That's because the alpha-beta pruning is pretty much discarding every other move relatively quickly. Only when we have a complex position, where the actual best move is not early on, does the search have to do lots of work visiting thousands of possible nodes to try and find the best move.

 

So, for this reason, having those moves in a sorted state is pretty useful.  In fact, it's worth spending a fair amount of time just sorting. I've touched on this before - how can you sort based on position value, when you don't know the position value until you've searched. And the answer is... search.  But, not quite as deeply as when you're "actually" searching.

 

Just brainstorming. Maybe you’ve thought of this, and maybe I don’t understand the algorithms well enough. But wanted to mention it just in case.

 

Why not score and sort at each ply? IOW at ply N (where you are considering a single node from ply N-1), score and sort the new nodes before proceeding to ply N+1. I think this along the same lines as your idea of starting with a 1-ply search, but it does it at every ply without repeating plies.

 

With that approach, the evaluator need not score the board fully at each node. It can take the parent node’s score, subtract the old positional value of the piece being moved, add that piece’s new positional value, and if it’s a capture, account for the material and positional value of the captured piece.

[+Andrew Davie]

2 minutes ago, bizarrostormy said:

 

Just brainstorming. Maybe you’ve thought of this, and maybe I don’t understand the algorithms well enough. But wanted to mention it just in case.

 

Why not score and sort at each ply? IOW at ply N (where you are considering a single node from ply N-1), score and sort the new nodes before proceeding to ply N+1. I think this along the same lines as your idea of starting with a 1-ply search, but it does it at every ply without repeating plies.

 

With that approach, the evaluator need not score the board fully at each node. It can take the parent node’s score, subtract the old positional value of the piece being moved, add that piece’s new positional value, and if it’s a capture, account for the material and positional value of the captured piece.

 

 

 

There's some good thinking there, thanks.

 

Firstly, the scoring as it is is incremental already. I just keep a global value "Evaluation" and as a move is made I adjust that. I adjust both material values and positional values, based on captures, promotions, etc. So the game is not calculating all the values of all the pieces ever ply --- it is calculating just the changes.  So that covers your last point - already being done.

 

Next, "why not score and sort at each ply".  Yes, this is the plan. But you have to actually do a 1-ply "search" (that is, make each move) before you have the scores which you can then use to sort the moves.  Your concept in the last paragraph is effctively making a move, modifying the incremental score, and then un-making the move. And then sorting.

 

So you're suggesting exactly what is already happening insofar as a 1-ply search, sort, then a deeper search. Although I hadn't explicitly mentioned doing this at every ply, that is planned. But first I want to do it only at the very top level to see how much of a difference it makes to speed.

 

[+fdr4prez]

[+Andrew Davie]

A few tweaks; specifically, some work on adding the mobility component back to the evaluation routine.

I'm reasonably impressed with the quality of the games this has been playing (4-ply, 3-quiescence).

So, would welcome some feedback from others.  It's about a minute/move, give or take.

 

 

chess3E+20200722_4PQ3.bin

[Gray Defender]

14 minutes ago, Andrew Davie said:

A few tweaks; specifically, some work on adding the mobility component back to the evaluation routine.

I'm reasonably impressed with the quality of the games this has been playing (4-ply, 3-quiescence).

So, would welcome some feedback from others.  It's about a minute/move, give or take.

 

 

chess3E+20200722_4PQ3.bin 32 kB · 3 downloads

Might just be me, but I cannot seem to control this one with joystick.  The previous one is working for me... 

[+Andrew Davie]

1 minute ago, Gray Defender said:

Might just be me, but I cannot seem to control this one with joystick.  The previous one is working for me... 

Odd. I just tried the binary with stella 6.1 and 6.2 and works OK for me.

Just as a test, press SELECT - the computer should make a move (as white) and then see if you can move the black pieces.
Let's see if others have problems.

[Gray Defender]

Okay I am using Stella 6.1.2 It starts like I already pressed the button and does not respond, even pressing F1, F2.  Like I said maybe something on my end. Cursor is flashing though and other games are working.

 

 

[+Andrew Davie]

Just now, Gray Defender said:

Okay I am using Stella 6.1.2 It starts like I already pressed the button and does not respond, even pressing F1, F2.  Like I said maybe something on my end...

 

 

 

Yes, that definitely is behaving as if the button is pressed/held already.

I can't offhand think of any coding error that would cause that, but it's likely. Mmmh.

 

[+Karl G]

No movement issues for me, FWIW.

[Gray Defender]

I reinstalled installed stella... Working again.. That was weird...

[+Andrew Davie]

Just a reminder - if you want to 'cheat' by not waiting for the computer to make its moves there are two ways

 

1) turn on "turbo" mode when computer is moving - just press Ctrl-T to enable, and then again to disable when it's your move.

2) press SELECT to force computer to make its current best choice. This is pretty unfair to the computer, but does work.

 

In other words, no need to wait if you don't want to.

 

[+Al_Nafuur]

1 hour ago, Andrew Davie said:

A few tweaks; specifically, some work on adding the mobility component back to the evaluation routine.

I'm reasonably impressed with the quality of the games this has been playing (4-ply, 3-quiescence).

So, would welcome some feedback from others.  It's about a minute/move, give or take.

chess3E+20200722_4PQ3.bin 32 kB · 8 downloads

No movement issues for me on PlusCart.

 

8 minutes ago, Andrew Davie said:

Just a reminder - if you want to 'cheat' by not waiting for the computer to make its moves there are two ways

 

1) turn on "turbo" mode when computer is moving - just press Ctrl-T to enable, and then again to disable when it's your move.

2) press SELECT to force computer to make its current best choice. This is pretty unfair to the computer, but does work.

 

In other words, no need to wait if you don't want to.

 

Where can i find this "Ctrl-T" on my PAL 2600jr. ?

[+Andrew Davie]

Just now, Al_Nafuur said:

No movement issues for me on PlusCart.

 

Where can i find this "Ctrl-T" on my PAL 2600jr. ?

For 2600JR systems you have to pull out the 6502 and replace it with an ARM.

 

[devwebcl]

I am not sure if I already asked, but did you use any book as a reference to implement a chess engine?

[+Andrew Davie]

Just now, devwebcl said:

I am not sure if I already asked, but did you use any book as a reference to implement a chess engine?

 

No, I did not.

 

I did lookup some basic pseudocode of the negamax algorithm after I realise I had "independently" invented it. Then I rewrote it to the more efficient scheme represented by the pseudocode. Much of the basic functionality in chess engines these days is "stock standard", so I'm not doing anything groundbreaking or terribly original here.  Perhaps the originality is warping the algorithms into the bankswitching capabilities of the 3E+ scheme, where I am able to benefit from certain optimisations to improve speed.

And finally, I have followed computer chess for literally decades. I used to go to the physical library in the late '70s to find books on chess programming, so in that sense I guess the answer to your question would be "yes" - at least for the first two engines I wrote in the 1980s. But as I took from your question's context; for this engine, no - no books were consulted.

 

[+Al_Nafuur]

1 hour ago, Andrew Davie said:

For 2600JR systems you have to pull out the 6502 and replace it with an ARM.

 

This place here is full of tinkerers, i wouldn't say that too loud in here.. ?

[devwebcl]

11 minutes ago, Andrew Davie said:

 

No, I did not.

 

I did lookup some basic pseudocode of the negamax algorithm after I realise I had "independently" invented it. Then I rewrote it to the more efficient scheme represented by the pseudocode. Much of the basic functionality in chess engines these days is "stock standard", so I'm not doing anything groundbreaking or terribly original here.  Perhaps the originality is warping the algorithms into the bankswitching capabilities of the 3E+ scheme, where I am able to benefit from certain optimisations to improve speed.

And finally, I have followed computer chess for literally decades. I used to go to the physical library in the late '70s to find books on chess programming, so in that sense I guess the answer to your question would be "yes" - at least for the first two engines I wrote in the 1980s. But as I took from your question's context; for this engine, no - no books were consulted.

 

Cool story, similar to mine, however still I need to write/finish an engine

 

[+Andrew Davie]

As an analogy for how my day's been, I present this 4-move loss for white...
 

Sometimes every decision you make is not only doomed to failure, but also the worst possible one
All good, just a drab day.

 

[+Andrew Davie]

I have a few ideas I'd like to work on, one of which in particular I thought might pose a fun challenge for you, dear reader.

 

That one is where I would like to save the board position to the SaveKey/AtariVox, so that you can turn off the game at any time, and when you turn back on again, you have the board position where you left off.

 

So, let's assume there are just 64 bytes available for storage.  How do you efficiently save...

 

a) The pieces and their positions (all 32 of them)

b) whose turn it is to move

c) en-passant status for any relevant pawn

d) castling status for each side (and if the relevant king/rook has moved)

e) ragequit bit - see below

 

I'd like to keep some of those 64 bytes for other stuff, so let's budget (say) 48 bytes for the above.

Challenge: come up with an incredible and brilliant encoding scheme and get credit in the manual

 

Other things I might be tackling in the next few days...

 

 

a) Record the moves during the game.

b) Implemente RESET = resign.

c) After a game is over (you win, or computer wins, or you resign), then RESET = start new game, and SELECT = review

d) Implement review - this allows you to step through all the moves of a game from the beginning.

e) Save a flag/bit to saveKey/AtariVox indicating game is in progress - the "ragequit" bit. The purpose of this is to allow the game to detect if a game has been aborted (by power-off) mid-game.  This could be used to prevent rage-quitting (by restoring the board), or to react to a rage-quit.

 

 

[+Pat Brady]

2 hours ago, Andrew Davie said:

I have a few ideas I'd like to work on, one of which in particular I thought might pose a fun challenge for you, dear reader.

 

That one is where I would like to save the board position to the SaveKey/AtariVox, so that you can turn off the game at any time, and when you turn back on again, you have the board position where you left off.

 

So, let's assume there are just 64 bytes available for storage.  How do you efficiently save...

 

a) The pieces and their positions (all 32 of them)

b) whose turn it is to move

c) en-passant status for any relevant pawn

d) castling status for each side (and if the relevant king/rook has moved)

e) ragequit bit - see below

 

I'd like to keep some of those 64 bytes for other stuff, so let's budget (say) 48 bytes for the above.

Challenge: come up with an incredible and brilliant encoding scheme and get credit in the manual

 

I’m probably missing something, but:

 

A1. 32 bytes. Choose any order for the pieces and any order for the 256 squares. Store the position for each piece in order by piece. Removed pieces are marked with the same position as that side’s king.

 

A2. 8 bytes. Each pawn (in same order as above) has an extra (beyond its position byte) nibble. 1 bit stores whether it may be captured en passant. Another bit stores whether it has been promoted. The other 2 bits encode what it was promoted to (queen, rook, bishop, knight).

 

B. 1 byte. Have a byte for game status. Bit 7 is 0 if it is white’s turn, 1 if black’s.

 

C. Use bits 2-5 in game status for castling, one for each rook. Each bit is 1 if the corresponding rook has moved. If the king has moved or the player has castled, both of the bits for that player are 1.

 

D. Bit 6 in game status is 1 if ragequit.

 

41 bytes, with 2 bits of game status still available.

 

Edited July 24, 2020 by bizarrostormy