CONNEX (1982) (With source)

[orac81]

CONNEX is a version of the well known "4-in-a-line" game
(Connect-4), for any Commodore computer (C64, C16, PET, VIC, etc).

Download here:

connex8.zip

(39.97 KiB) Downloaded 170 times

connex-vic1.png (2.83 KiB) Viewed 4829 times

Or github:
https://github.com/orac81/miniapples/ra ... onnex8.zip


Contents of zip file:

"connex8bas.prg" - Basic source version to run on any Commodore.
NOTE: load with ",8" not ",8,1" (its located at $0401 so PETs can load.)
"connex8c64.prg" - Compiled c64 version.
"connex8c16.prg" - Compiled c16/+4 version.
"connex8vic8k.prg" - Compiled Vic20 8k+ version.
"connex-zen-vic5k.prg" - Original Basic Vic20 1982 version. (named ZEN)
"connexg7ansi.txt" - Generic portable ANSI/MS BASIC text version.
(Should run on any old computer - BBC, Apple, PC, etc)

The game is quite simple. Two players (White and Black) takes turns to drop a piece down a column on a 7x6 board. The first player that makes 4 in a line horizontally, vertically or diagonally wins.

When you first run CONNEX, you can type "X" to change the board width (from 4 to 10 columns), or "C" to change screen colour.
Then select "1" to play against the computer, or "2" to play another human.

During play, use these keys:

1-9 - Play the column you want. (0 for column 10)
G - Make the computer take your go.
A - Make the computer auto-play.
I - Change the IQ play level.
Q - Quit game.

connex-c16-1.png (2.97 KiB) Viewed 4825 times

( 10 Column wide board)

CONNEX started life as a PET program in 1980, then was ported to the VIC20 in 1982, and published.

The "connex-zen-vic5k.prg" VIC20 version of CONNEX was first published in Personal Computer World Magazine, Jan 1983.

https://www.worldradiohistory.com/Perso ... _World.htm

This original VIC version was very widely copied to software libraries around the world, and was re-published (unknown to me!) by Artic software, and many others. (they even made cassette inlay art for it!)

CONNEX only uses a simple 1 ply search, but the evaluation is suprisingly effective. It assigns an evaluation in each direction based on how many pieces in a row a move makes (or blocks), and whether the ends are "open".
The IQ=2 mode then subtracts the evaluation (divided by 4) for the square above the played piece, since playing a position enables access to that square for your opponent. This simple idea is suprisingly effective for a BASIC program that cannot really otherwise do deep searches. The ec() array adds a center bias - central moves are best.
I resisted the idea to add hires GFX, and left it as a "PETSCII" program.
(Note that the older versions do not have all the commands listed above.)

I have a more modern C version of CONNEX which will do deep searches on PCs, to be ported/ released later.

Anyway I hope someone enjoys this little bit of BASIC history.

=============================================
The source code is released as free software under the GNU GPL3 licence, see GNU website: www.gnu.org/licenses/gpl-3.0.html

[Lechuck]

Very nice version, indeed. Your algorithm is certainly effective. I've tried it several times and, especially with IQ 2, it's very hard to beat (in fact, with IQ 2, I haven't been able to win).

I tried programming this game in Basic when I was younger and never got anything that was challenging to play with. In fact, since I couldn't get the VIC to play well enough, that version ended up being a 2-player-only game.

More recently, when I got back into the VIC-20 world, I programmed it again, but in Assembler, using a MiniMax algorithm. The version is here, if you want to try it out:

https://sleepingelephant.com/ipw-web/bu ... 15#p113398

In my version you can choose between easy, normal and difficult (which correspond to checking with depth 2, 3 or 4 in the algorithm) and after testing your version with IQ 2 against my version a few times, I could only draw (and only if I played my version at the maximum depth level, that takes 'some time' to think ):



Cheers

[orac81]

Interesting, thanks for that!
When you say you use minimax, does your program use alpha-beta pruning? Its simple to implement, yet will reduce the size of the search tree as much as 2x square root(node count) with optimal move ordering.

https://en.m.wikipedia.org/wiki/Alpha-beta_pruning

Otherwise its down to tinkering with evaluation factors.

Expanding a bit on what the basic code does, the routine at line 500 scans 4 direction pairs (510 for d=0 to 3) counting the number in a row playing either side that square would make (n=1..4) and how many "open" ends there are (o=0,1,2) to create a look up into array e(), (read from data in 9600) which is added to eval (e). So 4 in a line scores 1000, 3 in a line with open ends 16, blocking an opponent 4line is 120, etc. So for the data in 9600:

Code: Select all

n:  0  1  2  (#open ends)
---------------
1:  0  2  3
2:  0  4  6
3:  1 12 16
4: 1000..

After reading your post i decided to try my C version against this old Basic vic version. The C version would draw or win on depth 5+ ply, but could loose the odd game on lower levels.
It is surprising that a simple 1 ply evaluation can work that well.

Anyway the C version compiles fairly well with VBCC, at some stage I will release that too..

[Lechuck]

When you say you use minimax, does your program use alpha-beta pruning? Its simple to implement, yet will reduce the size of the search tree as much as 2x square root(node count) with optimal move ordering.

No, it doesn't use it. I remember having read about branch pruning when learning how minimax algorithm works, but didn't implement it (I thought that it might make it more complex to implement and I wasn't even sure I would be able to implement it correctly). Something to consider if I ever go back to that game. It could certainly speed up the calculation process that, for depth, 4 is very slow...

After reading your post i decided to try my C version against this old Basic vic version. The C version would draw or win on depth 5+ ply, but could loose the odd game on lower levels.

Yes, that is consistent with the result I got. With depth 4 (the max depth in my version), it only draws (at least the times I have tried it)

It is surprising that a simple 1 ply evaluation can work that well.

Yes, agree. It is very neat and smart your way of implementing it. Congrats!

Cheers

[wimoos]

Thank you for this ! I remember trying to get something like this going, back in the 80s.

Astonishing to see that the Austro version improves the response time here from 12 down to 3 seconds on a move.
I went to build a WimBasic version of this game and managed to improve it from 12 to 7 seconds on a move.
Total size of the WimBasic version is less than 2.5k and comprises less than 100 lines (cheated a little by removing all lines not suitable for VIC20).

Regards,

Wim

[orac81]

I didnt go far down the road of optimization of the basic version for compiling, since I wanted to keep it close to the original simple basic program, doing enough to make it run on different cbm machines, adding a little colour, help text etc.
For example I used a 2d board array, which means a slow multiply for each board access. In C I use a BYTE array, and use a macro like

#define BPOS(X,Y) ((X)+((Y)<<4))

avoiding multiply to find a board pos.

Austrospeed is a fast p-code compiler, but it doesnt offer a lot of options. Its a shame its doesnt allow the code to be located higher than $1201, to allow UDG hires graphics. That would a nice hack for someone to do. The source is out there somewhere, there is also a +4 austropeed decompiler too.

I used BASIC64 to build the 64 version, that compiler has some nice features, ie you can declare integers with rem macro
10 rem@i=var,var,...
and switch between pure machine code and p-code, so you can compile sections to be fast, and keep the less critical parts as compact p-code. Overall BASIC64/128 might be the fastest 6502 compiler.

Hacking BASIC64 to compile for the VIC20 might not be too hard, it has near identical basic rom/page zero ram usage, it would be a question of reverse asm of the library blob and relocation for vic20, a little utility could do the conversion. I think the compiler already allows code start loc to be specified.

Well done for making wimbasic compiles so small, that is useful for the VIC, i will have a look at it. The library overhead for austrospeed is 4k for the VIC20, and 8k for the C16/+4, so yours at 2k is very good. The c16 version of Connex only just runs on a c16.
As for speeding up wimbasic, maybe adding integer declaration macros like BASIC64 and bitshift to avoid multiply would be enough to make up the speed. Also adding constant declares, constant folding can make a big difference. Some compilers use the fast multiply, which uses a 512 byte lookup table, a trade off between size and speed..

[wimoos]

One interesting find that I did is that the arrays X() and Y() are not necessary.
After reading in from DATA, array X() holds { 0,1,1,1 } and array Y() holds { 1,1,0,-1 }.
Referring to these elements (Q = X(D) and R = Y(D)) is the same as Q=SGN(D) and R=SGN(2-D), respectively.

Thus, DIM X(3) and Y(3) can be removed, the FOR loops with the READ statements can be removed and the associated DATA lines can be removed.
There are more capabilities in BASIC V2 ROM than we are aware of.

Regards,

Wim.

[Mike]

Well done for making wimbasic compiles so small [...] yours at 2k is very good.

WimBasic is a BASIC extension, not a compiler. That means there's 2.5 KB tokenised BASIC text plus 8 KB for the BASIC extension (call that library overhead if you want), so there ...

[wimoos]

WimBasic is not a compiler, but a BASIC extension to the interpreter. It sits in BLK5, and adds dozens of new commands and features to a stock VIC20 or a VIC20 with regular RAM upgrades.

In the CONNEX game, the core algorithm routine looks like this in WimBasic.

Code: Select all

1 DIME(1,9):FOR C=. TO 1:FOR X=. TO 9:READ E(C,X):NEXT:NEXT
...
10 £E=EC(X):FOR D=. TO π:£Q=SGN(D):£R=SGN(2-D):FOR K=1 TO 2:£N=.
11 £I=X+£Q:£J=Y+£R:WHILE B(£I,£J)=K:£I=£I+£Q:£J=£J+£R:£N=£N+π:WEND:IF B(£I,£J) ELSE £N=£N+1
12 £I=X-£Q:£J=Y-£R:WHILE B(£I,£J)=K:£I=£I-£Q:£J=£J-£R:£N=£N+π:WEND:IF B(£I,£J) ELSE £N=£N+1
13 £E=£E+E(ABS(C-K),MIN(9,£N)):NEXT:NEXT:RETURN
...

Main speed improvers are: SuperNumbers (variables with a £ sign) and the WHILE/WEND commands. And, it is faster to use π instead of 3.
Using π here is safe because £N won't be larger than 9, and the added .1416 fractions together will never reach 1.0.
These optimizations bring response time down from 12 seconds to 6.2 seconds on an IQ=2 move.
The tokenized BASIC text is now 2252 bytes and the program comprises 73 lines.

Regards,

Wim

[orac81]

Thats an interesting optimisation using sgn(), there is always a way to improve code. I wrote that x(d) y(d) code on a PET a long time ago. The better way (as done in the C version) is to have a simple single dimesion board array, b%(), then access with b%(x+y*16), then the direction var become just one, the eval called with d=1,15,16,17.. In the time critical parts its all addition, no multiply!

Yes I now see how wimbasic is working. One of those what-if's is whether commodore went the right direction after basic 2. The very early MS Basic offered a floating point interpreter that could run on a 4k altair 8080. But by the time of the 64 they still used the same primitive system, only 2 char var name, slow search for vars and goto targets, no proper int arithmetic, etc.

In contrast, other systems (hp, atari 800, bbc, apple integer basic) took something closer to an "interpiler" approach. A full version of that would be tokenising/resolving long var/proceedure names, constants, etc, (even tokenising as each line is typed), offering better structured features, generating something close to pcode. That would have been the thing to fix before implementing those other gfx features in basic 3.5/7.

I did start writing a version of Basic that did this, but its not finished..

[Mike]

One of those what-if's is whether commodore went the right direction after basic 2. The very early MS Basic offered a floating point interpreter that could run on a 4k altair 8080. But by the time of the 64 they still used the same primitive system, only 2 char var name, slow search for vars and goto targets, no proper int arithmetic, etc.

At that time, priorities were set to cram the most functionality into a given ROM size, possibly at the expense of speed. Often enough, also a quick 'time-to-market' took importance over everything else.

When it comes to scientific applications, you want to do stuff with float, an integer-only BASIC is completely unusable for that! Put the other way round, it's fairly easy to add integer variables for more compact storage on top of a float library, and that had been the design choice of MS BASIC then.

In contrast, other systems (hp, atari 800, bbc, apple integer basic) took something closer to an "interpiler" approach.

Not that I know of.

Atari had a bog-standard interpreter, Apple Integer BASIC was somewhat faster but as implied, integer-only and thus out of question for serious stuff. Acorn actually had a very efficient interpreter indeed, developed in house, with later extremely fast re-incarnations on the Acorn Archimedes. However, it also had definitely a bigger ROM size (about 32K for BASIC and Acorn MOS combined) and ran on a 2 MHz 6502, so the comparison is somewhat skewed.

What HP BASIC are you actually referring to?

A full version of that would be tokenising/resolving long var/proceedure names, constants, etc, (even tokenising as each line is typed), offering better structured features, generating something close to pcode.

This is what you got from later versions of Acorn BBC BASIC, but ...

That would have been the thing to fix before implementing those other gfx features in basic 3.5/7.

... BASIC V3.5 and V7 also offered extensions for program structure - IF .. THEN .. ELSE, DO .. LOOP in both, BEGIN .. BEND to enable multi-line blocks within selection structures with V7, trap/error and event handling, the latter which required an own runtime stack instead of sharing that with other stuff on the 65xx hardware stack, which would have made it unfeasible to unwind the stack.

To note, even BASIC V2 already tokenizes the program lines as they are stored in program memory.

If you point to the graphics commands as criticism, the question remains whether any of the 8-bit BASICs would have provided enough performance to do anything like real-time vector graphics. The graphics commands were included so people could do graphics in the supplied high-level language without the need to wrap their brains around machine code to draw things at least at a bearable speed. Nothing more. What you can expect then is something like VICtoria did for the map display, where a selection of empires is drawn from predefined shapes.

...

Further discussion about "what ifs?" in design decisions that had be made in those times and then led to the language implementations we got then should probably go into a new thread in either the General or Programming section.

[orac81]

Ok, so heres an "improved algorithm" version of CONNEX, in C:
(I will add a v20 version later, see below)

Download: https://github.com/orac81/miniapples/ra ... latest.zip

https://github.com/orac81/miniapples/bl ... sdl-connex

sconnex-screen-c64.png (2.81 KiB) Viewed 715 times

(c64 console vbcc version)

(SDL version)

SCONNEX is a version of the famous 4-in-a-line game, written to work on almost any computer. It can compile to work as an SDL app (screen shot above) or as a C99 terminal program. The compiled executable is only 7k for the 6502.

Now I have experimented compiling C99 sconnex with vbcc (see the cbm dir in zip), and it outperforms the cc65 by about 40%, so you can play a game on level iq5+ (5 ply) at a few seconds a move on a 1mhz 6502. As the game progresses deeper searches can be used. It needs time regulation/iterative deepening to work best, but thats not yet on this "simple" version of the program.

The program uses the "classic" recursive AlphaBeta search pruning algorithm which looks like this:

Code: Select all

int AlphaBeta(int depth, int alpha, int beta)
{
    if (depth == 0)
        return Evaluate();
    GenerateLegalMoves();
    while (MovesLeft()) {
        MakeNextMove();
        val = -AlphaBeta (depth - 1, -beta, -alpha);
        UnmakeMove();
        if (val >= beta)
            return beta;
        if (val > alpha)
            alpha = val;
    }
    return alpha;
}

(I am sure most coders have seen this before, but I have seen programs just using brute force minmax, so its worth mentioning.)

I think an asm version should speed the code up by a factor of 5 or so, and there is plenty of room for improvement, the search is quite simple. Still this version plays quite well, and could be built for almost any machine, the console version only needs putchar and gets supplied (no printf!).

To build the code, change these defines in sconnex.c

#define IS_SDL 0
#define IS_C99 1

then simply compile:

cc sconnex.c -Os

I was trying to make a vbcc version for the vic20, but the is no lib yet in vbcc. Its really very simple, nearly the same as the c64, the basic rom is near identical, just moved from $a000 to $c000. Also basic start for 8k+ machines would be $1201 rather than $0801. an option for starting at $2001 would be useful so that $1000-1fff can be used for hires gfx.

To get unix time() in vbcc, a simple hack is to make long var peeking the jiffy clock, then divide by 60. (I didnt leave that in this version.)

A generic CBM target might be useful, just using std kernal calls, and a user supplied code start, zp area, jiffy clock ptr etc.

Anyway, thoughts welcome..

Edit:
The author of vbcc has added a provisional vic20 library to vbcc. here is a version of sconnex built for the vic20(8k+) with vbcc. It is about twice as fast as cc65, about 200 nodes per sec.

http://forum.6502.org/download/file.php?id=21743u