The Lemon Fool

Not a puzzle as such, more of an idea that might spur some discussion.

I was listening to a podcast about a chess computer that machine learned how to play by being given the rules and then set to play millions of games of chess against itself. The end result is a program that plays chess very very well.

I also recall that chess, has been 'solved' on a 5x5 board. So every possible move has been worked through and if one were to play against a machine that had the database, you can never win.

So I was musing about noughts and crosses and how I would have tried to solve that using an old machine with very limited memory - A BBC micro would be ideal.

I keep musing and might even dust off my very rusty programming skills to see where I get to.

With a 3x3 grid, we have only 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 for 362,880 possible game variations.

Except we don't.

Any play that ends in win reduces that number.

In idle musing, I was working on reducting the number of possible variants of play and the first multiplier '9' is not '9' it is three - There are only three possible opening moves, center of grid, corner or the middle bit. The board needs to be rotated or mirrored.

The drops the total gameplay variations to 120,960 and that is as far as I've got.

It won't be difficult to work out an algorithm to never ever lose at tic-tac-toe but I feel that it should have been possible with a bit of clever programming to solve it with a database of every move possible and fit it into 32k.

Over to you.

B.

PrincessB wrote:It won't be difficult to work out an algorithm to never ever lose at tic-tac-toe but I feel that it should have been possible with a bit of clever programming to solve it with a database of every move possible and fit it into 32k.

When I was in the sixth form (some decades ago!) the school got access to a time sharing system, using an ASR 33 dialled in with an acoustic coupler to a PDP-7. 'twas revolutionary at the time!

Well, every year the school would have an open Saturday, which was basically the kids showing stuff they'd done to the parents, and a mate and I programmed up noughts and crosses in TELCOMP and charged parents I don't remember how much but only a little to play 3 games against the computer, with some I don't remember how much but lots more than the stake prize if they won any of the 3 games.

If they managed 3 draws we'd give them another game for free ... of course, nobody ever beat it.

We didn't have a database of moves, just an algorithm, and IIRC the program was pretty short, just a few dozen lines, if that. (Programs couldn't be very long 'cos we weren't allowed permanent file storage, and had to punch them off to paper tape instead!). We also programmed up Monopoly, just for our own amusement ... I now wish I'd kept a printout of those ...

PrincessB wrote:Not a puzzle as such, more of an idea that might spur some discussion.

I was listening to a podcast about a chess computer that machine learned how to play by being given the rules and then set to play millions of games of chess against itself. The end result is a program that plays chess very very well.

I also recall that chess, has been 'solved' on a 5x5 board. So every possible move has been worked through and if one were to play against a machine that had the database, you can never win.

So I was musing about noughts and crosses and how I would have tried to solve that using an old machine with very limited memory - A BBC micro would be ideal.

I keep musing and might even dust off my very rusty programming skills to see where I get to.

With a 3x3 grid, we have only 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 for 362,880 possible game variations.

Except we don't.

Any play that ends in win reduces that number.

In idle musing, I was working on reducting the number of possible variants of play and the first multiplier '9' is not '9' it is three - There are only three possible opening moves, center of grid, corner or the middle bit. The board needs to be rotated or mirrored.

The drops the total gameplay variations to 120,960 and that is as far as I've got.

It won't be difficult to work out an algorithm to never ever lose at tic-tac-toe but I feel that it should have been possible with a bit of clever programming to solve it with a database of every move possible and fit it into 32k.

Over to you.

B.

The game is so trivial that I think it could be programmed in far less than 1k. Would have been doable on the 4-bit micros I used to program in Assy. May be a good challenge for readers of this board to produce the most compact piece of executable code to do the job? Of course how the input/output is done is a big factor but maybe we can allow for free a call which returns then next move and another call which outputs the computer's move.

GS

ISTR the player who gets the first move is guaranteed to win provided they make the right moves.

Or have I made that up?

PrincessB wrote:Not a puzzle as such, more of an idea that might spur some discussion.

I was listening to a podcast about a chess computer that machine learned how to play by being given the rules and then set to play millions of games of chess against itself. The end result is a program that plays chess very very well.

I also recall that chess, has been 'solved' on a 5x5 board. So every possible move has been worked through and if one were to play against a machine that had the database, you can never win.

So I was musing about noughts and crosses and how I would have tried to solve that using an old machine with very limited memory - A BBC micro would be ideal.

I keep musing and might even dust off my very rusty programming skills to see where I get to.

With a 3x3 grid, we have only 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 for 362,880 possible game variations.

Except we don't.

Any play that ends in win reduces that number.

In idle musing, I was working on reducting the number of possible variants of play and the first multiplier '9' is not '9' it is three - There are only three possible opening moves, center of grid, corner or the middle bit. The board needs to be rotated or mirrored.

The drops the total gameplay variations to 120,960 and that is as far as I've got.

It won't be difficult to work out an algorithm to never ever lose at tic-tac-toe but I feel that it should have been possible with a bit of clever programming to solve it with a database of every move possible and fit it into 32k.

Over to you.

B.

An overestimate of the number of positions you would need to store is:

Empty board (starting position) = 1 position.

Positions after first X played = 9 positions (9 choices for where to play it)

Positions after first X and first O played = 9*8 = 72 (9 choices for where to play the X, then 8 choices for where to play the O)

Positions after first two Xs and first O played = 9*8*7/2 = 252 (9 choices for where to play the first X, then 8 choices for where to play the O, then 7 choices for where to play the second X, but for each of those sets of choices, you could reverse the order of playing the two Xs and end up with the same position)

Positions after first two Xs and first two Os played = 9*8*7*6/(2*2) = 756 (similarly, but now we can independently swap the two Xs and swap the two Os)

Positions after first three Xs and first two Os played = 9*8*7*6*5/(6*2) = 1260 (similarly, but now there are six possible orders of the three Xs that all result in the same position)

Positions after first three Xs and first three Os played = 9*8*7*6*5*4/(6*6) = 1680 (similarly - I'll skip the detailed explanations from here on)

Positions after first four Xs and first three Os played = 9*8*7*6*5*4*3/(24*6) = 1260

Positions after first four Xs and first four Os played = 9*8*7*6*5*4*3*2/(24*24) = 630

Positions after first five Xs and first four Os played (final positions) = 9*8*7*6*5*4*3*2*1/(120*24) = 126

Total positions = 1+9+72+252+756+1260+1680+1260+630+126 = 6046

There are at most 9 possibilities for the move to be made in any position, so it would be easy to store the move-to-make information for two positions in a single byte. So the tables for a table-driven program could easily be stored in about 3k of memory. But most positions have eight variants that differ only by symmetries of the board (though some have fewer, the extreme case being a single X in the centre of the board which only has one variant), so if you factor those out, you should be able to reduce the table size by a factor of getting on for 8, to maybe 400-500 bytes. And there are further reductions due to positions that cannot occur, either because they must already have been won (e.g. positions with lines of three for both players) or because of how the program will have played earlier (e.g. if the program plays its first X in the centre of the board in the starting position, then it can never be faced with a later position with the same numbers of Xs and Os but without an X in the centre of the board). I'd guess that it would probably be possible to reduce the memory required to maybe 200-300 bytes.

There is however the issue of the complexity of calculating which table entry to look up - even just calculating that for the 6046 positions described above is not entirely straightforward, and the more you factor out symmetries, impossible positions, etc, the more complicated it becomes. At the opposite extreme, we might want to make that calculation very simple - for instance, by representing an empty square by the ternary digit 0, an X by the ternary digit 1, and an O by the ternary digit 2, we can reduce any position to a number in the range from 0 to 3^9-1 = 19682. Again storing two table entries per byte, that would allow us to store some very easily-looked-up tables in 9842 bytes.

So a table-driven noughts-and-crosses program could be fitted into under 10k of tables with pretty simple table lookup, or less (down to a few hundred bytes) with more complex table lookup. That's easily within the capabilities of a BBC Model B, and quite possibly within those of a BBC Model A (though I'm not entirely certain of the latter, as I don't remember how much of the BBC Model A's 16k of RAM was reserved by its OS).

Note I'm not saying that the best way to write a noughts-and-crosses program would use a table-driven approach like that - just that it could be done that way within the memory of a BBC Micro. What the best method is is a rather ill-defined question, anyway - best with respect to what? E.g. the pretty simple method using 10k of tables might well be the best from the point of view of writing and debugging a working program as quickly as possible, but it's pretty certain not to be the best from the point of view of using as little memory as possible.

Gengulphus

Mike4 wrote:ISTR the player who gets the first move is guaranteed to win provided they make the right moves.

Or have I made that up?

No, if both players play perfectly then it is a draw.

Mike4 wrote:ISTR the player who gets the first move is guaranteed to win provided they make the right moves.

Or have I made that up?

If you start in a corner and your opponent responds anywhere other than in the middle, you can win. Any other first moves will, with perfect play, result in a draw.

I recall many years ago that someone had invented a variation where players tossed a coin each turn to determine whether they had to write a nought or a cross. The other rules were the same so you could unavoidably lose on your own move.

For added interest, try quantum noughts and crosses, or a 3D version on a 4 x 4 x 4 grid.

Julian F. G. W.

It's been done ...

Sometime back in the '70s - when my generation of the family were schoolboys - my mother borrowed a computer. Possibly while its owner was on hols or somesuch. About 1Kb RAM to play with; 8-bit arithmetic.

My brother and I of course took every opportunity to play with it. One of his projects was to make it learn noughts-and-crosses. It would start by playing randomly, and learn which moves led to what outcomes.