Crap 0.1 first assembly project

Show us what you're working on, (preferably with screenshots).
Nomad
Manic Miner
Posts: 600
Joined: Thu Dec 28, 2017 12:38 pm

Re: Crap 0.1 first assembly project

Post by Nomad »

Update:

While not directly related to the project, the GAP programming language is very useful to anyone wanting to do maths with a computer. How it can be applied to the project - my looking for cyclical sequences can easily be handled by this program. It can generate thousands of sequences that will be extremely useful to creating music on the spectrum.

I really should have looked for this before, but I am a potato. Pretty much everything I was interested in using has already been created and is ready to use. I just have to hit a button and I get the data I want now. :lol:

This also is going to have a fairly large impact of what I can feasibly do - its greatly expanded the set of tools available. I now no longer need to implement half a dozen different algorithms to get the data I want. Its all done already. It completely changes the focus of what I am doing. I don't need to worry about implementation details. Very nice.

Even a potato can do a lot with such a system. :lol:
Nomad
Manic Miner
Posts: 600
Joined: Thu Dec 28, 2017 12:38 pm

Re: Crap 0.1 first assembly project

Post by Nomad »

Day 55, 310 days left!

Today project time was spent refactoring crap chess. (sound familiar.) :lol: One sentence covers a lot of work. So.. time to elaborate...

This might not be the most straight forward way of refactoring/defining the problem but I figured why not.

I got to thinking why not define a program as a Set, and all of the parts of the program as cosets of the Program set. Then work my way down from there mapping the features of the subsets.

This turned out to be a very nice way of defining the program. By counting the subsets that had the same name (Like for example GAME INPUT, MENU INPUT, SCREEN A,...) I could figure out just by a simple count what subroutines would need to be focused on, optimized the most and what I could just leave till much later.

One thing that was obvious was the amount of data crap chess needs, and that its a big issue even doing it this way. Game data is one of the major components.

That said the microdrive essentially solves this problem. With the hacks that were revealed by the ZX computing article I am now confident this can be resolved.

I decided to switch the assembler I was using also. hate to be lazy but zeus being able to handle the keyboard input & masks is fantastic. That removes a major headache. Not using the full blown Zeus ide as it looks pretty horrific under wine, just the assembler.

Feature bloat - I figured what is a chess game without a computer player... :lol:
Don't worry I am not alone I found of all things an Atari book that went through the design of a chess program.. in basic. But still it got my mind working on how to do this in assembly on the speccy. The computer will be a crippled opponent (because I don't want the person to have to wait 20 mins between moves.) but that is the price you pay - you can get a window-kicker opponent with acceptable load times or an okish opponent with a fair amount of lag.

Nirvana graphics - what I did was keep my animated loading screen, but the menu is nirvana, and also the main program. While its not exactly going to set the world on fire it does make designing tiles for chess a whole lot easier. I wish I had known how to use Nirvana from the jumpstart. :lol:

What happened was I was about done doing the write up, and I looked at what was there and thought to myself 'I can't put this out, its not a real game yet.'

I'd much rather do something right than cheese it.
Nomad
Manic Miner
Posts: 600
Joined: Thu Dec 28, 2017 12:38 pm

Re: Crap 0.1 first assembly project

Post by Nomad »

Here are some screen shots for the visually starved.

These are the initial tests for the Atari port.. (Done during my laptop having that disaster mesa update where I could only use wine :lol: )

Internal clocks are nice, Atari Basic has some unusual design choices. Lol I can see why most people went for the Microsoft cartridge.


Image

Image

One really cool feature is the ability to have a cassette tape have one chanel set as an audio stream and the other as a data stream. What this lets you do is have audio from the tape play along with the program. You can do really cool things like show images and data on the screen as you have a narrator talk in the background. I wish there was a way to do this with the spectrum.

What this lets me do is add a nice feature to the Atari port. The chess tutor can have someone talking you through the moves/problems on the screen. If the player picks the wrong move then you can tell them they are a dummy / explain the proper move.

That was just my back of the napkin idea but there are many other applications. Atari used this feature to do the 'invitation to programming' course. But this technique was used by 3rd party developers to create extensive course ware. (but in this case they had a custom encoder that took until 2015 to be cracked :lol: )
Nomad
Manic Miner
Posts: 600
Joined: Thu Dec 28, 2017 12:38 pm

Re: Crap 0.1 first assembly project

Post by Nomad »

Day 56, 309 days left!

Search depth, and 8 bit limitations.

When evaluating moves in chess you come across an intresting problem. if we try and just evaluate every possible move you get an situation of eponentially increaseing choices in the search tree. This is fine for say a 64 bit multi processor machine.. (to a point) but on the 8 bit machines with much more limited processor power its a real problem.

Lets just throw a number out there. say to evaluate a position it takes 0.1 seconds.

We evaluate 10 moves at level 1, this takes 1 second.
level two we have 100 moves to evaluate that is going to be 10 seconds..
level three we have 1000 moves to eval.. 100 seconds (still ok..)
level four we hit the wall with 10,000 moves to evaluate giving us a whopping 16 mins and 40 seconds..

The problem is even if we go to level four its still not really enough just to brute force a positional evaluation of the board space. A good human player is going to be able to plan four moves ahead and so might have set up a trap for the computer. What we need is the ability to plan the moves perhaps 20 moves ahead.. to be sure that the human player could not possibly have planned so far in the future.

This is a real issue because say we just take the fact that the machine will sit there for 16 mins evaluating one move, we go to level 5 and it gets much worse.

Level five we have to evaluate 100,000 possible moves or 2 hours 46 mins to evaluate a board position.

But hey its research right? I bet someone would let it run for 2 hours + on one move... correspondents chess style.

Level 6 gives us 1 million moves to evaluate .. that now brings us to over 27 hours to evaluate a move. Still ok for postal chess.

Level 7 gives us 10 million moves to evaluate 11 days I think the patients of even a postal chess player is going to be strained at this point.

Plus we have to consider even if you are dropping the non-interesting branches of your search tree you are going to get into serious problems way before this point with the 8 bit systems.

Anyway.. just to push home the point that a pure positional evaluation is not enough for 8 bit. Probably the best bet is going to keep our 3 levels of positional evaluation but add on a bunch of rules to help focus the search tree. And also spot obvious gotcha's. One idea I have been thinking of is this.

Write the move evaluate to focus on control of the center squares (what a human would be doing anyway). Have a table of most probable moves the player will make D4|E4... and have a book of lines ready to play. There are play styles for black that can really annoy a white player by shutting down opportunities early in the game. If the human player lets crap chess do it, it will follow such a plan. Thereby overcoming computational limitations by just playing a very solid defensive/smothering opening against white.

A good player will still crush crap chess at this point. But we force a draw with the majority of potato players.

One of the big challenges is stopping crap chess being so reliant on a material count. Good players know that typically a computer player is going to be greedy to the point of loosing a game (by giving up position for points). By having it follow book openings somewhat mitigates this till the middle game/end game. But its still not a complete solution.

There is another way though, its very cheesy but crap chess through the interface I could 'phone a friend' and offload the evaluation. :lol: I think this is cheating though. You could just hook it up to stockfish and badabing badaboom it would crush the player every single time. :lol: would be a funny joke to play on your friends when they are around. Especially the chess nerds "can you beat a spectrum chess game?" Then watch them get wiped.
Nomad
Manic Miner
Posts: 600
Joined: Thu Dec 28, 2017 12:38 pm

Re: Crap 0.1 first assembly project

Post by Nomad »

Update:

The Atari book while being a bit of a flawed diamond in terms of usefulness (its actually a well written book, just by a guy without much depth of programming know how..). What I respect about the guy was he held his hands up and said flat out he was not an expert but pointed the reader in the direction where to go to get better info. (SARGON listings). For me that is one of the more classy moves I have seen in a period microcomputer book.

While the book itself is not state of the art, its a nice practical introduction, you then take that and apply it to the more slick (well for 1979-85') techniques. There are a ton of academic books on computer chess from this period. Reading how SARGON/SARGON II/SARGON III was developed is great. I recommend this to anyone contemplating developing a 8-bit computer chess.

There are some excellent articles in BYTE on computer chess written by the programmers behind SARGON. What is nice is it was written in z80 assembler. But Sargon got ported to many different targets.

What I like about the Sargon system was they were never satisfied and really pushed the envelope of what was possible. Not just a 'grinder' there are a bunch of really interesting techniques being used to get the most out of the 8-bit machines.

The plan is to get a computer player with an ELO of around 1600. (Around SARGON II rating) That would be quite something on the spectrum. To put that into perspective that is your average club player. With the microdrive you can have quite an extensive opening and endgame book to cut down on the amount of calculations the engine has to make. The limiting factor as I said before is the time the engine takes to evaluate the moves.

Here is the listing for SARGON (the first one.) I think you can see why I got excited - points to note its designed to work with CP/M but that is no big deal. The big advantage is this is z80 baby.. It's the logic that is the most important things. Everything else is pretty straight forward to get working on the humble speccy.

To play along at home follow the link as there is to much to post here..

If you are anything like me, your first instinct was to save then print the listing.

http://www.andreadrian.de/schach/sargon.asm

This answers so many implementation questions I had. Ok its not SARGON II/III but this is way better a spot than I was 24 hours ago.

Being able to see how someone else did it is a great help.

Also well worth a look is ...

Alan Kotok's thesis http://www.kotok.org/AK-Thesis-1962.pdf
Nomad
Manic Miner
Posts: 600
Joined: Thu Dec 28, 2017 12:38 pm

Re: Crap 0.1 first assembly project

Post by Nomad »

Shout out to Marek Strejczek & the Technical University of Łódź,..

http://www.top-5000.nl/ps/SomeAspectsOf ... amming.pdf

This is a great overview - while the project was done in Borland C++ much of the research and theory is very useful.

So you get the Byte magazines, and the links above I think you are at pretty much the same stage with regards to research documents. Now comes the fun part. The analysis and then the coding. Much of the heavy lifting has been done already thanks to SARGON but I think that some improvements can be made to the Opening book and the end game analysis part.

The only thing I couldn't find a copy of annoyingly was the book written by the Spracklen's. Sargon, a computer chess program - This is deeply annoying as archive.org has a copy but its part of that book loan thing. So essentially unavailable :evil:

Still have the source code, the articles. So I think its going to be ok. My thinking being that they would have put the meat and potato portion of the book into the articles.
Nomad
Manic Miner
Posts: 600
Joined: Thu Dec 28, 2017 12:38 pm

Re: Crap 0.1 first assembly project

Post by Nomad »

Day 57, 308 days left!

Today's project time was spent reviewing all of the books/articles regarding creating a chess engine for a 8-bit computer.

To give some insight into what is happening though. (for the morbid curious)..

I have been agonizing over the choice of board representation, really we have two basic choices when you write an engine. Piece centric vs Square centric. Crapchess has been a square centric design but this really limits what you can do when it comes time to write the analysis functions later.

If you have the chance most advice seems to be to go for a Piece centric bitboard design.

I will make the finally decision probably in the next day or so after I have slept on it. But unless something radical happens I am fairly positive I will go with a bitboard method.

After that is the next coding challenge - that is getting crapchess to have a set of the complete rules of chess that needs to have no errors. If I screw this part up the whole program is borked and it would require a complete rewrite. It also requires a decision to have been made about internal board representation. (how you explain the rules is in terms of the internal representation, so its different for square centric programs vs piece centric programs.)

The GUI for crapchess is already done (luckily). It's just a matter of plugging the engine in.

I was reading a port report on SARGON from a guy who had converted the z80 to 8080 code. This took him 6 months working every night. The scale of these engines is really quite something. It easily dwarfs every other part of the program in terms of complexity.

I am convinced you can get a semi-decent game of chess from a spectrum. These fellows were getting competent results from z80s on other platforms, stuff that beat engines running on mainframes. So there is no excuse.

But I will say this, I am fine with the engine being crap if it looks like I won't be able to complete the project. Just getting crap chess playing the game is ok. I can always come back to it and do an update once I get better.
Nomad
Manic Miner
Posts: 600
Joined: Thu Dec 28, 2017 12:38 pm

Re: Crap 0.1 first assembly project

Post by Nomad »

Day 58, 309 days left!

I slept on it and I am going bitboard :lol: it makes it a bit more complex to implement a piece centric board representation for crap chess but the gains in doing so can't be ignored. And for the z80 you need every advantage you can get as we can't just build a grinder type engine. (the humble z80 is just too slow.. yes even an z80e..)

Todays development time will be spent creating a bitboard for crapchess.

Additionally, further reference works are needed for review. I have an idea how to offset the move evaluation but I need to check first against the theory books if I got it straight or not then search to see if anyone has (hopefully) implemented it.

The plan is to focus on a handful of openings, like I said before strong openings that smother the opponent and give the greatest chance for a draw. After that its just a matter of building a table of moves. This is one of the simple parts of the program to understand. The decision comes do you want a very wide but shallow opening book or somthing with a lot of depth? The issue with a shallow opening book is obvious. We have lots of memory being used for a bunch of moves we will never use.

You could overwrite the opening book after the game has moved past the initial n moves, but then that requires you reload the game every time. (but its a legit strategy..).

The second problem faced with a shallow opening book is that is not really how a human player plays chess. Usually a good player has a few openings that he/she will use based on a few key variables in the opening phase of the game. I want crapchess to behave more like this so I would prefer it had a fairly comprehensive understand of a handful of openings than a whole bunch that might never get chosen.

The nice thing about the smothering style openings is they generally give the player a very solid base for the middle game, mitigate risk of opponent gaining too much influence in the center squares and offset as much risk as possible. This hopefully leaves the computer in a good position to perform board evaluations without the help of the book.

The trick is to know what squares to watch (Hint.. its the center squares, and the positions of both its own and opponent men.)

There is a lot of other stuff you need to build into the engine to make it even competent. Like as a human player you know pawn structure is important. But I think it does not become clear just how important pawn structure is in evaluating moves until you do this. This is actually non-trivial problem trying to get the engine to understand pawn structure and how to identify good/bad layouts. There are lots of simple methods to do this but they all have one thing in common they either take up a large amount of processor time or memory.

What is needed is a way to simplify the representation of a good pawn structure... hmmm. ah well somthing to think about.

I remember from chess magazines sometimes people sent in board diagrams with the scored moves for each type of chess man for every legal move on the board. I think this might help with the chess engine it would cost a little memory but having a lookup table like this would be very usefull.

5 x 64 = 320 bytes.

per side you say... but hmmm. you could just flip the table and you have what you need.

If you are evaluating opponents moves you just negate the value in the table.
Nomad
Manic Miner
Posts: 600
Joined: Thu Dec 28, 2017 12:38 pm

Re: Crap 0.1 first assembly project

Post by Nomad »

Update:

So it turns out there are a number of implementation decisions you have to make from the jump start regarding how you actually set up the bittable. It is important decision because it impacts the whole program.

That said, just picking the bittable gives you payoff when building your opening book/evaluation portion of the program. This is because we can use a powerful yet efficient technique Hash tables. This enables the program to switch between lines in the opening to adapt to the players moves without needing to move out of book opening phase. This is good because its much faster, and more reliable.

There is a more subtle reason to want to do this. With the 8-bit machine we want it as much as possible to stay within a book phase and try and get the maximum advantage. It is actually the most dangerous point for the opponent because when its in book its got the advantage of all these pre-evaluated/tested lines that are known to be the 'best' answer to the opponent. What you do is offset the evaluation to chess history/or a powerful engine that is writing the opening book for the 8-bit machine to use.

It becomes then a question - how much is really the 8-bit machine? When you use the opening book.. This question is one of the controversy with computer chess when the engines have to play without access to an opening book. It can be said its the best way to test the engines against each other but what if you designed the engine to work with the opening book from the ground up? Typically you would not want to build an engine that worked purely off evaluation. That is not an efficient use of the machine. Especially in 8-bit.

If you are looking for information how I wrote the bit board, lol stay tuned for my funky pdf.

It is not as straightforward as you might think :lol:
Nomad
Manic Miner
Posts: 600
Joined: Thu Dec 28, 2017 12:38 pm

Re: Crap 0.1 first assembly project

Post by Nomad »

Day 59, 308 days left!

Nearly day 60 and I think I have pinned down the specification for the Crap Chess engine.

Needs to have at least a 1600 with the end goal being 1736+ ELO.*

Sargon II by 1980 was at this level and had been kicking ass and taking names for a number of years, it was a z80 based chess programming running on a stock microcomputer. Therefore it proves you can get a high level of play from a z80 microcomputer. As the Spectrum is a z80 based machine. There is no reason why you can't do this on the spectrum.

* This would make it better than 99% of all chess players and better than 85% of all tournament players.

While I am not a husband/wife highly educated set of maths boffins. I do have something they didn't have 38 years of research that went after into the algorithms that are used in computer chess. :lol:

There was evidently something of a crash research project to get a chess computer to a stage where it could beat a grand master. I had no idea the amount of active research there was on this subject during the 80s. Fascinating. Of course what can be applied and what is appropriate to a z80 based computer is another thing. :lol: There are many intresting vector baised solutions that would work just great on somthing like a Cray. Not so much on a Spectrum.

But that is where doing the research survey pays off. For those reading this who are in the dark. Its simple. You take a book describing the subject you are interested in. Look for the bibliography/citations. Now take that list to google scholar or whatever database you use to look for papers. Get all the papers listed. You now have a stack of papers to read on computer chess. This is the start of the survey. Go through each paper and like a magpie look for stuff you want. :lol: The interesting stuff you mention in your survey paper. Why write the survey paper? Because you are going to forget what you read. This is your shortcut to reading the stack of papers later. All of the interesting stuff is going to be in your survey. You get the technical infos from the actual papers/reports when you are coding the engine. But often times you just need an idea or gloss on what to do.
Nomad
Manic Miner
Posts: 600
Joined: Thu Dec 28, 2017 12:38 pm

Re: Crap 0.1 first assembly project

Post by Nomad »

Update:

I have been umm'in and arr'ing over what to prefice my documentation with. Untill now...

I found the perfect quote to sum up what I wanted to do with crapchess..
In fact, at the lowest level, any Tom, Dick or Harry may be able to sell, through the small ads column of one of the numerous computer magazines, a few copies of his program. If it is slow and weak and virtually useless, it does not matter to him. So long as it plays legal chess, he may satisfy the letter of the Trades Description Act and other consumer protection legislation.
--The New Chess Computer Book
For me this was the specification/market segment for crapchess (well as a minimum anyway).

Know it was silly but I have been looking at the introduction for ages and not satisfied with it till now. :lol:

In other news I finally went through Cyrus-is-chess and did a proper evaluation. It had some nice interface/menu ideas that I will 'adopt' for crapchess (like being able to flip the board), and perhaps even get the engine to play itself. That would be good for testing actually.

In fairness for an old game Cyrus had a bunch of good features. The only annoying part was the input - I want to be able to type my move into the machine using notation. Lucky this was always going to be a feature of crapchess. But being able to use the cursor keys is a nice touch also for the window lickers.

Image

You should expect to see 'THINKING...' a whole bunch with Cyrus :lol:

Reading through these old academic books on chess computers is a gold-mine of ideas and pointers to more stuff to investigate. For example I never realized that the creator of 1k chess wrote a series of articles on the development of the program. (Need to track that bad boy down.)

One thing that is becoming abundantly clear is there was such cut-throat competition among the professional programmers of these chess projects a lot of the techniques used were basically the same for microcomputers. Each team seems to have focused on the same set of design choices and algorithms. Like you see a clear adoption of new techniques by these guys pretty quickly after it gets published. Among the armature coders there is more variation.

I have to get crapchess to 4 ply search. That will guarntee no dummy moves or unforced errors. Tatically by getting to 4ply you already have a 1000 elo player just on tatical play and being able to avoid making mistakes. That is a good basis.

It's getting anything to run within an acceptable time limit at 4ply though on the z80s.. but my headache was just using a simple tree search. With these new techniques I can greatly reduce the nodes that the engine will examine (from around 35 to just 6)... so that will really speed things up. I would rather get 1296 nodes to examine than 1.5 million. :lol: But these articles/reports/papers all make big claims about the effectiveness of such and such a technique. Its hard to know really till you actually test the thing. But if its true what they are saying then I should have a 4ply search in around 1 min and 9 seconds on the spectrum. That would in theory get you 8ply in just over 2 days.

But it gets better, as it stands I have reviewed most papers till about 82' and if the advances in algorithmic search is anything to go by even further refinements should be possible I think. Just how much more you can get out of these little machines will be interesting.

One thing I would dearly like to know is how the programmers behind the dedicated chess computers managed to get there programs to run so efficiently. There are examples of these machines running with only 140-256 bytes of ram. This has to be a stack machine setup. But the problem with this is I could find no information on how these things were actually written in practical terms. As it would have been a trade secret.

Thinking of the design of crapchess, I often wondered if it was better to use a disk/cartridge system over tape/microdrive. The same book I found the quote earlier about the crap chess games had a very nice evaluation of the pros/cons for the microcomputer and using the various media. (with the exception of the microdrive)

Disk:
Floppy discs do enable a program to be loaded very quickly, and provide additional protection against piracy, but they require additional expensive hardware (a disc drive can cost anything from $250-1000) so a program which is only available on disc has a limited market, although it gives much more scope to the programmer to write a long program with book openings.
--The New Chess Computer Book p.163
I had been thinking of using the +3 disk drive, but that would require a lot of disk swapping for it to work in the same way as the microdrive system.. Regarding the spectrum yea his comments are fair for the 48k and anything other than the +3 but, when it comes to the +3 disk is the go to choice for chess programs I would say.

Tape:
From the user's point of view, the main advantage of a cassette is that if he does not think much of the program, little money has been wasted and he can buy another. The main disadvantage is the slowness (up to 5 minutes) with which cassettes load into the computer. They are the least convenient form in which to possess a program -- particularly chess, which
tends to require a long program.
--The New Chess Computer Book p.163
Hardly a ringing endorsement :lol:, but it is fair i suppose.

Cartridge:
A program on ROM cartridge is available at once -- just plug it into the expansion socket provided (not all computers have this), switch on and play. Cartridges are particularly important for the Commodore, Atari and Texas Instruments machines which, unlike the Sinclair Spectrum and ZX81, have expansion slots built-in. For computers with small on-board memory (the standard VIC for example) the ROM cartridge makes possible a decent-sized program which would not fit into the RAM of the machine if you had to try to load it from cassette tape or disc. Cartridge programs are more expensive than those on tape, but actual prices vary.

For the programmer and software publisher, different considerations come into play for programs on cartridge: the higher capital cost must be balanced with the increased protection against the pirate copier. The fact that it costs a lot to produce a ROM module, that they must be mass-produced to make this worthwhile, and that this is unlikely to happen if the program is no good, amounts to indirect protection for the buyer of the software. On the other hand, he is paying three to five times as much for his chess program and it will not be upgraded or copyable; also cartridges must be handled carefully lest they be damaged by static electricity.
--The New Chess Computer Book p.163-164
Nomad
Manic Miner
Posts: 600
Joined: Thu Dec 28, 2017 12:38 pm

Re: Crap 0.1 first assembly project

Post by Nomad »

Further update:

Bitboards & tables.

So with bitboards being used as a quick & efficent way to represent a lot of useful information in the game that would have otherwise taken up a significant amount of processing time. we can do more...

By combining them with tables of weighted values we now can use the bitboard + tables to wihtout any complicated processing derive an answer to an evaluation.

For example. we take the Black knight bitboard.

Code: Select all

0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 1 0 0 1 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
Ok nothing to surprising its the start of the game. Hypermodern style.

But say we want to do some cheap evaluations in our move selection. Knights are very useful pieces and can dramatically influence the game.

So what we do is have a weighted map of the whole board, where we assign values based on what we add or subtract to the final move evalaution for a particular peice. Then we either modify or use a different table depending on what stage of the game we are in.

So for the knights, we desperatly want them to avoid the sides of the board. As this reduces the options for movement and with reduced mobility makes them easier to pin, less efective in attack and unable to defend as well.

Code: Select all

-FF -FF -FF -FF -FF -FF -FF -FF
-FF  00  00  00  00  00  00 -FF
-FF  00  00  00  00  00  00 -FF
-FF  00  00  1A  1A  00  00 -FF
-FF  0A  10  1A  1A  10  0A -FF
-FF  10  14  18  18  14  10 -FF
-FF  11  16  19  19  16  11 -FF
-FF -FF -FF -FF -FF -FF -FF -FF
Notice this is a simple map, there is no extra bonus for positions on the center of the board. probably if this was 'for realz..' you would have a bunch of different numbers aside from the outside squares. With most of the pieces you want to encourage moving to contest/defend the center squares.

Especially with pieces such as knight - you want them getting busy before bishop, ideally get rooks on their own open file. all these things you can encode within the tables. This is where the real power of using bitboards comes in. With square encoding you don't get this level of fine grained encoding like you do with the bit board. So A lot of the heavy lifting is left to the processor.. With this approach we save on processor time, but at the expense of ram.
AndyC
Dynamite Dan
Posts: 1388
Joined: Mon Nov 13, 2017 5:12 am

Re: Crap 0.1 first assembly project

Post by AndyC »

Nomad wrote: Thu Mar 01, 2018 9:46 am I had been thinking of using the +3 disk drive, but that would require a lot of disk swapping for it to work in the same way as the microdrive system.. Regarding the spectrum yea his comments are fair for the 48k and anything other than the +3 but, when it comes to the +3 disk is the go to choice for chess programs I would say.
I'd be surprised at that, there is far more free space on a +3 Disk than a microdrive cartridge (and don't need to waste any with duplicate blocks for speed), it has better support for random access files and, of course, you have a lot more memory to play with. You can even just let +3DOS handle it via the RAMDisk interface so you don't have to do manual memory management if your code is already file oriented.
Nomad
Manic Miner
Posts: 600
Joined: Thu Dec 28, 2017 12:38 pm

Re: Crap 0.1 first assembly project

Post by Nomad »

How did I ever make that mistake?? I miss-remembered the drive being small! :lol:


Image

So one thing that is confusing me when I flip the drive its not accessible I thought you could record on the reverse also.
AndyC
Dynamite Dan
Posts: 1388
Joined: Mon Nov 13, 2017 5:12 am

Re: Crap 0.1 first assembly project

Post by AndyC »

Well 173K per side was small, even back in the day, just not that small! :lol:

But you're right, flipping the disk should allow you to use the other side. You might just have a disk which isn't formatted on the flip-side, which gives some suitably cryptic "Not accessible" like message IIRC.
Nomad
Manic Miner
Posts: 600
Joined: Thu Dec 28, 2017 12:38 pm

Re: Crap 0.1 first assembly project

Post by Nomad »

Yea I flip the image in fuse but when I cat it the disk read 0 sector 0 data its like its complaining there are mo sectors. When I try and format it flipped it errors :lol: I notice for some reason I have single sided 40 sector drive selected for A so I think that is the problem. I will have a play.

So the stock amstrad disk drive on the +3 was 80 sectors DD?
Nomad
Manic Miner
Posts: 600
Joined: Thu Dec 28, 2017 12:38 pm

Re: Crap 0.1 first assembly project

Post by Nomad »

Lol now I remember why I wanted a beeb :lol:

I can't figure it out, I flipped the disks, changed the drives back and forth from 40 to 80 single and double and still nothing. Its still the tiny drive I remember :lol:
Image

Image
Nomad
Manic Miner
Posts: 600
Joined: Thu Dec 28, 2017 12:38 pm

Re: Crap 0.1 first assembly project

Post by Nomad »

Day 60, 307 days left!

Today's updates, not so much got done today as was busy. But one fun thing..

Here is the creator of Sargon, Sargon II, and Sargon III on Computer Chronicles.

[youtube]https://youtu.be/CnHiSeE-yBY?t=4m10s[/youtube]

You can see that even by 1985 things had dramatically moved on since the end of the 1970s with computer chess. Already you have good computer players and fully featured programs. Now how many people back in blighty had the money for a multi thousand pound machine in the early 80s well that is a small market. (for the Apple II) But its still pretty cool.

In project news.. Slowly comming round to the idea of doing this on the plus 3. Having the memory disk, and being able to swap data easly in and out from the physiical floppy disks is quite somthing. Plus more ram is always good. Only issue is +3 was not so popular and so the amount of information on the platform is a lot less than say 48k.

Anyway assuming I can convince fuse to allow me to use both sides of the disk image :lol: It would seem a lot more straight forward to use the disks than the microdrives. This is a little annoying as I spent a significant amount of time figuring out how to talk to the microdrive in assembly :lol: but there is no reason I can't do both I suppose. Its never wasted finding out about this stuff I think.

+3 ram use is a little bit esoteric with is many pages :lol:

Funny as there was a new series on youtube that poped up that deals with +3 and assembly. So that was well timed.

Thanks to peter's heads up about the Spanish +3 manual. I now can check the diagrams and tables. here is hoping google translate is going to be ok. I think comparing this to the text from the typed in English manual should be enough to check there are no errors.
Nomad
Manic Miner
Posts: 600
Joined: Thu Dec 28, 2017 12:38 pm

Re: Crap 0.1 first assembly project

Post by Nomad »

Thanks to the kind intervention of others I now have a scan of the +3 manual.

Image

Lol now if only I could figure out how to use the other side of my disk in fuse. :lol:
Nomad
Manic Miner
Posts: 600
Joined: Thu Dec 28, 2017 12:38 pm

Re: Crap 0.1 first assembly project

Post by Nomad »

Day 61, 306 days left!

Major news in the world of crapchess. :lol: Ok your all sitting down...

Crap chess is going +3.. Yea I got the disk problem sorted out with a combination of lots of assistance from non-potato's (Thanks Peter and Bob for the assist).

I must have taken a rather large hit to the head before thinking the microdrive would have been a better solution. I can store tones of data on each disk this way with the +3 disks. Plus I get the memory disk into the bargain.. When you look at things like that its an obvious choice.

But for every gain, wadaya loose? Well besides market share (and that is the major issue with going to a +3 system from a historical point of view I just cut a huge chunk of the potential user base.)

There are also other concerns about errors on the +3 board and sound. Assuming the board never got fixed its going to sound more distorted than your stock 128k. But then this is not a demo scene performance - its crapchess. Sounds were never going to be a big part of this. So I can live with the loss.

Ok in light of this change - going to have to do some re-packaging when we use pasmo or zeus as so far as I know there is no way to generate a disk image. So its a case of generating a tap and then copying the memory to disk. That is ok. It's the same/very similar syntax to how you do it with microdrive.

So what did I do after I got the first disk set working - you better believe I backed that bad boy up :lol: I think the suffering/negativity/rage that went into the creation of that humble disk image :lol: Anyway - now that is safely backed up its time to get busy with the next stage of the project.

Now all of the examples I have for z80 chess engines use CP/M. It would be a lot easier to talk to the grey beards if I were to use the same OS... But I don't have to.. hmmm... This is the next choice.. CP/M gives me some advantages as there is a TON of information on it, lots of people have used it, tutorials, books, magazine articles abound. Most of the source code is going to use CP/M..

Lets just say there are some very compelling reasons to use CP/M in the project.

But going back to the original project brief - I get the feeling that expecting our already dwindling market demographic - someone who now owns a +3 and has CP/M.. who wants to play chess... You begin to see the problem.

That said with the disks, now you can create a very very nice chess tutor, and the opening book for crap chess is really only limited by the patients of the person operating the computer to swap disks. Given that assuming the person is a non-potato and has an organized index of disks.. There is no real difference between a system with 5 disks and 50 or 500... (well besides physical space)

I could have every opening in my chess encyclopedia including the variant lines contained on 200 disks... Just for example.

People were paying big money for a good chess computer/engine in the early 1980s at the high end your talking 1000-2000 dollars/pounds (there seems to have been the same transatlantic markup even then..)

Still the disks on this kind of system would have been a killer assuming we live in a fantasy world where I could have sourced 200 Maxwell CF2 disks for this it would have cost me 800 GBP for the disks alone. :lol: But as I remember these disks were always out of stock. But anyway lets assume you could acctually get hold of the kind of inventory you would need.

My guess is a system like this you would have had a demo system... then gone out and bought more disks when you made a sale. Lets face it a 200 disk system is not going to have many sales... :lol:

So lets be generous and assume we could get a bulk discount for 200 pieces from maxwell. (Even back in the day probably for bulk orders it would have been a much better deal). So lets say instead of 4 pounds we get a sweet deal of 3.25 per disk. The crap chess opening library would cost 650 GBP at cost... probably the same again for the game database (but you would have a very nice library. My guess is someone would buy that.. have you seen the money chess people spend on books?) Nobody is selling something like that for nothing... It needs a good margin. So call it a round grand for the opening library.

Fine so we established its kinda possible to make a boutique software solution on the +3, and that there is a strong likelihood to appeal to a handful of wealthy chess nerds who probably would have bought the +3 just to use the system if it was good enough...

We have gone a long way from the 5 pounds in the small adds of a spectrum magazine...
Nomad
Manic Miner
Posts: 600
Joined: Thu Dec 28, 2017 12:38 pm

Re: Crap 0.1 first assembly project

Post by Nomad »

Sources for crap chess.

So I figured the best idea with setting up the strategic rules for crapchess to follow was to use a method that is now called hypermodern system. Its nice because the book that I used as the basis for formulating the rules is extremely easy to read - its widely acknowledged as one of the best chess books ever written. True chess nerds will already know what book I selected but for everyone else..

My System - Nimzowitsch.

The daddy of the hypermodern style. It's hard to overstate the impact that his book had on chess.

Anyway that is getting off topic. What is important is he lays out a system to the whole game explaining each step in detail. Outlining what analytical steps needed to take place. This is fantastic for creating a set of rules for crap chess.
  • The center
  • Play on the open files
  • Play on the seventh and eighth ranks
  • The passed pawns
  • The pin
  • Discovered checks
  • Exchanging
  • The pawn-chain
The basics gives solid advice, if the program just managed to follow these rules effectively then it would win against most opponents. Against a strong club player there will be problems. But even then you already have beat 99% of the people that will play the engine. getting that last 1% is the really tough part.
Nomad
Manic Miner
Posts: 600
Joined: Thu Dec 28, 2017 12:38 pm

Re: Crap 0.1 first assembly project

Post by Nomad »

Day 62, 305 days left!

Received dogma and bitboards..

So it struck me today that perhaps; just for a moment. That the received wisdom of using multiple tables of bitboards to represent the board encoding might result in overly complex and expensive evaluation stages to the chess engine.

Especially for 8 bit.

There said it, lol. Seems to me that creating all of these tailor made, situation specific rules might result in just a huge mess of branching if else statements (well from a logic point of view)

Does not not make more seance to go for something that is more simple in the way it represents the board space? Sure you loose in that you can't use quick shorthand for various piece positions you need to pick them out of a board representation of other pieces. However.. everything is working from that same byte table..

Plus with the bit boards eventually you are going to have to merge the information to get a weighting for the board space as a whole anyway...

Smoke and Mirrors - a.k.a using a hashing function to direct a search.

Another thing that occurred to me was if processing power is at a premium (with the 8 bit machines) It makes seance to offset as much of the evaluation to external process as possible. Getting a robust and extensive opening book massively pays off. We can encode the most likely moves that an opponent will play and what we should do to avoid expensive evaluation periods.

All pretty humdrum stuff. I figure use a hash of the board to look up a baked evaluation. As its a table indexed by the hash that returns a move its pretty efficient.

This also helps with the problem of analysis paralysis that these engines seem to suffer from. If the decision weighting is not handled correctly you can end up with a situation where the engine does not know what to do with enough certainty to act. This is a bad spot to be in - but its better to pick a random answer from your set of candidates than waste hours looking at deeper levels of simulation.

My thinking is I would rather have an engine that was fast, that I could improve the weighting of its evaluation function through repetition than letting an inferior version of the engine spend hours evaluating a move.

This then brings us to our final 'revalation'

It probably makes more seance to build the evaluation data using a different machine, then just use the results on the z80. Why because nobody wants to be doing ill iterative learning on a z80 in 2018 :lol:. In a matter of days I can do what the humble z80 would have taken decades to perform.

So the plan is come up with a weighted table of values for various chessmen, based on a database of 16 million games. Once the data is compiled - it is the basis of what we use in the evaluation function for crap chess on the z80. But its all done on a modern PC initially.
Nomad
Manic Miner
Posts: 600
Joined: Thu Dec 28, 2017 12:38 pm

Re: Crap 0.1 first assembly project

Post by Nomad »

Day 63, 304 days left!

Media update:

I woke up to find a disk image that was a true copy of a Maxwell CF2 disk. Thank you Guesser.

This makes things way way simpler in creating the crap chess disk set. No longer looking at 400 files - it has cut the number of images in half. And as a bonus this is how they would have existed were they a true CF2 disk.

Excellent!

Project update:

I have been researching how to create a chess engine in hardware and I found out an interesting secret (well secret to me - the advertising behind these widgets tented to obscure the fact). The vast majority of chess computers you could buy commercially were really microcomputers just packaged with specialized interfaces (usually 6502 but sometimes z80s were used) They might have had tiny memories but the chip was stock and the ROM would have just been a regular program that used a limited ram stack.

Very few had anything like custom chips to do stuff like move generation, evaluation in hardware. It was essentially a software deal.

If you wanted a true hardware implementation of a chess engine, it would have been blisteringly fast when compaired to the microcomputer - but at a much greater cost.

However there were a few examples created usually by research groups and big corporations. You already know one (Deep Blue). Belle is another.

So to get back to the point, a lot of the research that went into these devices that eventually got talked about/published is applicable. As they are really using stock chips to work the magic. The chances of research in computer chess during this period being for non-standard chip architectures are very small. This is great as the depth of research is really something.

All of it is applicable to 8-bit.

Research win!

Ok you remember me talking about how it made much more sence to develop the opening book/rules/play style on a modern system and bake the results then import to the z80 target. This is much closer than before.

There are two systems I am testing - both are written in C. (Well they could have been done in x86 assembly but I don't have time). The neural network is a simple test, it takes four arrays of input and you teach it to regonise the contents of the arrays. It then goes into a loop where it 'learns' to regonise the input and builds a weighted evaluation.

This is only working for 16 data points at the moment, eventually it needs to do 128 but I am very encouraged by the performance. it works to a very fine margin of error (there is always a error in evaluation) but even on a potato system like mine its finishes its training in a flash.

This seems a great way to develop the evaluation weightings that you need. But this is a huge rabbit hole so I side step this part for now. And focus on a more well troden/conventional route.

The plan is to build a program that can generate the data I need for crap chess. This is pretty straight forward. I just feed it the first million games, it will sit and evaluate each ply and generate statistics that are used by the engine on if a move was good or bad, how it affected the game.

What you do is try and predict the outcome using this training data. you see how close the program was in making its guess. if its better than the last time you ran the program. you update the new weightings. if its producing about the same. you don't change anything. if its worse, you don't change anything. You keep repeating until you get a good weighting set.

Now you are confident your engine has a good set of values to evaluate moves, you can now test it against the rest of your data set and see how it does.

Hopefully its good, this data is then what you use in the evaluation function and move generation subroutines for crapchess.

z80 progress:

Found a great little encoder/decoder from the CPC wiki. (thanks SevenFFF). Somehow I missed it the first time. It works in real time and from what I can tell is really nice at encoding sparse data tables. Not sure where this will fit in but if your data is sparse it can save a ton of space. (assume you have a 32 x 24 table, you can encode 6-7 data points, think of it like a star map) Now to do that normally would take 768 bytes. with this encoder you can get it down to a ~32 byte string. very nice.
Nomad
Manic Miner
Posts: 600
Joined: Thu Dec 28, 2017 12:38 pm

Re: Crap 0.1 first assembly project

Post by Nomad »

Book recommendation:

Well if you are interested in computer chess. Otherwise its going to be dry.

Behind Deep Blue: Building the Computer that Defeated the World Chess Champion - Feng-Hsiung Hsu.

The head of hardware design for Deep Blue's account (mainly of the chip design) that went into Deep blue.

I think one of the weaknesses of this otherwise excellent book is he tends to skip over the software side of deep blue and focus on the nitty gritty of how he designed the chips. I guess its understandable as he was the hardware guy but it would have been a much more well rounded and useful book.

With all that said, its still a great read. I found it to be full of interesting details about the history and more importantly the background to why the guy thought the way he did about design choices. A lot of these type of historical retrospects are dry and boring but this is one of the rare books that finds a way to make a subject you would think was totally boring interesting and fun to read. I read this in one sitting,

If you read the book, he throws various bones explaining at a high/mid level how he built deep blue. You can then consult the literature and read up on the techniques/design philosophy.

I never realized just how much work was down to Hsu. Quite surprising as the guy didn't have a strong chess background. The speed that he was able to design the chips is really something. I had to laugh when the guy called himself lazy, yet managed to design, test and fabricate a entire chip in 6 months on a shoe string budget.

To sum up its a good book, easy read and lots of intresting ideas.
Nomad
Manic Miner
Posts: 600
Joined: Thu Dec 28, 2017 12:38 pm

Re: Crap 0.1 first assembly project

Post by Nomad »

Day 64, 303 days left!

Found a good utility for the +3 that will help a lot editing the disk. DICE, I knew it would be good when I saw it and read the features but it was only when I read the manual it dawned on me quite how nice this was. You can edit all aspects of the disk, even the files. So you can do stuff like design custom disk loaders, set down to the bit level how you want the disk to be.

Very nice.

Besides that, spent the project time tracking down more papers and information on 80s and 90s chess engines. Chessbase especially thank to the recommendations I got from the forum.

Got a lot further figuring out what to do with the game disks thanks to people here also. Everything is progressing nicely.

And with a compact printing routine that got shared a few days ago here makes it possible to make a tutorial look decent next to a chess board on the screen.
Post Reply