Slim's Geek Gazette

[Slim]

I hadn't noticed that detail about the pipe! The watch looks off as well. I'll get it to have another go.

[Slim]

I spent ages on the code today, at times wanting to tear my hair out (but it's not long enough to get hold of).

I've settled on this idea for the "AI mode" for the computer:

Start off in "hunt" mode.

If you hit a ship, set to "find next" mode - go through the orthogonally adjacent squares until you hit a ship square. Then set the AI mode to "linefind".

In "linefind" mode the computer will walk along the line of hit squares until it finds a square that has not been tried, that's adjacent to a hit square. Then it will shoot at it (might be empty water, might be another part of the ship). It continues in this mode until the ship is sunk, then it returns to "hunt" mode.

Coded it up (was a bit painful to do). It works.

There is another possible improvement I can make. In "hunt" mode it can make stupid choices. It can shoot at a square that cannot possibly be part of a surviving ship. I'll look into fixing that.

[Slim]

I have, mainly, fixed that. It occurred to me that a simple expedient to prevent the computer from aiming at squares adjacent to ships that it's sunk is simply to silently mark them as already attempted. So I did that.

The computer player could still aim at squares in a set that doesn't have space for a remaining ship. I could potentially fix that. But I don't think it's worth it.

Still to do: allow the player to "redo" the player grid with a right-click and organise the win / lose counting / logic.

[Slim]

I decided, for my next coding project, to create a Bash, terminal version of the old game Battleships, originally played using pencil and paper, occasionally sold as a plastic or wooden board game, but realised as a computer game in the late '70s.

It's basically grid-based so similar to Star Trek in some respects. But it involves some complex problem-solving, so it should keep me occupied for a few weeks.

Just finished this. Optimised the code, added some frame buffering, added a high score function and a shot counter, added the win / lose logic, added a "rearrange the fleet" function (right-click).

That was very absorbing but took less than two weeks. Need to think of something else now!

Also I need to document this one and post it up on GitHub.

Highslide Image Viewer

[Slim]

Uploaded to GitHub: https://github.com/StarShovel/bash-ships

I did think of including a "wide mode" version that would use a 10x12 grid, or even 10x14. But some of the code assumes single digit x&y co-ordinates and I'd have to have a proper rewrite. I don't think it's worth it.

[Slim]

Shared the URL on Reddit and got a reply asking me if I'd consider a human vs human version for players logged into the same machine!

Would need to devise a protocol for the two processes to synchronise, maybe using a named pipe. Each running instance would be the authority for its own fleet and return "hit", "miss", or "sunk", the latter including the co-ordinates for the whole ship.

[Slim]

For my next project I'm going to do something that's superficially simple: noughts & crosses.

The board will look like this (a mockup, I haven't started coding yet)

Highslide Image Viewer

This uses a method called Minimax which I vaguely remember learning during my AI course. The basic idea is that the program recursively plays out every possible move, assuming both sides will make the best move each time.

For a 3x3 board this is not expensive, the program can explore all the possibilities very quickly and it will actually be impossible to beat; the best you can hope for is a draw.

For a 4x4 board, if you can imagine such a thing, the program would take years to explore the possible outcomes for the first few moves.

If the same strategy was adopted for chess, the "game tree" as it's known would take trillions of trillions of trillions times the age of the universe to bottom out.

[Slim]

I've got the algorithm done now. I had to learn the Minimax algorithm during the AI module of my degree course in 1988 or 1989, but apart from the basic idea I'd forgotten it. So I've more or less relearned it today.

As I mentioned in my last post, the computer can't actually lose if I implement it properly. But ..

Code Select Expand

your move 5
computer move: 0
your move 3
computer move: 1
your move 4
YOU WIN

Each square is represented by a number, 0-8. The mouse control and terminal graphics are not implemented yet. More importantly, clearly there was a bug.

Fortunately I tracked it down - there was a variable in a function that should have been local, that was global. The computer is unbeatable now, as it should be.

Interestingly: the computer takes about 10 seconds to make the first move. It has to examine thousands (40,320 worst case) of possible future versions of the board. But subsequent responses are much quicker - with only 6 empty places left, the very worst case is 720 boards.

So: I had an idea. There are only 9 possible human first moves of course, so instead of calculating the first response, just use a lookup table. I'll use the script in its current form to see what it does for each. Then I'll just put them in a table, hard-coded into the script.

There's no random element, the computer's move will be the same every time for the same first human move.

[Slim]

I've got the mouse control and the graphics sorted now.

Highslide Image Viewer

What I also did was this: if the computer AI finds more than one move leading to a win, it picks one at random. Just to make it a bit less predictable.

This gives rise to the following behaviour. If it knows it can't be beaten, sometimes it will decline to play the winning move. In the above example, instead of placing its next ⭕ to complete the middle row (and win), it placed it in the middle of the bottom row.

It still can't lose. It doesn't cost anything from the computer's point of view; it's not "wrong". But it seems odd. Almost like the computer's trolling you.

[Slim]

It turns out that the minimax method, in its raw form, is in a way very inefficient - in that it will analyse the same board multiple times, even in the same move - because there are sometimes several different ways to arrive at it.

When it is evaluating the "game tree" for a particular sequence of moves, it will recursively look possibly thousands of moves into the future to score the board. Then when it backs up and evaluates the branch for an alternative sequence, it forgets the scores for boards it's seen before. It will blindly re-calculate the entire future tree again.

There's an easy fix for this though, which I implemented yesterday. I set up an associative array as a cache. So when the board scoring routine assesses a score for a board embodying a particular potential move, it saves the score for that board. A board is represented as a simple string of digits with 0 for an empty space, 1 for the human's mark (an X) and 9 for the computer's mark (a 0). Like 191999011, for example.

Because the game is actually pretty boring - the best the human can do is draw - I also set up an optional "compromised" mode, in which the computer AI is only allowed to descend two levels of recursion to analyse a board.  In practice this allows the human to win occasionally.

It may be that the caching defeats the first computer move delay, and I don't need to set up a lookup for its first move. Will test that.

[Slim]

In fact - it does, so I've stripped out the code that works out if it's the computers first go and selects a first move, and that's made the code a lot more compact.

This is something I find fascinating - I've done some diagnostics with updates to a log file, and the cache never gets updated after the computer's first move. That's because the first time the Minimax algorithm runs, it explores every single legal combination of moves that can happen from that moment until the end of the game. After that, the cache is complete.

Well, it's finished now. Will document it and publish it on Github.

[Slim]

Highslide Image Viewer

[The Picnic Wasp]

Love the price which must seem so alien, even to someone in their fifties. That makes me shudder.

[Slim]

I don't miss all that pounds and shillings nonsense, but I certainly do remember it.

Blows my mind that a "ten bob note" was what we now call 50p.

Highslide Image Viewer

[The Picnic Wasp]

I don't miss all that pounds and shillings nonsense, but I certainly do remember it.

Blows my mind that a "ten bob note" was what we now call 50p.

Highslide Image Viewer

These were such a wonderful sight when opening birthday cards. Around 1974 our family visited the Isle of Man. I was really surprised to find they used 50 pence notes.