Can someone make Pente for the 2600?

[Atari Rescue Group]

Pente is a game I'd like to see made for the 2600.

 

Grid pattern, player pieces get placed at intersecting lines. First marker played starts in the middle of the board.

Two ways to win:

1) Line up five in a row to win (horizontal or vertical or diagonal with no empty points between)

2) Surround/capture five (or more) pairs of opponents markers with yours.

 

Joysticks would work for a (one or) two player version, or could 2-4 paddles be used to allow more players?

 

Possible? Impossible?

[Zach]

What are the dimensions of a Pente grid?

[Atari Rescue Group]

Not that any appreciable time should be taken away from Tank AI development (because that's VERY important!), but......

 

I've got the version with the rolled playfield that goes in a tube. It has 19 lines on each side (including the side borders) where markers can be played (17 lines and an outside border) Not sure if the folding board version has a larger playfield.

[Zach]

If it's 19x19 then that's the same size as a Go board. I've been thinking about how to port Go to the 2600. I think the best way would be to use a kernal similar to Paul Slocum's RPG engine. (BTW, great job Paul!) There would be a width of 10 sprites using flickering. It would look something like this:

 

 

If I understand your description, Pente would work on this same board. With 2 bits necessary to represent each piece at 361 positions, you would need 722 bits of RAM, or 91 bytes.

 

It seems that Go and Pente could be put on the same cartridge, since the boards are the same. I don't know so much about Pente, but AI for Go would be very difficult. The best Go systems in the world (at time of writing) are ranked at "weak amateur", and I assure you they don't run on a 2600. At best, the AI could challenge a beginner with less than an hour of experience. Nevertheless, a 2 player version would still be fun.

 

I'd love to do this, but you're right about my other project being more important. If someone wants to take on this project, be my guest.

[Pitfall Harry]

It seems that Go and Pente could be put on the same cartridge, since the boards are the same. I don't know so much about Pente, but AI for Go would be very difficult.  The best Go systems in the world (at time of writing) are ranked at "weak amateur", and I assure you they don't run on a 2600.  At best, the AI could challenge a beginner with less than an hour of experience.  Nevertheless, a 2 player version would still be fun.

 

Actually, I wrote a Go program in 1989 which was able to beat friends of mine who were far, far better than your typical "beginner with less than an hour of experience." I wrote the program in Turbo Pascal and it ran on a 10 MHz 80286. The game was not overly complex, running a fairly simple but ingenious algorithm based on an article I read in an old issue of BYTE magazine. The article is called "Programming the Game of Go," and it appears in the April 1981 issue. According to Jonathan K Millen, the author of the article,

 

"A Go opponent, called Wally, was programmed on a KIM-1 within its approximately 1K bytes of memory. Wally's algorithm is based on essentially two capabilities: finding the liberties of a connected group, and matching a few common patterns. Moves take less than a second.

 

A 15 by 15 board was used because it was convenient for addressing reasons to represent it internally within a single 256-byte page. Although there would be room for a 16 by 16 board [within A SINGLE 256-BYTE PAGE], A Go board ought to have a center point. Rows and columns were numbered from 1 to F (in hexadecimal) so that the coordinates of a move could be entered on the KIM keyboard."

 

The game I wrote after reading the article played surprisingly well, even though I implemented the algorithm using a full 19 x 19 board. It played better still when I threw in a few additional pattern-matching algorithms of my own design, each of which did not consume an appreciable amount of program code or data space.

 

If a decent implementation of Go (including display!) can run on a KIM-1 in 1K of memory and return moves in less than a second, I believe an experienced 2600 programmer can match -- and likely surpass -- the achievement given the luxury of 4K of ROM.

 

 

Ben

[Zach]

Hi Ben,

 

Very interesting. I'm going look for that article on the web.

 

I believe an experienced 2600 programmer can match -- and likely surpass -- the achievement given the luxury of 4K of ROM.  

 

You mean like the man who made "Connect the Dots"?

[Thomas Jentzsch]

AFAIK Wally is still a quite weak algorithm, often used as a lower benchmark for testing other Go programs (based on neural networks).

 

Probably only good enough to beat beginners.

[Pitfall Harry]

You may have difficulty locating the article on the web. I couldn't find it when I searched for it. If you can't find it at your local library, I'll scan the article for you from my copy of the magazine.

 

Apparently, I'm not te only one who read the article and implemented the program. A guy by the name of W.H. Hewman wrote a MSDOS implementation in C and offered it up into the public domain. I've attached a .ZIP file which includes his program, C source code and a few comments in a readme file. If you read the header comments in his C source code, he cites the 1981 BYTE Magazine artical as the model for his program. This is all very well and good, since I suspect the source code for my implementation may never be dug out of the mountain of notes in my garage.

 

There are other public domain Go programs you may want to look at. There's a nice list of them here...

 

http://www.britgo.org/gopcres/gopcres1.html#s-play

 

Yes, Wally isn't really all that smart. But most people don't have a clue how to play it well anyway. I've played a lot of Go, and I must say that Wally is capable of making some hauntingly clever moves. Of course, once you understand the method to its madness the game is a snap to beat. And its play degenerates into bumbling when it gets into the end game.

 

Nevertheless, I'm sure Wally (even with improvements via added pattern-matching elements) can be fit into a 4K Atari ROM. And no, little ol' dot connector me is a long, long way from being up to the challenge.

 

Ben

wally.zip

[Zach]

I commend your enthusiam for Go, Ben. I found Millen's article in a library, and briefly looked over it. The main problem I see is that "1K bytes of memory" evidently refers to RAM instead of ROM. His references to recursive algorithms and "a 100 byte stack" were the giveaway.

 

Back to the original topic of this thread, I briefly spoke to one of my professors about Pente. His expert opinion is that AI for that game would be much easier than Go. I'm going to ask him for more details soon.

[Pitfall Harry]

I commend your enthusiam for Go, Ben. I found Millen's article in a library, and briefly looked over it.  The main problem I see is that "1K bytes of memory" evidently refers to RAM instead of ROM.  His references to recursive algorithms and "a 100 byte stack" were the giveaway.

 

Yes, you are quite right. The program Millen implemented did not conserve RAM quite the way an Atari 2600 programmer would because he was working with a computer and had a full 1K of RAM as a combined code and data space. Millen's board was represented as a 256-byte array for "reasons of convenient addressing." Convenience is great when you can afford it. An Atari 2600 programmer would have to forsake "convenience" to conserve more RAM than that because he's only got 128 bytes to work with, only half of what Millen uses to represent the game board! Of course, 2600 programmers are used to overcoming obstacles such as these.

 

A 16 x 16 go board can be "somewhat conveniently" represented in as little as 64 bytes. Represent each of the 256 intersections of the board as a pair of bits, and the following truth table shows how each intersection is occupied

 

00 = an empty board space

01 = point occupied by a black stone

10 = point occupied by a white stone

11 = (not used)

 

Thus the entire board can be saved in 512 bits, or 64 bytes. You still have 64 bytes of RAM left over for the 30-byte stack, rudimentary pattern matching lookup tables, and for loop control variables. Since the 7 pattern match lookup tables span so very few board points, I could easily see all 7 implemented in as little as 28 bytes. That leaves 6 bytes for loop control variables... easily within the realm possibility, if you use and reuse them carefully.

 

Back to the original topic of this thread, I briefly spoke to one of my professors about Pente.  His expert opinion is that AI for that game would be much easier than Go.  I'm going to ask him for more details soon.

 

He's probably right. I'm sure you could write a stronger Pente playing program for the 2600 than you could for Go. Still, I believe a suitably motivated programmer really could implement Wally on the 2600.

 

Ben

[Robert M]

Doesn't Go require a board with an odd number of spaces on each side? 21x21, 19x19, 17x17, 15x15 etc.

 

Pente is a good idea for a 2600 hombrew. IMO

 

Go is very ambitious.

 

Cheers!

[Zach]

We seem to agree on the major points that 1 player Go would be challenging to program, and that it could only rival beginners.

 

On the other hand, I disagree with using a 16x16 board. Go is traditionally 19x19, and on a smaller board it's a different game. I'd call it something like mini-go.

 

You're right about using 2 bits for each intersection. On a 19x19 board, you'd need 722 bits or 90 bytes and 2 bits. Unfortunately, that leaves even less RAM free for everything else you'd need to do.

[Pitfall Harry]

Well, the good news is: There's absolutely no reason to store the pattern match tables in RAM since they never change. So the 28 bytes of RAM I said they would consume can now be applied to the 27 additional bytes you'd need to save a 19 x 19 board, leaving you with one more byte of RAM for variables than I previously thought!

 

And as long as the pattern tables are in ROM, not RAM, you'd likely have space to add a dozen pattern tables of your own design to make the game play stronger, should you be so inclined.

 

 

Ben

[Thomas Jentzsch]

Don't forget that you need some RAM for the game itself (kernel, scoring etc.)

[Pitfall Harry]

Don't forget that you need some RAM for the game itself (kernel, scoring etc.)

 

Wally doesn't do much accounting work. All he does is count stones, which takes only one or two bytes.

 

Also, I should point out that 91 bytes is by no means the most compact way to save a 19 x 19 board. Remember: 25% of the bits in the 91 byte array are unused, which suggests the bit array could consume 25% less space if you're willing to endure the coding overhead of compacting/decoding it. The need to reclaim 22 more bytes of RAM may make doing it a necessity, but it can be done.

 

If Atari could write a workable chess program in 4K, I have no doubt at all that Wally could be squeezed into the same space. It all comes down to how badly you want it.

 

 

Ben

[slapdash]

One minor aside... IIRC, Pente doesn't use as large a board as Go or Go-Moku. I could be wrong though, as it has been years (a decade & a half probably, maybe two) since I've played Pente.

[Zach]

I'm glad Slapdash brought up Go-Moku. It is my understanding that Go-Moku and Pente are basically the same, with maybe some minor differences. Can anyone elaborate on this?

 

It seems that Pente is a Parker Brothers game. Does anyone know if they own the name as a trademark? If that's the case, it might be better to make Go-Moku. (Might be fun to build the carts out of unloved Frogger carts, though.)

[Zach]

Pente doesn't use as large a board as Go or Go-Moku. I could be wrong though

 

OK. I just looked at some Pente boards on eBay. They come in different kinds of packaging, but they are all 19 lines by 19 lines. Unlike Go, I believe you don't place pieces on the outside edge. So Pente is essentially on a 17x17 board.

[slapdash]

Interesting... I could have swornit was smaller, but oh well.

 

And yeah, as far as I know Parker Bros just took Go-Moku and called it Pente. I'm not sure about differences, but I MIGHT be able to find out. Email me a reminder if you'd like me to look into it, but don't expect the info to come soon. :-)

[Atari Rescue Group]

It's good to see some potential interest in making the game and working out programming ideas.

 

I'll be looking for cheap Froggers to supply to whomever takes on the project!

 

I found some instructions...

 

Object of the game: There are two ways to win in Pente:

 

1. Win by getting five (or more) stones in a row, either horizontally, vertically, or diagonally, with no empty points between them, or

 

2. Win by capturing five (or more) pairs of your opponent's stones.

 

How to play:

Start play with the board completely clear of stones. The first player (chosen by chance) begins the game by playing one stone on the center point. Thereafter the players take turns playing their stones, one at a time, at any empty intersection. The stones are played on the intersections of the lines (including the edge of the board, rather than on the squares.

A move is completed when the stone is released. Once played, a stone cannot be moved again, except when removed by a capture.

The players take turns adding new stones to the board, building up their positions, until one player wins.

 

FYI -- stone colors i've seen are red, yellow, blue, green (they are made of glass for the board game)

 

The instructions say that Pente combines the basic elements of Go (strategy), Niniku-Rinju (flashy tactics), and Go-Moku (for it's simplicity).

 

Rules are by a guy named Gary Gabrel (1982)

 

Looks like there was a USPA (United States Pente Association) but I couldn't find them on the www. However, the WPPF (World Pente Players Federation) is apparently alive and moving their stones about http://www.playpente.com/minutes.php. They just had a meeting in May, 2003.

 

Rules and strategy are on the web site.