New game project: Phoenix Chess

[+Vorticon]

Yes, a chess game. Contain your excitement please!

This has been something I wanted to do for a very long time, as I have long ago exceeded Video Chess' level of play and there was only one other available alternative for the TI, namely a Sargon 1.0 conversion by Michael Swiridenko (it's on the TI Gameshelf) which was did not play much better and was super slow at higher levels.

Can I do better? I have no idea. This is a complex topic of which I know very little from the programming aspect, so I will learn as I go and keep a log of my progress here. There are no guarantees I will end up with a playable product or a challenging one, but I've got to try

 

I picked UCSD Pascal as the language for the project, primarily because it has a lot of advanced features simply not available in any other TI language (don't know about gcc though), like complex data structures (records, sets, linked lists) which will be crucial for a project such as this. Furthermore, the ability to use separately compiled units will be a huge help in debugging. And finally, through the use of program Segments, I will be able to dynamically move code segments in and out of memory during runtime, thus allowing me to have a much larger program than otherwise possible with the limited memory of the TI. Did I mention I also have a very soft spot for Pascal?

Speed may be an issue, but since this is hardly a graphics intensive project, it should be fine, and there is always the option of using external assembly routines as needed for support.

 

Why the name? Well chess has been kind of dead on the TI for a while with nothing new happening, so I felt it was appropriate to make it rise again in the collective minds of the TI community

 

There will likely not be much to show visually for a very long time as most of the work will be mostly data processing behind the scenes so to speak, but I will try to post regular updates on my progress and challenges.

 

More to come

[ti99_forever]

Hear hear!

Big fan of UCSD. And chess. Can't wait to see your progress.

[Tursi]

Definitely be curious to read about how you tackle the algorithms, I've gone through the mental exercise a few times and never wrapped my head around it! But I'm not very good at chess either!

[globeron]

Are you based in Phoenix, AZ?

(are there any good TI-99/retro shops? I am in Phoenix next month 18-25 Feb, but quite busy with

the conference and not sure how much spare time I have)

 

-----

 

Wow (with the upgrade of Windows 10 and Xbox, I was looking at their Chess and I also was thinking about it how to create

the algorithms in a program) and how it makes decisions. As a kid I am a chess player (my father taught me, but after that went for Chess classes

and played competition as well) and TI-99/4A Video Chess was one of the first modules we had (and the 1st module I plugged in after 30 years

when unboxing it and my kid was laughing at me when it makes the start-up screen sound).

Also I played Sargon 1, both advanced levels are slow and lower levels are not challenging.

 

UCSD-Pascal - I have the P-code card here (then I need to pull out my PEB-Box) or use the alternatives (see ti99videos on youtube)

so that a larger community can also try it out in the emulators. But I never ran any program on it and I do not have programming experience

with UCSD Pascal, but I should be able to read and test it. There is another person (here on Atari Age forum in Netherlands) who has much

more experience with UCSD-P.

 

When I was a kid I remember I had a chess program listing (maybe MSX-Basic) of a Chess program, which I tried to convert to the TI (unsuccesfully).

(maybe next week I can find it, it might be on my cassettes).But what I think there might be good source codes and libraries somewhere (GitHub ?) on

internet already which can help to port the game to USCD-Pascal ?

 

Do you know if UCSD-P can support graphics (e.g. can it address the 9918 or 9928 (F18A) or 9938 (80 Column card) or 9958 video chipsets?

(or is it more text based).

 

Looking forward to your updates!

[+Vorticon]

Yes, UCSD pascal supports some graphics, certainly sprites, but it's slow at rendering those. Natively, it only supports the graphics mode, the multicolor mode, and the 40 col text mode. However, you can use external assembly routines to expand it any way you want. Anders Persson, the UCSD pascal guru, has managed to run bitmap graphics on it for his turtle graphics module.

 

Regarding how to program chess, it's broken down into several steps:

• Board representation
• Move generation
• Analysis

I have a pretty good idea as to how to do the first two and will be elaborating on that in upcoming posts. The third one however is going to be the tough nut to crack given the limitations of the TI memory. It's fairly straightforward to create a simple chess program (it was done in under 1K on the Kim 1 computer!), but coming up with a program that actually plays well is magnitudes more difficult.

 

This topic is going to likely end up being a tutorial on chess programming, hopefully with copious input from the TI community

[+mizapf]

This topic is going to likely end up being a tutorial on chess programming, hopefully with copious input from the TI community

 

What about a broader scope: AI programming on the TI? (I mean, in addition to that)

 

Well, of course not hard AI, but simply: How to create a clever computer opponent? In the book from Russel and Norvig I found a section about the "Wumpus world"; I think this can be a pretty interesting and valuable endeavor.

 

(RIP Marvin Minski - I have an autograph in my edition of "The Society of Mind" which I got after his talk at the University of Vienna in 2000; I think it was the EMCSR2000 conference)

[+dhe]

I've always been interested in Chess on the TI.

 

Sargon - could have been much better with the addition of know opening moves. I have not studied it in a long time, but I think most of the games in the 80's had programmed know opening moves libraries that went up to the first 5 - 10 moves.

 

This really gives the computer some more leverage if your play blitz chess (5 minutes on each clock) and if you have an AMS card you could go lots higher.

 

I have also read TI Video Chess had an advanced level, but they couldn't seem to debug it, so it was excluded from the released product.

 

It would be interesting to know if either Sargon or Video Chess are thinking about their next move in the background while waiting on you....

[+Vorticon]

 

What about a broader scope: AI programming on the TI? (I mean, in addition to that)

 

Well, of course not hard AI, but simply: How to create a clever computer opponent? In the book from Russel and Norvig I found a section about the "Wumpus world"; I think this can be a pretty interesting and valuable endeavor.

 

(RIP Marvin Minski - I have an autograph in my edition of "The Society of Mind" which I got after his talk at the University of Vienna in 2000; I think it was the EMCSR2000 conference)

 

I did not know that Marvin Minski has passed away

This topic is certainly worthy of its own thread, which I actually started a while back here: http://atariage.com/forums/topic/208936-musings-in-machine-intelligence/?hl=+musings%20+in%20+artificial

[+Vorticon]

I've always been interested in Chess on the TI.

 

Sargon - could have been much better with the addition of know opening moves. I have not studied it in a long time, but I think most of the games in the 80's had programmed know opening moves libraries that went up to the first 5 - 10 moves.

 

This really gives the computer some more leverage if your play blitz chess (5 minutes on each clock) and if you have an AMS card you could go lots higher.

 

I have also read TI Video Chess had an advanced level, but they couldn't seem to debug it, so it was excluded from the released product.

 

It would be interesting to know if either Sargon or Video Chess are thinking about their next move in the background while waiting on you....

 

Yes, opening moves are definitely necessary in order to give the computer a fighting chance This is where linked lists will come in handy.

I have always wondered why there was only an intermediate level in Video Chess. I guess now I know why! What a shame the programmers could not figure it out...

One of the features of UCSD Pascal is concomitant execution of program segments, which I plan to fully leverage to have the computer think on the player's time.

 

This is definitely going to be one of my most challenging projects to date, and I'm looking forward to breaking it down into small bits and tackling it piecemeal. But first I need to really dig down into UCSD pascal and get fully familiar with all it has to offer. This weekend I'll post my framework for the board representation as a first step.

[+Vorticon]

OK here we go:

The first consideration will be how to represent the chess board in memory. I am opting for the simple one dimentional array, with each position indexed by the number composed of the combination of the y and x axis.

  1  2  3  4  5  6  7  8
8
7
6
5
4
3
2
1

Each square on the board will be represented as a number made up of the combination of the y and x axis. For example, the lower left square will be 11, the upper right square will 88 etc... One of the advantages of this scheme is that it will be easy to tell if a piece lands outside the board if its final square value is less than 11 or greater than 88. Another advantage is that is simplifies the calculation of the legal movements of each piece by having a table of all the possible displacements of each piece. For example, from any starting square, the knight can have the following displacements: [21,12, -8, -19, -21, -12, 19, 9] which are added to the value of its starting square to calculate the target square (go ahead and try it!). Of course some of these displacements will be invalid if they land outside the board as discussed previously. Therefore, we will have a displacement table for each pawn, rook, knight, bishop, queen and king, noting that the queen displacements will simply be the combination of the rook and bishop ones. Note that the pawn table will take into account the en passant capture in addition to the standard displacement of 10. If memory becomes tight, there is a way to reduce the size of the long range pieces (rook, bishop and queen) displacement tables by having them contain only the first displacement in each direction and then having the program calculate movement "rays" in each direction by simply repeating the displacement. This is more computationally intensive but does save a little memory. At this point in time, I'd rather use memory and shave off computation time, but we'll see how things go as the program develops.

 

So now we have an array of integers called board[11..88] to represent the chess board. This representation does require an 88 element array instead of a 64 element one because indexes 1 to 10 are not used. The displacement tables will be arrays as well: N[8], R[28], B[28], K[8], P[3]. The queen will not have a dedicated array because the program will simply use the rook and bishop arrays sequentially to determine valid queen moves. The pieces will be represented as such numerically:

 

Black: K=01, Q=02, R=03, N=04, B=05, P=06

White: K=11, Q=12, R=13, N=14, B=15, P=16

 

The board array will be filled with the values of the pieces in each location, after initialization with 00 in all locations.

 

Next time we'll talk about the actual valid move generation procedure and tables. Until then, I'll start working on implementing the above in UCSD Pascal.

[+Vorticon]

The board and piece initialization as detailed in the previous post are now complete. There is an INIT procedure that does all this, and I defined it as a SEGMENT procedure since it will be needed only once per game. It will therefore be taken out of memory once it is completed during runtime. The piece displacement data was stored in a file of integers on disk since Pascal has no facility for DATA like statements as in Basic. It took me a while to re-acquaint myself with file handling in Pascal though

 

I have decided to code the project directly into the UCSD Pascal environment rather than copy and paste from a text editor because I did not want to lose the formatting. It was slow painful at first, but I quickly got the hang of it and it's surprisingly not that bad now One problem I have though is that I have no way to access the contents of my work disk outside of the UCSD system in order to post the source code here. If I use TI Imagetool or TIDIR, all I see is a single PASCAL file that appears empty. Is there a way to circumvent this?

 

Now on to the next step, which is move generation. This part will likely be an iterative process required with each game 1/2 ply up to the desired search depth, and will be a segmented unit. In a nutshell, for each side, the routine will generate all possible legal moves for each piece and store them in a move table in the format <starting square:ending square>. This is done by simply adding the possible displacements for each piece to its starting square value and checking whether the resulting square is empty or not and that it is within the bounds of the board. Only the moves that land on an empty square will be stored. Special checks will be made for castling, moves that cause the king to be in check, and pawn en-passant moves. If a particular move lands on an enemy piece, then that move will be stored in a capture table in the format <value differential:starting square:ending square>. Each piece type is assigned a value based on its importance:

• Pawn: 10. However, if it is within 2 squares from the promotion row, then its value becomes 50 (similar to a queen)
• Bishop: 20
• Rook and knight: 30
• Queen: 50
• King: 100

So for capture moves, the value differential will be attacked piece value - attacking piece value. This will help prioritize the capture decision later in the game by giving higher priority to capturing the queen rather than a pawn if both options are available for example.

 

From there, the search function will take over to weed out the good moves from the bad, and will really be the determinant factor in how the game performs. We will be moving from a relatively passive function to nothing less than an attempt at extrapolating the essence of human analytic power. Piece of cake But that's for next time...

[+Vorticon]

Move generation is turning out to be a lot more complicated than I initially anticipated and will be closely tied in with the search and position evaluation functions. The way it looks right now, for each move generated on the computer side, a full set of moves will be generated on the player side as a response with each response going through the evaluation function and scored. This will be the basis for sorting out the computer moves from best to worst. The hope is that a particular move will score high enough as to preclude continuing the move generation any further (i.e. a cutoff), whether through a positional advantage or a high value capture. From there the top few moves (number to be determined) will go through the same process again as many times as the desired search depth. As you can imagine, the whole process will be very time consuming on the TI, which is why it will not be practical to check all moves and responses past the first round of move generation. How well that will work remains to be seen because the computer could be ignoring apparently mediocre moves which could a few plys down the line become killer moves... The evaluation function is really key here, and I have not yet determined how I am going to proceed here.

The best way to represent the move and capture tables in Pascal is through the use of linked lists of records since the size of the tables will wildly vary depending on the number and type of pieces remaining on the board. It would be very wasteful from a memory standpoint to allocate a static large array for each table with the maximum possible number of elements, while a linked list's size will be dynamically adjusted as needed, with the downside being the need for extra manipulation for maintenance. The tables will look something like this:

type
  moveptr = ^movelist;
  captptr = ^captlist;
  movelist = record
               start : integer;
               end   : integer;
               next  : moveptr
             end;
  captlist = record
               start : integer;
               end   : integer;
               value : integer;
               next  : captptr
             end;

[+Vorticon]

Here's the high level move generation algorithm I am contemplating so far. I have tossed the idea of using the top several best moves to search in subsequent plys given the exponential increase in computational time required, and so I will only use the single best move found by the evaluation function per ply. A temporary board will be created reflecting that best move as well the best player calculated player response, which will be used as the basis for the next ply search, and so on and so forth up to the desired search depth. A linked list will be maintained containing the best computer and player response for all the searched plys, so that if the player does indeed play the expected response, then no search will be necessary and the computer will automatically play the next move stored in the list.

 

 

Move generation algorithm.pdf

[Fredrik Öhrström]

http://www.nanochess.org/chess6.html

[+Vorticon]

http://www.nanochess.org/chess6.html

 

Very interesting indeed. The original Atomchess at 398 bytes is not relevant however since it does not implement the full rules. Atomechess Reloaded however at 831 bytes of x86 machine code, while having a non-existent strategy and thus extremely weak, does defend itself quite effectively and I am thoroughly impressed. Below is a sample game I played against it, and if you follow it you will notice that its moves are pretty random (by move 8 I pretty much had total control of the board) unless there is a direct threat of checkmate or capture in which case it fends itself pretty well. There was even one instance of it threatening to fork my rooks! I played a pretty lazy game trying to see how the program responds to different situations, and overall this is a very decent attempt given the size of the program

1. e4 h6
2. Nf3 Nf6
3. Nc3 h5
4. Bc4 Ng4
5. h3 Nf6
6. d3 h4
7. O-O Nh7
8. Nxh4 g5
9. Nf3 f6
10. Nd4 g4
11. Qxg4 Ng5
12. Bxg5 fxg5
13. Qxg5 e6
14. Qg6+ Ke7
15. e5 Rh6
16. Qg8 Rh5
17. Rfe1 d5
18. Bb3 c5
19. Nf3 Nc6
20. Ng5 Qe8
21. Bxd5 exd5
22. Nxd5+ Kd8
23. Nf7+ Kd7
24. Nf6+ Ke6
25. Nxe8 Ke7
26. Nf6 Rf5
27. Qh7 Ke6
28. Qg6 Rxf2
29. Kxf2 Nd4
30. Ne4+ Ke7
31. Qf6+ Ke8
32. Nfd6+ Bxd6
33. Nxd6+ Kd7
34. Qf7+ Kc6
35. Rac1 Kb6
36. b4 cxb4
37. c4 bxc3
38. Rxc3 Nc6
39. Rb1+ Ka6
40. Qc4+ b5
41. Qxb5# 1-0

What I'm trying to do with Phoenix chess is a little more ambitious however

[+Vorticon]

Yes, the project is still very much alive I'm still working on the move generation routine which is proving to be extremely challenging from an implementation standpoint, with many levels of nesting as well as recursive processes which I had never tackled before. The good news is that UCSD pascal is very feature rich particularly when it comes to data structures, a fact which is making implementation much easier. I'm about 3/4 of the way done with the move generation code, which however remains untested at this time. Debugging is going to be a bitch...

 

I have to admit though that I am not making it any easier on myself by doing all the coding directly within the UCSD pascal OS environment rather than using a modern text editor and copying and pasting the code in. Why? Well, I want to see if I can develop a complex program within that OS without the help of modern programming tools. My only concession to modernity is the use of the Classic99 emulator for portability and reliability reasons (my p-code card seems to be a little flaky). Oh how I miss 80 columns! Please don't judge me

[+Ksarul]

There are supposedly only half a dozen or so changes required to one of the p-Code Card GROMs to make it work in 80-column text mode. . .the German user's group from Munich actually did those mods using a little daughter-board they designed for it, but I lost contact with the owner before I could document the board and get the necessary code changes.

[+Vorticon]

Too bad... This is definitely an environment where 80cols will make all the difference from a usability standpoint, particularly when there are a lot of indentations. In some of my routines, I have to scroll the screen horizontally twice to get to the right-most statement given the level of nesting.

[ElectricLab]

Chess anyone?

 

I recently completed a chess game that can be used to play with other TI users on the web, using Stuart Conner's web browser.

More info at: myti99.com

 

Basically I took a different approach, so that I could write the code using modern object-oriented concepts, and I created an API to separate out the management of the boards, games, and validate moves, etc. I did this so that other retro platforms might be able to participate with only a local program needing to be created to use the API and "glue" it to the platform in question.

 

This project actually stemmed from another project I was working on, which was a 3D chess-like game. There were lots of new types of pieces that the game designer was still working on, but I needed to get busy on the coding, so it occurred to me to try creating a Piece object and have its allowed moves placed in a SQL database. This allowed us to program in new pieces and moves as they were designed - they could be just inserted into the database and Bob's your uncle. I ended up defining attributes of chess pieces, such as:

• Can a piece move over others or must pass through clear spaces? (Knight is the only one that can jump)
• Can a piece move differently on its first move? (Pawn can)
• Must a move in a particular direction require a capture (Pawn moving diagonally)
• Can a piece be left in a capturable space? (King's can't be in check)
• Can a piece move in only one direction? (Pawns)

All of these support a Z axis for the 3D chess, and I ended up with a flexible data model that I decided to exercise the system by inserting data for standard 2D chess pieces. Then I learned about Stuart's web browser via AtariAge and I thought it would be easy to make a glue program to use this API and to serve up pages in Stuart's custom (and brilliant!) 99ml markup language.

 

 

The API controls everything, and basically a call is made to it in order to make chess moves, and all the validation rules are applied there, making the glue program relatively dumb and really just the "display layer". The API can be used to get the status of a particular match, and returns a blob of data containing all pieces remaining on a board and their locations.

 

If someone were so inclined and wanted to play with AI without having to program all of this chess and move logic, one could register a user at myti99.com and use its credentials to access the API and:

• scan for open games and join them
• scan for games for which it's "my turn"
• dump out the status of the board to XML or JSON
• submit moves

Basically you could make a chess player and experiment with algorithms to play chess. I want to do this eventually if I find the time. I was thinking of making a really dumb chess bot that just made random moves - I might even be able to beat it then

 

What I found the most tricky part of chess logic is:

• Are we in check? This wasn't too hard all since I made methods like Piece->determineMoves so I could iterate through all opponent's possible moves to see if my king is in threat.
• Is my move legal? This requires iterating through a piece's allowed moves as defined in the database.
• Are we in checkmate? I never did finish this but it requires determining that a player has no valid moves remaining on the next play. Sounds easy, right?

 

This engine was made for a product that never made it to the market, and I was given permission to do with it I want. Some day, I might get around to implementing a 3D version which might be fun.

 

Anyway, if someone wants to see what I've done, I'd be glad to share. I did all the backend in object-oriented Perl, including the API. However you could use ANY language to access the API and do your thing, leaving all the validation to the backend. One could write a better-looking chess game that ran right on the TI, and was multiplayer by using this API.

 

PM me if you want more details. The API is fairly well documented.

 

-Corey.

Edited March 10, 2016 by ElectricLab

[+Vorticon]

Nice I probably will use this as a test bed for Phoenix Chess once the engine is complete and see how well it performs.

Move generation and validation is the most computationally intensive part of any chess program. Try validating castling for example... The latter is the last piece of the move generation code I still have to tackle. It's not "hard", just computationally taxing.

My approach to the king being in check is simple: during move generation, each piece is moved according to its legal range of displacements on the board, and I make no attempt at validating king's checks during that phase. The piece simply replaces whatever happens to be in the final square. In the evaluation and scoring phase, the board will be scanned, and if the king is missing, then the whole move ply is scored 0, thus invalidating it as a possible move choice for the AI. This is a lot faster than trying to validate during move generation.

[ElectricLab]

At first I had move invalidation, where a move was made and "Saved" in the database, but then if it was invalid, I had to roll it back. I decided to do it in memory instead which is much faster.

 

The trick with AI s being able to store board state and multiple iterations of possible moves if you're scoring moves to narrow down the best move.

 

Let me know if/when you want to use my system's API.

[+Vorticon]

 

The trick with AI s being able to store board state and multiple iterations of possible moves if you're scoring moves to narrow down the best move.

 

 

 

My implementation has it scoring each possible move (computer and possible player response) in a given ply as it is being generated and represented on a temporary board. After the entire move generation is complete, only the move that scored best is retained in a linked list of best moves 'x' ply deep. The only exception is the first ply search where the top 'x' moves are retained and each searched down to the selected depth with the one yielding the highest score at the end of the deepest search depth being retained for the next plys. This strategy prevents the computer from falling for a gambit trap for example which may initially score high on the first ply because of the initial material gain but then leads to disaster.

I have not yet defined the evaluation and scoring algorithm though, and a lot of thought and research will have to go into that.

[+Vorticon]

Yup, still working on it. The code for the move generation is finally complete, and accounts for en-passant capture as well as castling. The latter part was quite onerous in processing requirement as expected. None of it is tested as of yet though as I just managed to get all the source compiled successfully after rooting out a gazillion syntax and structure errors from the 700+ lines of code to date. It will likely take me a couple of weeks to debug the code logic, particularly the recursion part, given my limited hobby time these days... I'm really curious as to how long it will take the move generation routine to come up with a list of best moves. At the moment I am arbitrarily setting the maximum number of best moves to 5 and the deepest ply depth to 6, but this may need to be adjusted depending on processing speed.

[ElectricLab]

Looking forward to trying it out! I have plans to refactor some of my chess code after being blown away by the <1k tiny chess games that I've learned about thanks to this forum. Such a fun project.

[+Vorticon]

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 . Next is flagellation...