It is currently Tue Jul 17, 2018 10:46 am

 All times are UTC - 7 hours

 Page 1 of 2 [ 19 posts ] Go to page 1, 2  Next
 Print view Previous topic | Next topic
Author Message
 Post subject: Go on the NES - is it feasible?Posted: Thu Apr 14, 2016 12:57 pm

Joined: Thu Jul 23, 2015 7:54 pm
Posts: 180
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 [ 34.16 KiB | Viewed 3042 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

 Post subject: Re: Go on the NES - is it feasible?Posted: Thu Apr 14, 2016 1:48 pm

Joined: Thu Mar 31, 2016 11:15 am
Posts: 316
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

 Post subject: Re: Go on the NES - is it feasible?Posted: Thu Apr 14, 2016 1:55 pm

Joined: Fri May 08, 2015 7:17 pm
Posts: 2144
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

 Post subject: Re: Go on the NES - is it feasible?Posted: Thu Apr 14, 2016 2:38 pm

Joined: Sun Apr 13, 2008 11:12 am
Posts: 7307
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

 Post subject: Re: Go on the NES - is it feasible?Posted: Thu Apr 14, 2016 2:46 pm

Joined: Sun Jan 22, 2012 12:03 pm
Posts: 6399
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

 Post subject: Re: Go on the NES - is it feasible?Posted: Thu Apr 14, 2016 3:39 pm

Joined: Sun Sep 19, 2004 11:12 pm
Posts: 20257
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

 Post subject: Re: Go on the NES - is it feasible?Posted: Thu Apr 14, 2016 3:58 pm

Joined: Sun Jan 22, 2012 12:03 pm
Posts: 6399
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

 Post subject: Re: Go on the NES - is it feasible?Posted: Thu Apr 14, 2016 6:09 pm

Joined: Sun Dec 12, 2010 10:27 pm
Posts: 312
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

 Post subject: Re: Go on the NES - is it feasible?Posted: Thu Apr 14, 2016 6:27 pm

Joined: Thu Jul 23, 2015 7:54 pm
Posts: 180
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

 Post subject: Re: Go on the NES - is it feasible?Posted: Thu Apr 14, 2016 6:54 pm

Joined: Fri May 08, 2015 7:17 pm
Posts: 2144
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

 Post subject: Re: Go on the NES - is it feasible?Posted: Thu Apr 14, 2016 7:20 pm

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

Top

 Post subject: Re: Go on the NES - is it feasible?Posted: Thu Apr 14, 2016 7:29 pm

Joined: Thu Jul 23, 2015 7:54 pm
Posts: 180
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

 Post subject: Re: Go on the NES - is it feasible?Posted: Thu Apr 14, 2016 7:34 pm

Joined: Fri May 08, 2015 7:17 pm
Posts: 2144
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

 Post subject: Re: Go on the NES - is it feasible?Posted: Thu Apr 14, 2016 8:12 pm

Joined: Sun Jan 22, 2012 12:03 pm
Posts: 6399
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

 Post subject: Re: Go on the NES - is it feasible?Posted: Thu Apr 14, 2016 8:48 pm

Joined: Sun Jan 22, 2012 12:03 pm
Posts: 6399
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

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 1 of 2 [ 19 posts ] Go to page 1, 2  Next

 All times are UTC - 7 hours

#### Who is online

Users browsing this forum: dougeff, lidnariq and 4 guests

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

Search for:
 Jump to:  Select a forum ------------------ NES / Famicom    NESdev    NESemdev    NES Graphics    NES Music    Homebrew Projects       2018 NESdev Competition       2017 NESdev Competition       2016 NESdev Competition       2014 NESdev Competition       2011 NESdev Competition    Newbie Help Center    NES Hardware and Flash Equipment       Reproduction    NESdev International       FCdev       NESdev China       NESdev Middle East Other    General Stuff    Membler Industries    Other Retro Dev       SNESdev       GBDev    Test Forum Site Issues    phpBB Issues    Web Issues    nesdevWiki