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.
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.
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.
Attachment:
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 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.