Kingslayer Chess - New beta release version 1.0 available

[Peer]

Kingslayer Chess

Let me know what you think.

Many Cheers,

Peer

[TrekMD]

Oh, wow. Very nice!

[vectrexmad]

Thank you for bringing a different game genre to the Vectrex.

Having tried to write a chess program many years in the past (in BASIC for a Sony PS2) and ending up with a weak solution, I can really appreciate the complexities of trying to fit any sort of game resembling chess into the Vectrex. Recently, there’s been a Vectrex chess game demonstrated but using an external CPU (Pitrex) to do all the grunt work.

So it is remarkable to see a version of chess that is currently just 13K ROM in size. Considering the Vectrex has less than 1K of useable RAM available, I can really understand the limitations imposed on the programmer.

First off, it’s fitting to hear the national royal anthem!

It is good that there is a calibration screen to allow the player to adjust the pieces on the board. I’m sure this game appears perfect on an emulator, but on the two Vectrex consoles I tested, I do see a waviness of the gridlines. The pieces look static, so I am wondering if there need to be a few more reset0ref()’s between the line drawing points? An alternative is to get rid of the board lines, and put the chequered board on an overlay, this would help with the game goal to draw with optimum frame rate.

The input and chess piece selection is really strong. It is not possible to make an illegal move. It is good that during each calculation of the Vectrex move, a bar is shown giving the status of the move calculation.

Out of all the times, I played Kingslayer Chess I was able to beat it. I think this is understandable because of the limitations of the Vectrex. The limited memory does not allow the Vectrex to have a big look forward at all the possible permutations.

The random move mode is not very entertaining but I’m guessing you implemented this first to test out their chessboard input and output engine. I played mostly "AI 2" mode so far as that was a good compromise between game intelligence and speed of moves. "Deep Thought" mode took a really long time for each move, even against a simple pawn move at the start. Maybe, when I have more time I will try this mode as the title infers the gameplay is likely to be more challenging.

I appreciate this work is an experiment and the programmer was trying out different algorithms. The setup options allow the player to select different gameplay intelligence and it's even possible for the Vectrex to play itself.

Would be nice if there was an option (say button 1) where you could have the option of quitting the game.

Overall, a very good effort for version 0.2! I suspect what appears on the surface is hiding a lot of complex programming aspects underneath. Really enjoyed testing this game.

[Peer]

Hi guys,

thank you both for your feedback and for trying out the prototype!

Here are some further explanations regarding the implementation:

The whole thing started out as a performance experiment which only later turned into a playable version of chess. I was primarily interested in how difficult it would be to implement the standard Minimax chess AI algorithm in a way that allows the complete board and all pieces to be kept in view on the Vectrex screen at all times.

Minimax can rather easily (well, sort of…) be implemented by using recursion, but its recursive form makes it unsuitable for the Vectrex's draw-everything-in-each-50Hz-frame requirement. So the fun was to break down Minimax into a state-machine-form that executes one slice of the algorithm in each frame. I deliberately chose not to have the board imprinted on the overlay, but to truly draw it in vector form, just like all the other pieces. That was part of the challenge.

Of course, drawing everything, especially also the board, has a negative impact on the overall performance of the AI computation, as there are only some few 1000 cycles left for this in each frame. The whole experiment is a bit academic in nature and probably of less practical value, but hey, there is a reason why I called my Vectrex lab page "Weird Science"

I have not yet tweaked the Minimax algorithm to make it any smarter. Currently it is just the standard algorithm with a very simple board evaluation function. There are lots of known heuristics I could try to improve this, but I am a lousy chess player myself, so it would be rather hard for me to judge if the program had become any smarter or dumber. I am pretty sure that the program will never be able to beat any serious chess player, no matter what I tried. But I think and hope it will still provide some fun for amateur or novice players, or maybe even for kids who are just about to learn the rules of chess. And for that, I think, it is good to have to board displayed at all times.

I added the "random moves" opponent just for testing purposes, and also because it was fun and easy and cost virtually nothing. Also, I found it quite amusing to watch the other AIs play against it.

There are actually 3 different AIs, corresponding to Minimax levels (depths) 1, 2 and 3:

• WOPR  –  calculate the best move based on the current board situation only
• HAL 9000  –  calculate the best move based on the current board situation while also taking into account all possible subsequent opponent moves
• Deep Though – calculate the best move based on the current board situation that allows the best possible next move after any possible subsequent opponent move
  

What is considered to be "the best move" depends on the board evaluation function. Right now, I am using a rather simple one here which counts the values of the present pieces and also takes into account the grid position of each pieces on the board.

I found that Minimax level 4 just takes too long on 8 bit hardware, even when run with 100% CPU and without any drawing, so I did not add any further AI.

I did not encounter any shaky or wobbling vectors on my console. All vector lists drawn have their proper Reset0Ref(), so I would be interested in learning more about any waviness of the grid lines or any wobbling of the pieces. Especially, if this happen with the default settings, or only after calibrating the screen by means of the setup menu entry.

Some more trivia: The current implementation uses some 350 bytes RAM only (plus some few 30 bytes on the system stack), so there is still a lot of RAM available. The current ROM size of roughly 13K could probably be reduced to, I don’t know, maybe 10K? I have not size-optimized the code in any way and there are several redundant parts in it.

Regarding a possible 0.3 version, I will add a switch-off-the-screen-during-AI-computation mode, so that you can experience the performance of the AI computation at CPU 100% usage. I will probably also try to improve the board evaluation function, to make the AI a bit smarter, but I am afraid that I am too bad at chess myself to really tell.

Many Cheers,
Peer

[hcmffm]

Thank you, for Kingslayer chess, Peer, which is another nice project which again came out of nowhere. Your above explanations regarding AI and difficulties are quite interesting to read. Personally, I played chess when I was juvenile. I never tried playing on a computer because I find the design of the chessman and view of a virtual chessboard irritating and an extra challenge. Perhaps I should just give it a try and see whether I can beat the AI.

Anyway, I wish you good fun, many "Aha!" experiences and new expertise with this Vectrex project, Peer!

[drsnuggles]

OK, i was giving it a try. Haven't played chess since Battle Chess.
Was hoping that WOPR will be about Tic Tac Toe difficulty and thanks Peer. It was fun!!!! 
White = WOPR

and WOPR did more such moves

OK, i was also lazy but end game looks promising

I love WOPR. I won and found that WOPR was not detecting check by my queen instead moved a pawn.
Only had emu for playing but interface was intuitive and easy to use.
The symbols are easy to distinguish.

Sorry for screenshots without overlay. Just started playing...

Thanks Peer!

[Peer]

Jun 8, 2021 14:02:23 GMT -5 drsnuggles said:

I love WOPR. I won and found that WOPR was not detecting check by my queen instead moved a pawn.

Glad you enjoyed the game!

Yes, WOPR does only compute its own best move based on the present only, and does not take into account any subsequent future opponent moves (Minimax level 1). If you want the AI a tiny bit smarter, then try HAL 9000 (Minimax lelvel 2). But be careful, HAL won't open the pod bay door for you!

Cheers,

Peer

PS: Right now I am working on version 0.3, which will have improved performance, and also offer AI 4 - UNIVAC, which will implement Minimax level 4.

[Peer]

FYI: Just detected a small bug in the AI computation, causing the pawns sometimes not to make the strongest possible move. The fix will be part of version 0.3.

Edit: Argh, this was caused by one missing "break" inside a "switch-case" statement. Fixed now.

[Peer]

Greetings everyone,

I have uploaded a new and completely revised and enhanced version of Kingslayer Chess. This is now beta release version 1.0.

These are the most recent changes compared to the previous version:

• Code has been optimized for performance, significant speed up of AI computations.
• Alpha-Beta pruning of the minimax-algorithm improved by adding one (simple) heuristics.
• Load-balancing introduced. The AI state-machine observes Timer 2 and schedules its computations so that a 50Hz framerate is maintained at all times (well, there might still be some occasional spikes). This can be nicely observed in Vide.
• AI levels 4 to 6 added. AI levels 1 to 3 do their computations rather quickly, 4 is acceptable, 5 and 6 are mainly included just for performance tests.
• Choice between board-view and progress-view during AI computation, see description on the project web page.
  
• Choice to let the AIs open a game by up to 3 random moves. This provides for a lot more variety and a means to quickly start an (interesting?) game, as AI computations are otherwise mainly deterministic (same situation on the board will lead to same decision of the AI).
• Choice between two different board evaluations functions (AI types). Type A is default and well tested, type B is highly experimental.
• Some bugs fixed which caused the AIs of the previous version to do some silly stuff on rare occasions.

It would be cool to get some feedback, especially if someone has a go against AIs 3 and 4.

Many Cheers,

Peer

[D-Type]

Nice to see some updates!

I'll give it a go over the weekend. It's probably worth trying it against some of the bot's on chess.com or lichess.com, I've not played chess since I was a kid but was able to beat them quite easily.

There are lots of different strengths available and on the two games I just played against very low skilled bots, they didn't castle. (A good player or bot will usually castle pretty early on.)

[D-Type]

I played Kingslayer Level 3 against lichess.org Stockfish level 1 (which seems to make almost random moves), 10 minutes each side.

Kingslayer was winning, but was significantly down on time and therefore would have lost. But before that happened, it walked a pawn to get promoted and Stockfish will not let you keep your pawn, so I had to abandon.

Was looking good while it lasted, though!

[Peer]

Great, thanks a lot for testing, D-Type!

Knowing its simple implementation, letting it play against Stockfish already feels like an insurmountable challenge, but limiting thought time to 10 minutes rather makes it a suicide mission. Unless you compiled Stockfish for the 6809 and let it run at 1.5 MHz only

I will see what I can do about castling and pawn promotion.

It is not that I am lazy or unwilling. It is just that such things cannot be easily integrated into the current implementation of the state machine and would require completely rewriting major parts of the code. I won’t go into the details here, but right now everything is heavily optimized with respect to the simplified rules of chess, and with respect to being able to simultaneously draw something on the screen at a 50Hz framerate (which this experiment was all about in the beginning).

Many Cheers,

Peer

[D-Type]

I didn't choose 10 minutes deliberately, I just noticed it when I was playing.

I don't expect you to change anything, the fact it can play at all is a pretty big achievement! However...

Adding castling and pawn promotion might not affect your engine code, if a pawn gets to the other side, you can automatically change it to a queen, other 8-bit engines do that.

Ideally you'd get a choice of pieces, you don't always want a queen, a knight could be more useful and a queen can also put your opponent in a position where he can't move, thus causing an stalemate.

For castling, you just need to let the human do it, your engine doesn't have to castle.

[D-Type]

Oh yeah, en Passant, well, that's pretty rare, I'd ignore that one.

No possible move stalemate, 3x repetition stalemate, 50-move rule stalemate, they're all rare also.

[8-Bit Waves]

How did I miss this?!

While I'm not an amazing chess player, I do enjoy playing. I find vintage computer chess games/gadgets very interesting for some crazy reason so this makes me particularly happy.

Thank you so much for the effort, Peer. You a really pumping out the games lately!