It is currently Wed Oct 18, 2017 10:40 pm

All times are UTC - 7 hours





Post new topic Reply to topic  [ 19 posts ]  Go to page 1, 2  Next
Author Message
PostPosted: Thu Apr 14, 2016 12:57 pm 
Offline

Joined: Thu Jul 23, 2015 7:54 pm
Posts: 145
Location: USA
I've been looking into Computer Go lately, and thought it would be a fun challenge to try and implement it on the NES. Graphics-wise, this works perfectly because 3 colors - tan, black, and white - can represent the wood of the board, the lines of the board, and the black and white stones. And since the standard board size is a 19x19 grid, it could easily fit on the screen.
Attachment:
nesgo_mockup.png
nesgo_mockup.png [ 34.16 KiB | Viewed 2010 times ]

Unfortunately, the NES just doesn't seem suitable for machine learning or anything else that was recently pioneered by AlphaGo, but a 2-player version seems a lot more in-reach.

I've been working on a prototype in C. What I've come up with so far is a way of determining if a stone or a chain of stones has been captured.
Code:
char check_surrounded(int x, int y)
{
    //if out of bounds, hit a corner or an edge; exit
    if (x < 0 || x >= BOARD_WIDTH || y < 0 || y >= BOARD_HEIGHT)
        return 1;

    //if current spot is empty, the group is not surrounded
    if (board[y][x] == EMPTY)
        return 0;
    //if current spot has an enemy stone, don't continue to recurse here. Break.
    else if (board[y][x] == enemy)
        return 1;

    //otherwise if the current spot has a friendly stone, more checks need to be done. Recursively check the 4 surrounding spots, but only if they haven't already been checked (To avoid redundant checks and potentially infinite recursion)
    else
    {
        if (board_checked[y][x] == 1)
            return 1;
        else
        {
            board_checked[y][x] = 1;
            return (check_surrounded(x, y + 1) & check_surrounded(x, y - 1) & check_surrounded(x + 1, y) & check_surrounded(x - 1, y));
        }
    }
}

If 1 is returned, a stone or chain has been captured.

So obviously, this uses recursion which poses problems since the 6502's stack is only one page, giving 125 subroutines assuming the stack isn't used for anything else except NMIs. I'm not the best at complexity analysis, but from traces I've done on paper, the worst-case space complexity seems to be O(n2), where every single stone would need to be checked. On a standard 19x19 board, that would be 361 calls, way more than the 6502's stack can handle. But I don't think that many stones would ever be captured at one time.

What do you guys think? If there's a better way of doing this, maybe even one that's iterative, I'd love to see it.


Top
 Profile  
 
PostPosted: Thu Apr 14, 2016 1:48 pm 
Offline
User avatar

Joined: Thu Mar 31, 2016 11:15 am
Posts: 197
If you need a larger stack then create your own in RAM and use it hold the need-to-be-evaluated positions. In general you can convert any recursive function in C to a looping function this way.

A slightly better algorithm involves keeping track of contiguous groups of stones. A group is created when a stone is placed on the board having no neighbors of the same color. A group is expanded when a stone of the same color is placed on the board adjacent to it. If the placed stone is adjacent to two or more groups, then the groups are merged to form a single group.

If you keep track of the number of free spaces around a group then you'll get constant-time updates for most moves.

But anyway, this is just speculation from somebody who has never played Go. I'm fairly certain that better algorithms have already been written.


Top
 Profile  
 
PostPosted: Thu Apr 14, 2016 1:55 pm 
Offline
User avatar

Joined: Fri May 08, 2015 7:17 pm
Posts: 1772
Location: DIGDUG
Consider using a smaller board. What's impossible at 19x19 might be easy at 10x10.

_________________
nesdoug.com -- blog/tutorial on programming for the NES


Top
 Profile  
 
PostPosted: Thu Apr 14, 2016 2:38 pm 
Offline

Joined: Sun Apr 13, 2008 11:12 am
Posts: 6279
Location: Seattle
Rather than searching for chains without liberties using a recursive algorithm, why not instead use a flood-filling algorithm to mark chains that have liberties?


Top
 Profile  
 
PostPosted: Thu Apr 14, 2016 2:46 pm 
Offline
User avatar

Joined: Sun Jan 22, 2012 12:03 pm
Posts: 5718
Location: Canada
Feasible? Obviously yes, I think. We've had implementations of Go AI, and other strategy games on computers for a very long time.

The primary difficulties for Go AI are:
1. Too many possibilities to evaluate.
2. No obvious way to score a position in an unfinished game.

That said, you can come up with a lot of heuristics for 2 that can make an AI that would probably be reasonably challenging for a lot of players. It's similar to all the stuff you'd learn when beginning to study Go, i.e. how to identify good shapes and bad shapes, etc. This basically leads to an score estimation system that you can use with a traditional minmax approach. Analysis of shapes tends not to be so computationally heavy, it's trying to evaluate consequences in subsequent moves that overcomes the processing ability of a computer. (Dougeff's suggestion to limit the size of the board probably won't help much in this respect; the growth is simply too fast. It's also difficult to scale a lot of heuristics from 9x9 to 19x19, since so much of the game is about edge-play.)

A good enough player will eventually find flaws they can exploit to win every time. Often the approach is to figure out how to beat your own AI in this way, and then try to devise a heuristic to prevent the use of that flaw. Repeat until you can't improve it anymore. (And you won't ever be able to improve it beyond your own skill level.)

The AlphaGo approach was more or less to estimate the score of a position with a neural network that they trained to imitate other players. The size of any reasonable neural network for this purpose is way out of scope for the NES, though; I don't think there's any way to scale it down enough and get anything remotely useful.

Creating an AI that can perform reasonably at a moderately low level of play is well within the capabilities of the NES, I think. It's notoriously hard to search for, but I'm certain you can find versions of Go on contemporary platforms like the C64 or Atari ST.


Basically what I'm saying is just because intermediate level play is out of the question, doesn't mean a novice AI wouldn't be fun to play with. Most people don't even know how to play at all, so a computer that's only a little bit good at it might be enough to be fun for a lot of people. Plus it might be a fun project for you, and that's really what's important here. If you're interested, go for it!

Also, make sure to have a configurable handicap. Eventually if you give the computer enough extra stones it would (in theory) become a challenge for anyone. ;)


Top
 Profile  
 
PostPosted: Thu Apr 14, 2016 3:39 pm 
Offline

Joined: Sun Sep 19, 2004 11:12 pm
Posts: 19099
Location: NE Indiana, USA (NTSC)
A 4-in-1 multicart with Ataxx (Spot), Reversi (Othello), 9x9 Go, and Connect Four might sell. But then Spot used extra RAM (Spot: NES-SNROM). I haven't traced into it, but it might be related to AI scratchpad memory.


Top
 Profile  
 
PostPosted: Thu Apr 14, 2016 3:58 pm 
Offline
User avatar

Joined: Sun Jan 22, 2012 12:03 pm
Posts: 5718
Location: Canada
I think extra RAM would be critical for an NES Go AI.

I'm almost shocked that Battle Chess didn't have 8K WRAM. Chessmaster did, though.


Top
 Profile  
 
PostPosted: Thu Apr 14, 2016 6:09 pm 
Offline
User avatar

Joined: Sun Dec 12, 2010 10:27 pm
Posts: 282
Location: Hong Kong
There were actually nearly 10 Go games released on the Famicom. This is one of them.

Don't know about their AI (some of these games probably just replayed famous games instead of having AI of their own) but I think they're limited. You may first take a look to see what could be expected and try to do a better job.


Top
 Profile  
 
PostPosted: Thu Apr 14, 2016 6:27 pm 
Offline

Joined: Thu Jul 23, 2015 7:54 pm
Posts: 145
Location: USA
Gilbert wrote:
There were actually nearly 10 Go games released on the Famicom. This is one of them.

Don't know about their AI (some of these games probably just replayed famous games instead of having AI of their own) but I think they're limited. You may first take a look to see what could be expected and try to do a better job.

Interesting. It looks like there is indeed an option for a 19x19 board. Maybe I'll make an attempt to disassemble its 512 kilobytes of ROM and see what it does.


Top
 Profile  
 
PostPosted: Thu Apr 14, 2016 6:54 pm 
Offline
User avatar

Joined: Fri May 08, 2015 7:17 pm
Posts: 1772
Location: DIGDUG
Try this one...
Igo Sinan 32k PRG / 8k CHR
(Or 'igo shinan' on another list)

Smaller = easier to figure out. Maybe?

Edit, the actual cart says 'IGO SHINAN'

_________________
nesdoug.com -- blog/tutorial on programming for the NES


Top
 Profile  
 
PostPosted: Thu Apr 14, 2016 7:20 pm 
Offline

Joined: Sun Sep 19, 2004 11:12 pm
Posts: 19099
Location: NE Indiana, USA (NTSC)
Searching for igo on NesCartDB produces listings for these Go games for Famicom. In release date order:


Top
 Profile  
 
PostPosted: Thu Apr 14, 2016 7:29 pm 
Offline

Joined: Thu Jul 23, 2015 7:54 pm
Posts: 145
Location: USA
It's very confusing because I haven't studied Japanese in almost a year and have forgotten everything, but Igo Shinan 91 seems to be a 0 player game, which leads me to feel like the games are just hard-coded into the PRG.


Top
 Profile  
 
PostPosted: Thu Apr 14, 2016 7:34 pm 
Offline
User avatar

Joined: Fri May 08, 2015 7:17 pm
Posts: 1772
Location: DIGDUG
I tried out Igo Shinan (the first version)...

I can't read a word of Japanese, but I'm not sure it's a functioning Go game, but rather (looks like) a bunch of lessons on how to play Go. The moves appear to be automated, and the CPU doesn't appear to be calculating anything.

_________________
nesdoug.com -- blog/tutorial on programming for the NES


Last edited by dougeff on Thu Apr 14, 2016 8:55 pm, edited 2 times in total.

Top
 Profile  
 
PostPosted: Thu Apr 14, 2016 8:12 pm 
Offline
User avatar

Joined: Sun Jan 22, 2012 12:03 pm
Posts: 5718
Location: Canada
I believe "Igo Shinan" is the name of a famous 19th century book about Go, so it might make sense if the game was basically a digital learning book.

Hayauchi Super Igo appears to play a real 19 x 19 game.

Igo: Kyuu Roban Taikyoku seems to be a 9 x 9 game only.


Top
 Profile  
 
PostPosted: Thu Apr 14, 2016 8:48 pm 
Offline
User avatar

Joined: Sun Jan 22, 2012 12:03 pm
Posts: 5718
Location: Canada
I just played a game against it. I would recommend looking at Hayauchi Super Igo. I'm not quite sure how good it is, I did beat it, but it did seem to be playing at a reasonable capacity.


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 19 posts ]  Go to page 1, 2  Next

All times are UTC - 7 hours


Who is online

Users browsing this forum: No registered users and 7 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB® Forum Software © phpBB Group