New game project: Phoenix Chess

[+Lee Stewart]

Debugging is proving to be a very laborious process. Since I'm working directly within the UCSD pascal environment, every little correction I make requires a recompilation of the unit in question. If the change involves the interface section of the the unit, then the unit itself as well as any other units using it have to be recompiled, plus the library file has to be recreated. I have tracers throughout the code and I'm using the Classic99 video capture capability to analyze the screen output after the program runs.

I'm also running out of tractor feed paper because after each debugging session I have to reprint all the corrected sources for reference. This is necessary because it's hard to get a global view of the source code using the very limited screen real estate on the TI. This means transferring the current disk image from my laptop to the TI first then printing the source files from within UCSD Pascal.

Am I having fun yet? With all my complaining, I think yes .

 

Join the club! It's kind of like debugging fbForth's high-level code. ALC was easy, but not high-level code. A lot of indirect traps and painfully single-stepping. I don't envy you; but, I do empathize.

 

... Next is flagellation...

 

YeeHaa!

 

...lee

[+Vorticon]

As I was browsing the WHT sitelist.txt file, I came across a tantalizing entry under Users by Ben Yates titled chess.rtf. It's clearly programmed in a dialect of Basic, very similar to Microsoft Basic. Could it be Geneve basic? Can anyone here take a peek at the attached source code and let me know? I would love to check it out and hopefully learn from it.

chess.txt

[+Vorticon]

So the debugging of the move generation code is around 95% complete. I'm still getting some intermittent unexpected results in some situations and these kinds of bugs are usually the hardest to track down. Nonetheless, I feel confident enough of the current code base to forge forward with the project. To recapitulate the move generation implementation:

 

- The computer scans the board for its own pieces, and for each one found, it generates all of its valid moves

- For each one of these moves, it generates all possible responses from the human opponent to only 1 half move depth. As it does so, it evaluates the resulting position for each of these responses and scores it. There is a lot of recursion going on here.

- As the scores are generated, the computer maintains a linked list of the top 5 scoring positions.

- Once this first pass is done, for each initial move in the above linked list, the computer generates all possible full ply moves down to a depth of 6 ply, keeping only the highest scoring position at each ply.

- Once all 5 top positions have been evaluated in this manner to a ply of 6, only the one that scored the highest at that ply depth is retained.

- If subsequently the human player responds with a predicted move, then no move generation is needed since it's already been calculated.

 

Obviously quite an involved process So how long does it take for this process to complete? At full difficulty level, which means 5 top initial moves retained and a search ply depth of 6, it takes approximately 40 minutes. It will be significantly shorter at lower levels. I should however mention that the scoring function is currently not implemented and I'm just using a dummy function which generates random scores for testing purposes. I expect that the full evaluation function will likely add another 10-15 minutes to the process.

While this may seem like a long time, I'm actually pretty pleased by the results. Many chess computers of the era took at least that long at their highest levels, so this is not too shabby for a machine designed in 1979...

[ti99_forever]

Looks like Quick Basic to me. That's pretty old. Love my comments! I remember it vaguely. It's a port I'm sure.

I loved how Quick Basic (and Qbasic) were very Extended BASIC similarl.

[+Vorticon]

Looks like Quick Basic to me. That's pretty old. Love my comments! I remember it vaguely. It's a port I'm sure.

I loved how Quick Basic (and Qbasic) were very Extended BASIC similarl.

 

You mean lack thereof I'll try to run it in QBasic and see how it performs.

[+Vorticon]

Yup, it's QBasic alright. Does not seem to do castling though, but pretty fast. I'm going to take a closer look at its evaluation function.

 

[+Vorticon]

Here's the framework for the evaluation function:

 

• Material balance: simply add up the values of the pieces on each side except the kings which have infinite value. This is the most important factor in the function and will form the base score. All other factors will either add or subtract from it.
• Mobility: Closed files for rooks and bishops will penalize the position score, as well as knights sitting too close to the board's edge.
• Development: This will be applied only in the first 10 moves of the game. Castling will boost the score. Any knights or bishops still in the home row will deprecate the score. Any queen or king pawns that have not moved will also penalize the score.
• Pawn formations: Stranded pawns and doubled pawns will lower the score. Passed pawns within 2 squares of the opponent's home row will give a significant score boost.

That's pretty much it. As with any AI programming, simple rules when combined can lead to surprising complexity. I'll start coding that evaluation function in the coming couple of weeks and we'll see how it performs. Once done, the core chess program will actually be complete and playable, albeit without an opening library, utility functions or GUI...yet. What I'll do at this point is release a test version with just a primitive text interface for people to play with and give feedback. Getting there slowly but surely

[+Vorticon]

I finally picked this project up again after 4 years as I got tired of feeling guilty over it every time I saw the stack of printouts and notes I conspicuously kept around  In any case, it took me almost a week to go over the code again and gain a good understanding of what the hell I was trying to do, although having taken copious notes did help quite a bit. I corrected several bugs along the way and made a few optimizations and now the move generator works as it should down to a depth of 6 ply and I am ready to tackle the position evaluation function, really the heart of the whole project and will determine how well the computer opponent will play. My goal is simple: Phoenix Chess should be able to beat Video Chess at its highest level 100% of the time, otherwise why bother with another chess program!

The main issue with coding something like that in UCSD Pascal is that execution speed is quite slow: the program is expected to have 35 levels, and the first level already takes an average of 4 minutes per move. Obviously this will get longer with each level. Anyone wants to take bets on how long level 35 will take? ? But hey, this is primarily an educational experience as far as I am concerned so that's fine.

[senior_falcon]

Well, it it's 4*35 then it would be 140 minutes per move.

If it is 4^35 then it would be 2.25^15 years which is 2.25 million billion years which is WAY longer (162659 times longer) than the age of the universe. I hope it runs faster than that!

[+dhe]

If you can access AMS memory from UCSD Pascal (?) - then you could load in a library for opening moves (of course, as soon as you branch off of the first (n moves)) you have to start your look ahead algorithm, but it could at least make the beginning go by quickly, and hopefully set the computer in a strong opening position.

[+Vorticon]

7 hours ago, senior_falcon said:

Well, it it's 4*35 then it would be 140 minutes per move.

If it is 4^35 then it would be 2.25^15 years which is 2.25 million billion years which is WAY longer (162659 times longer) than the age of the universe. I hope it runs faster than that!

It actually takes 44 minutes, but that's with only a dummy evaluation function. I won't know for sure how much a proper function will add to the processing time until it's complete. The processing time does not increment linearly with each level obviously.

[+Vorticon]

6 hours ago, dhe said:

If you can access AMS memory from UCSD Pascal (?) - then you could load in a library for opening moves (of course, as soon as you branch off of the first (n moves)) you have to start your look ahead algorithm, but it could at least make the beginning go by quickly, and hopefully set the computer in a strong opening position.

I definitely plan on implementing an opening library, but I'm not sure I need AMS for that. Too early to worry about it yet

[+Vorticon]

Figuring out when the king is in check as well as potential captures turned out to be computationally intensive. Basically for each board position sent for scoring, the computer cycles through all the pieces on the board, performs all possible displacements for each piece and checks if the end-square happens to be the king (taking into account the playing side of course) as well as any other potential captures and assigning a base score to the position. Sooo, response time just went from a little under 5 minutes to 9.5 minutes on the first level, and there is still a lot to do with the evaluation function. Oh boy...

I have a feeling this is going to end up being an academic exercise at best ?

[+FarmerPotato]

54 minutes ago, Vorticon said:

Figuring out when the king is in check as well as potential captures turned out to be computationally intensive. Basically for each board position sent for scoring, the computer cycles through all the pieces on the board, performs all possible displacements for each piece and checks if the end-square happens to be the king (taking into account the playing side of course) as well as any other potential captures and assigning a base score to the position. Sooo, response time just went from a little under 5 minutes to 9.5 minutes on the first level, and there is still a lot to do with the evaluation function. Oh boy...

I have a feeling this is going to end up being an academic exercise at best ?

Couldn't you work backwards from the king? That way you'd examine at most 2 rows and columns, 2 diagonals, 8 knight moves = 35 squares to see if eligible pieces can attack.

 

What if you cached the squares that a piece can attack? thats 8 bytes for each piece. To test if any square is covered, make an 8 byte mask of squares to check, then test that against a bit field that each piece caches. Possible improvement: use a separate shape to test against a type of piece. Having matched a piece, you have to see if the piece is blocked from attacking. 

 

[1980gamer]

I stink at this game, but know the rules... I think? Castling is not in my playbook... I have had people do it to me... I have to assume they are not cheating!  LOL

Being as only 1 piece moves per turn, do you have to score each piece on the board each time?

 

Can that scan be reduced?  certainly some pieces will not change? But again, I do not know this game.  I am here for the process. 

I need to learn recursion for a project or some other algorithm and this seems much easier in other languages than TI Extended Basic!

 

However, you may spark something in me the figure it out. 

 

Another thought, early in the game when ALL pieces are still in play,  some cannot move.  Can you skip those pieces from the "scan"?

The Knight would always be scanned I would think. But other non Pawns are locked to start. You could skip them maybe?

 

[+Vorticon]

2 hours ago, FarmerPotato said:

Couldn't you work backwards from the king? That way you'd examine at most 2 rows and columns, 2 diagonals, 8 knight moves = 35 squares to see if eligible pieces can attack.

 

What if you cached the squares that a piece can attack? thats 8 bytes for each piece. To test if any square is covered, make an 8 byte mask of squares to check, then test that against a bit field that each piece caches. Possible improvement: use a separate shape to test against a type of piece. Having matched a piece, you have to see if the piece is blocked from attacking. 

 

The king in check search is actually incorporated into a broader potential piece capture routine and is just a secondary outcome. Each piece on the board goes through all its valid displacements, and if it hits the king then a check situation exists otherwise if it's an opposing piece then it's a potential capture. That routine creates a base score for any given position where the total material value of the pieces as well as the values of the pieces threatened by capture and any king checks are taken into account on both sides of the board then subtracted from each other. That base score will later be modified based on certain development criteria.

As for the displacement scheme, the internal representation of the chessboard is designed in a way that each piece has a limited set of displacement deltas and not absolute displacements (stored in a matrix), which are added to its current position to generate all possible reachable positions. For example, the king and knight have 8 displacement deltas, whereas the rook and bishop have 28. The queen simply recycles the displacements deltas of the rook and bishop combined. In essence this scheme is kind of a mask. The chessboard is an array [11..88] of integer, and any final position (current position + displacement delta) that falls outside of that range or lands on a friendly piece is not valid. The displacement delta is repeated to create rays, a process which stops at an invalid position.

 

Chessboard representation

 

18 28 38 48 58 68 78 88

17 27 37 47 57 67 77 87

16 26 36 46 56 66 76 86

15 25 35 45 55 65 75 85

14 24 34 44 54 64 74 84

13 23 33 43 53 63 73 83

12 22 32 42 52 62 72 82

11 21 31 41 51 61 71 81

 

For example, the king displacement deltas starting straight forward and moving clockwise are 1,11,10,9,-1,-9,-10,-11 and these will work from any starting position on the board.

 

 

[+Vorticon]

2 hours ago, 1980gamer said:

I stink at this game, but know the rules... I think? Castling is not in my playbook... I have had people do it to me... I have to assume they are not cheating!  LOL

Being as only 1 piece moves per turn, do you have to score each piece on the board each time?

 

Can that scan be reduced?  certainly some pieces will not change? But again, I do not know this game.  I am here for the process. 

I need to learn recursion for a project or some other algorithm and this seems much easier in other languages than TI Extended Basic!

 

However, you may spark something in me the figure it out. 

 

Another thought, early in the game when ALL pieces are still in play,  some cannot move.  Can you skip those pieces from the "scan"?

The Knight would always be scanned I would think. But other non Pawns are locked to start. You could skip them maybe?

 

Yeah, castling was a different challenge altogether  Recursion definitely plays a big part in this program, something UCSD Pascal is quite capable of. 

It's hard for a computer to figure out which pieces are blocked without checking each possibility unfortunately (see my previous post). And indeed, the first few moves are computed faster than subsequent ones because there are fewer valid movement options. 

The main issue here is that UCSD Pascal is quite slow compared to say assembly or forth, but on the plus side it's a very easy language to work with and very structured which is important for complex projects like this one. As I stated before, this is more of an academic exercise than anything else  

[1980gamer]

Because I am trying to figure something out for me.... I am going to ask you related to your project.

I have not used Pascal on the TI.  Back in 1986 I had a class in high school.  I don't remember much about it.  

 

So, in UCSD Pascal, do you have a command similar to GCHAR?  Is it as slow?  That being relative to other instructions.

Do you actually scan the board for "pieces"  Or did you load an array of the board holding the pieces?

Then when you scan the board, you are actually looking in the array versus actual scan of the board?  In my project, I am doing an actual scan... "pieces" can be added randomly.  But I think I need to DROP that method.

 

I was thinking, can the scoring be done while the player is also evaluating a move?  I know you do not know what they will do?  But you per-scanned and know the moves are somewhat limited, Certainly at the start

When the most pieces are on the board.

 

I just paused and thought about the scanning.  Yes, when a single pawn moves, it can open up a few other back row options.  So, maybe that optimization is not as big as I was first picturing.

But as I pictured this in my head, quadrants!  If a piece doesn't Dirty a quadrant, can we skip the scan?  I already know them all to start.

If I move a piece within a section of the board, can I scan just that section?  If I cross, scan just those 2 sections.  50% reduction?

 

Again, I am pretty ignorant about the game.  So, I may not be grasping what you need to do?  I am looking at reducing work.  But obviously, if it does it wrong, then what is the point!

 

I am going to sit back and watch your progress from here.  Thanks for indulging me.  At least you can debug with overdrive!  If that works with pascal?

[1980gamer]

Missed post #41 some how...  That explains a lot and I want to delete my prior post mostly!

 

[+Vorticon]

There are no integral graphics commands to UCSD Pascal and the TI implementation does not include things like GCHAR, HCHAR or VCHAR, so you will have to roll your own.

The initial chess position is stored in the chessboard array with each piece having an assigned numerical value: King=1, Queen=2, Rook=3, Knight=4, Bishop=5 and Pawn=6 for white. Add 10 to the value for black. When generating a move, the array contents are scanned in order to locate pieces and make calculations, and the array is updated with each turn. Temporary mirror arrays are also created to test potential moves against the evaluation function before committing to any particular response.

The computer actually pre-calculates a limited set of player responses during its position evaluation depending on the ply depth and if the player indeed plays these moves, then the response time is immediate since no evaluation is required. However, since the evaluation function attempts to maximize the computer's score while minimizing the player's, I'm not sure if it will frequently succeed in predicting a good player's move  We shall see!

Given the complexities I have encountered, I am utterly amazed how some brilliant programmers have managed to create complete chess programs under 1K (in assembly)... They may not play well, but still!

[1980gamer]

I always wanted to learn this game.  But like most things in life...

I had chess master x000 I don't remember 8000 maybe?  I played 10-15 sessions ( 2-5 matches, depending how fast I lost )

this was before google and youtube to get some instruction.  I learned what pieces could do what and that is about it.

 

Yes, 1K is Incredible.  NanoChess is around these parts from time to time.  Has a nice INTY Basic book also.   https://nanochess.org/chess3.html

 

 

[+TheBF]

1 hour ago, 1980gamer said:

Yes, 1K is Incredible.  NanoChess is around these parts from time to time.  Has a nice INTY Basic book also.   https://nanochess.org/chess3.html

This amazing!  Toldedo Atom chess can be less than 400 bytes in x86 ASM.  I am shocked.

 

https://nanochess.org/chess6.html

[+Vorticon]

 

It's alive! Ok still very dim-witted, but alive...

This is just a test window with the computer playing against itself, and it just nearly checkmated itself in 3 moves! Still having trouble detecting check mate situations as well as getting out of check threats. This test pretty much exercises the entire code base, and at least I know the piece movements are correct and that the board is being updated accurately. I have so far only implemented basic pawn strategies, general piece capture incentives  and king check maximization, but everything else is remains very much random movement.

[+TheBF]

Good on you!  Your efforts prompted me to go looking for what is out their in Forth. 

I found a very old chess game that was originally written for Win32Forth but the version I found was translated to be Demo for the F21 Forth CPU designed by Chuck Moore.

I got it to compile on Camel99 Forth but it is not running yet. The screen stuff needs tweeking for TI-99 and I have not grokked all the code but you inspire me to keep trying.

 

[+dhe]

Bump Bumpedy Bump