The complete SHOGUN story on computers (AND THE ZX81)

General games-related topics
Post Reply
dr beep
Posts: 1638
Joined: Thu Jun 16, 2011 8:35 am
Location: Boxmeer

The complete SHOGUN story on computers (AND THE ZX81)

Post by dr beep »

The complete SHOGUN story on computers
--------------------------------------

In 1976 the boardgame SHOGUN was released.
In 1979 this boardgame became "Game of the year".

I got the game as a birthdaypresent and we played it a lot.
The board has 64 fields with a small piece of iron underneath eash field.
16x on the left, 16x right, 16x up and 16x down.
Together with 16 stones containing a small magnet and a disc each stone will point to a number
on the stone. Due to different discs the stones will react differently on each field from eachother.
Add to this that you can rotate the board and swap stonepositions will give enough randomness to keep the game attractive.

Although I had the game as a kid and the computer became part of the household I never coded a version on the computer.



2010
====
In 2010 I wanted to join the minigamecompetion with a game for the ZX Spectrum.
I thought it would be nice to see a version of this classic boardgame to be played against the computer.
The first thing I had to do was to simulate the board and stones
I picked up the boardgame and rotated each stone on a field to see the order each stone was built.
I could do the same for the board and define 4 playfields to mimic the computerversion with the boardgame.
I decided to set a randomly defined board each time. After playing many games on the board the fieldvalues
of the shogun became quite predictable (even when the board rotated) so it had to be more random than the boardgame.

When you code a version where you can play against the computer you need to store information about the board.
Each field can hold information. I determined each field with the following bits:

; uscvvvii
; u is set to 1 when the field is in use. Technically the rest of the bits can be 0 but even then a stone can be on this field.
; s=piece is shogun. This info is needed to hit the shogun when possible.
; c=colour (or player 1 / player 2 indicator)
; vvv=indexvalue of piece 0..7. Each player has 8 pieces and these bits point to the stones in memory.
; ii=indicator of value from piece 0..3. The information about the value of the stone to display.

When you play on the board each player will keep in mind which destinations a stone goes to.
For a computerversion you need to calculate to which field a stone can move so we need another 2 bits
to determine if a stone can reach another field. We need 10 bits in total to store all information.
The game itself is stored as a 1024 bytes program on tape, but the program will use more memory than 1024 bytes.
For easy access the boardinfo is stored in 512 bytes and another 512 bytes are used to undo each played move to find the best move.
Besides the data in memory the program uses a recursive routine to find each field a stone can go to.
The recursive routine to find the endfield is using the IX-register as a directionfinder.
The intelligence of the computer is simply to do all possible moves with each stone and then determine which move gives the highest score
and finally do the move with the highest score.
The AI had in mind should do the following checks

; 128 = move can hit shogun and win the game
; 64 = shogun is attacked before move
; 32 = move can hit normal stone
; 16 = stone is attacked before move
; 8 = stone is not attacked after move
; 4 = stone is protected by other stone after move
; 2 = stone is moved forwards
; 1 = stone is moved backwards

The higher score in playing forward was part of the AI to give the computer a more attacking gameplay than defensive.

After implementing this AI the game was larger than 1024 bytes and did not fit the compo so I had to alter the AI
to make it fit 1024 bytes again. When a move has an equal score the latest move is kept as best move.
By altering the order in checking each reachable field I did the check on forward moving as the final step.
This was only a change in the table and in the AI the score for moving forwards or backwards could be deleted.
The game fitted 1K for the 2010 MiniGameCompo. You can find the entry here.
https://spectrumcomputing.co.uk/entry/2 ... rum/Shogun



2011
====
After the MiniGameCompo I wanted to port SHOGUN to the ZX81.
I wanted to keep the display as it was, but the ZX81 has no colour so the display was altered
for the ZX81. Since the ZX Spectrum used the border to display who won that had to be altered too.
Most of all the ZX Spectrum used user defined graphics and I needed something like that on the ZX81.
I was aware of hires graphics om the ZX81 so I searched for the routine to make a hiresdisplay possible.

With the display now altered I only had to convert the input and the game could run.
Well, not that simple. As I mentioned the recursive destinationroutine was triggered with IX and IX on the ZX81
is needed to allow displpay of the screen. This routine had to be altered as well to make SHOGUN run on the ZX81.
Also the use of tables in memory had to point to addresses suitable for a ZX81, but that was peanuts.
Due to the extra screendisplay to be coded on the ZX81 the game would never fit 1K so the game was a 2K entry for
the competion in 2011. The AI is the same as on the ZX Spectrum.
http://minigamecompo.weebly.com/2k-page.html



2021
====
To set myself a challenge I thought of recoding SHOGUN but now for the unexpanded ZX81.
The first problem I encoutered was to reduce the board to just 64 fields.
The first two games had a 3x3 display for each stone/field. A shogun had a nice crown on top of the number.
With a 3x display that was easy to do, but the board was 3x3x8x8 fields.

The display of the normal stones wasn't that hard. Just normal and inverted numbers 1 to 4 for player and computer.
The shogun however needed to be recognized as shogun but unlike the hiresversions it needs to be done in just 1 position.
I was thinking of flashing stones, but then I thought about using letters to ressemble the values 1 and 2 which
are the only values on the SHOGUN-stone. I decided to use "I" for 1 and "Z" for 2. Now each stone shows its value and
you can recognize the shogun. The next step in reduction of the code was to reduce the size of the stack and tables
that are used in the previous versions. Although the code is on tape only 1K in size the memory that is used is much more.
Each field had 10 bits of information, this information is doubled for the use of testing a move and undo a move to
test a next move. Each table was also stored on a 256 byte boundary so about 800 bytes were only used to check the board.

Since the check of a valid move from the human player is the first the program does this was the first optimization to do.
This routine used 8 bytes per step on the stack to find valid endfields. A reduction in the stack would gain easy memory.
The routine was altered and not only did it get shorter, it also used 2 bytes less per step on the stack.
The human player was now working, but the AI from the computer still used 10 bits per field.

If somehow I could reduce it to 8 bits then I would instantly win 64 fields when I was able to fix the 256 boundary as well.
I used 2 bits to determine a shogunstone and use of a field. Both were needed since the position of the shogun
was different per player. Also a value of 0 could still mean the field was in use. I altered the setup of the game so 1 stone was used
double to prevent the 0-value and the position of the shogun was made to be the same for player and computer.
Now the value of a stone would always have a value and the shogun a fixed position. 2 bits were won and the table could fit in just 128 bytes.

A field now held the following information:
; ADcvvvii
; A The field is attacked by the computer.
; D The field is defended by the player
; c=colour (or player 1 / player 2 indicator)
; vvv=indexvalue of piece 1..7. Each player has 8 pieces 1 stone is used double.
; ii=indicator of value from piece 0..3. The information about the value of the stone to display.

Besides the compressed screen and reduced tables the game had to show a message when an error occurred, your shougun was attacked
or which player had won. Extra fields on the screen would also mean extra bytes in memory. Since the board has 64 fields and both
players only 16 stones 48 fields remain empty. I decided to use the empty fields for the messages.
A "." is normal empty field.
A "?" is an error in previous move, example move a piece to invalid position.
An inverted "." indicates your shogun is under attack.
A "-" indicates you lost the game from the AI.
A "+" indicates you won the game from the AI.

Finally further optimizations in the code made the game fit in 1K memory.




2021/2022
---------
After coding the 1K ZX81 version I set myself another challenge.
The Odyssey2/Videopac is a gamecomputer with cartridges. This machine has a RAM-pack of 128 bytes.
All the active game data should be stored within these 128 bytes.
The board itself already needs 64 bytes and a backup. I need to find a way to compress information even further

Besides the lack of RAM the stack of the processor can only handle 16 bytes.
My recursive routine could never work on the Videopac. The altered routine in SHOGUN 1K still needs 72 bytes at the max.
The game would be a failure if the recursiveroutine could not be coded in a less stackusing way.
I started in Sinclair BASIC to code a routine that would do the job. I used Sinclair BASIC since it would be easier to show
if it succeeded because the display of the Videopac would be another problem to solve.

I was able to make a routine without using a stack so the first step was taken. Now it only needed to be altered into 8048-code.
The first thing to code on the Videopac would be a visible board with 16 stones. The videopac allows 12 characters and 4 sprites.
Together that would be 16 stones to dispay. The board could be made from the backgroundgrid. Then the next problem.....
With 12 characters and 4 sprites on the board no character was free to make a cursor to select a field and move a piece to a net field.
My solution became flashing the background. With the cursor on the background now stones could be selected.

I needed to store the information of the board in less than 128 bytes on the ZX81.
Each field held information if a stone was there. That ment that 48 fields held info of NOT having a stone.
I skipped all information about a stone on a field and only stored this info on a field.

; ....ADii
; A The field is attacked by the computer.
; D The field is defended by the player
; ii=indicator of value from piece 0..3. The information about the value of the stone to display.

Now the info only had 4 bits and the other 4 bits could be used to store the backup from the field.
The info of each stone can be stored on fixed locations where the location defines each stone and the
value in that memrylocation would tell where a stone was displayd on the field.
The stoneinformation also needs a backup so a total of 96 bytes would fit all info that was stored in 128 bytes
on the ZX81.

Next would be the iterative routine to reach each field. In Sinclair BASIC this routine had 6 variables. Another problem.
Some routines from the ROM I used needed registers that I would need as well. In the end I was able to store the variables from the
BASIC into just 2 registers on the Videopac. I was now able to move pieces over the board.

The RAM is limited to 128 bytes but luckily the program must fit a ROM-cartridge. This is at least 2K so size of the program
is not a problem. I had to find a solution for some selmodifying code, but that was not a problem
The 8048 is a microcontroller much simpler than a Z80. What is lacking is SUBTRACTION. In order to do a subtraction
you need to do a 2-complement addition.

I had an idea about a different AI.
The old AI noticed if a shogun was attacked and held that information as usefull.
It is irrelevant if ths shogun is attacked. It is relevant to know if the shogun is NOT attacked after a move.
This info is relevant not to lose so that info is now set in bit 7.
All info shifted 1 position upwards leaving me 3 bits at the bottom to count the stoes protected by own stones.
Since an attack on the shogun is set in bit 7 the highest value to reach is 7 so it fits the position.

Now we only need information IF we can hit the opponents shogun.
This is now solved by setting all bits to 1. An extra option in the game is that
the AI calculates if a taken stone will cause a player to lose the game with just 2 stones left.
This KILLERMOVE is also a GAMEOVER move so this is also a move that will result in 255.

Furthermore the AI was extended with a 2 level option EASY and HARD.
The EASY-mode skips a few checks and therefore easier to win.
The HARD-mode will also check if the player has set up a trap where a stone can be taken but then
the stone can be retaken by the player. If this results in losing the game the comnputer will not play that move.


; 255 = hit shogun or killermove (before move) v H E
; 128 = shogun not attacked (after move) v H E
; 64 = hit other piece (before move) v H E
; 32 = attacked before move (before move) v H E
; 16 = current stone not attacked (after move) v H
; 8 = protected after move by own stone (after move) v H
; number of stones -current -shogun not attacked (after move) v H
; avoid killertrap from player (after move) v H

This version of SHOGUN has the best AI sofar in all versions I have coded.

When the game worked a lot of extra's were added, a menu, information, sound on/off, 2 player,
a slow move by the computer showing where a stone came from and where it went.

The game is NOT released yet (2022-june-11)



Other SHOGUN-programs
---------------------

2014
====
After coding my Videopac-version I wondered how many versions were coded by others.
I knew that in 2014 TCKSOFT tried a version. I even offered my AI to share.
In the end he coded a version which is less strong than mine as he stated in a reply to me.
https://play.google.com/store/apps/deta ... l=nl&gl=US

2020
====
In 2020 an app on android phone appeared. This version plays quick, but has a very simple AI.
I can win a game within a minute of playing. I can need up to 15 minutes in my own versions to lose the game.
https://play.google.com/store/apps/deta ... =gsw&gl=US

1991
====
I found a note to a Sam Coupe version of the game from 1991.
This was a 2 player version only so no AI from a computer.

Conclusion
==========
2010 was the first year to be able to play SHOGUN against the computer.
The game can be coded in just 1024 bytes.
The game could use more macchines to have it run on. Sofar only a few machines support a game of SHOGUN

Future goal
===========
Trying to code a 1K version with the AI (and perhaps the iterative routine) from the Videopac
on the ZX81.
dr beep
Posts: 1638
Joined: Thu Jun 16, 2011 8:35 am
Location: Boxmeer

Re: The complete SHOGUN story on computers (AND THE ZX81)

Post by dr beep »

The last weeks I coded a SHOGUN version for the TRS80 MC10, my first computer.

At the moment I am recoding the 1K ZX81 version.
I am working on a shortened enddestination routine that also doesn't create a large stack.

I am hoping to add 2 player mode and 2 levels of AI in a new 1K version.
dr beep
Posts: 1638
Joined: Thu Jun 16, 2011 8:35 am
Location: Boxmeer

Re: The complete SHOGUN story on computers (AND THE ZX81)

Post by dr beep »

2 player version is working and I have 101 bytes to add the computer AI.
dr beep
Posts: 1638
Joined: Thu Jun 16, 2011 8:35 am
Location: Boxmeer

Re: The complete SHOGUN story on computers (AND THE ZX81)

Post by dr beep »

WIth only 20 bytes left (assuming the stack will not be larger tahn 16 bytes)
I will try a whole new approach.

I expect the AI going slower. but I would gain 64 bytes.
Post Reply