Gonnect on the Voyage 200

From Carls wiki

Jump to: navigation, search

Gonnect is a board game hybrid of Go and Hex. I started implementing it a few years ago on my Voyage 200, and now I'm returning to the program to apply some things I've learned about data structures since I wrote it.

I had forgotten how idiomatic TI Basic can get. Or rather, my TI Basic.

Contents

Features of the program

Bit-biltting

Graphics is handled through the built-in commands RclPic, AndPic and XorPic. They are used approximately as follows:

  • RclPic is used to put graphics on the screen. It could as well have been named OrPic, because it does not clear pixels, only sets them.
  • AndPic is employed, along with inverted bitmasks, to clear individual elements from the screen. In Gonnect, it is used just before updating a square on the board.
  • XorPic has the advantage of being its own inverse operation. That is, if I do the same XorPic call twice, I'm left with the screen I started with. I use it for placing the piece cursor, because clearing it is as easy as placing it: just use XorPic.

Short-circuiting

I'm a short-circuiting junkie, from programming modern programming languages too much. In these languages, the boolean operators and (&&) and or (||) short-circuit, which means that they don't evaluate more operands than there's a need for. This means that

  1. the program runs faster, because less comparisons are often needed, and
  2. it's possible to write things more succinctly, because later operands are only evaluated in certain circumstances

An example of (1) would be quickComputation() || slowComputation(). In a short-circuiting language, we don't have to evaluate slowComputation() if quickComputation() returns true.

An example of (2) would be array.length >= 1 && array[0] != null && "capaybara".equals( array[0].toString() ), which only proceeds investigating the first element if the list contains at least one element, and only tries to compare "capaybara" with the stringification of the element if the element is non-null.

TI Basic doesn't have short-circuiting. It has boolean operators, but they evaluate both operands, and only then perform the operation on them. Which means that time-savings of type (1) aren't time-savings, and using the idiom in (2) makes the program end with an error.

Fortunately, TI Basic has when(condition,value-if-true,value-if-false), which does short-circuit. I'm sure the people who put when() in the language never intended it to be used in the way I'm using it.

Because I'm using it all the time. 

If when(x>1,when(v[x-1,y],false,b[x-1,y]=c),false) Then

This line

  • returns false (that is, doesn't execute the Then leg) immedeately if x happens to be less than or equal to 1,
  • otherwise, returns false if v[x-1,y] is true (v is an already-visited matrix of booleans in this example),
  • otherwise, returns whether b[x-1,y] equals c. (Yep, = is comparison in TI Basic.)

Neat, huh? I can have my short-circuiting cake, and eat it, too! Or something. It might not be as readable as simple ands and ors, but it's more efficient, and often shorter than using several nested or chained If statements.

String references

Sometimes you want to do something with one variable under some conditions, and the same thing with another variable under other conditions. Problem is, variable names aren't really first-class values in TI Basic, so you end up duplicating code in the different legs of If statements.

...until you find the # operator. It allows you to de-reference a string value to a variable: #"var" dereferences to var. So if I want to put a black piece on the board if it's the first player who is on turn (p=1), and a white piece otherwise, I just go 

RclPic #(when(p=1,"pcbl","pcwh")),yy,xx

Notice here how # and when() play nicely together. This is not uncommon, and becomes really handy in more complex cases. The below code restores the board underneath a newly removed piece. 

RclPic #(when(y=1,when(x=1,"pcnw",when(x=n,"pcne","pcno")),when(y=n,when(x=1,\
"pcsw",when(x=n,"pcse","pcso")),when(x=1,"pcwe",when(x=n,"pcea","pcem"))))),yy,xx
If when(n=5,x=3 and y=3,when(n=13,x?1 and x?13 and y?1 and y?13 and mod(x,3)=1\
 and mod(y,3)=1,false),"die: unknown board size"):RclPic pcen,yy,xx

(Lines ending with \ are continued on the next physical line in this example for the convenience of the reader. In the program, they are not.)

(All the funny variable names? Well, pcnw, pcne, pcsw and pcse are corners, pcno, pcso, pcea and pcwe are borders, pcem is a place anywhere else, except for a few specially locations which have a pcen on them when they're empty. I don't remember what "pcen" stands for anymore.)

Complex numbers

TI Basic has no support for tuples, and I often find myself wanting to store coordinates together in arrays and matrices. There is, however, native support for complex numbers, so I use that.

Changes I'm about to introduce

The bottleneck the program runs into is speed. Right now, checking whether a move removes a group of pieces is a time-consuming task, because the program needs to run across the board doing all kinds of calculations. Checking whether a move wins the game is right out.

Equivalence classes

I can see traces in the code of half-heartedly wanting to implement some equivalence class calculations to the groups of pieces. This would possibly speed up the piece removal greatly. Apparently I didn't succeed. Since then, I have read more about it in TAOCP, and I'm ready to make another shot.

Calculations behind the scenes

Another thing I've always wanted to try, is to start making a move before the user has pushed Enter. This can be done, provided that the key loop routinely calls a little coroutine, which does small incremental calculations on the move — and also provided that these incremental calculations really can be broken down in small enough fragments so that the key loop doesn't lag.

I find the idea fascinating because of the sheer madness of performing preemptive move calculations using pseudo-multitasking in TI Basic on a Voyage 200. I really should be using C or assembler insted, at the very least.

Retrieved from "http://www.masak.org/carl/w/index.php/Gonnect_on_the_Voyage_200"