[Community Puzzle] Atari Go 9x9

Puzzles
#1

https://www.codingame.com/multiplayer/bot-programming/atari-go-9x9

Send your feedback or ask for help here!

Created by @Tux4711,validated by @trictrac,@dbdr and @field3.
If you have any issues, feel free to ping them.

#2

Replay:

One of victory conditions are:

  • If no player has captured any stones after the maximum number of turns is reached, the player that has played more stones wins (to prevent a draw if a player passes in every move)

But I placed a stone, and nothing else happened, then I lost the game.
image

#3

I also had a similar problem. You lost because you are white as the second player. The UI is a little bit confusing, since it is showingg the color of the captured stones. It would be better if it showed the color of the player instead.

4 Likes
#4

java.lang.ArrayIndexOutOfBoundsException: Index 1 out of bounds for length 1
at com.codingame.game.Player.getMove(Player.java:23)
at com.codingame.game.Referee.gameTurn(Referee.java:230)
at com.codingame.gameengine.core.GameManager.start(GameManager.java:122)
at com.codingame.gameengine.core.RefereeMain.start(RefereeMain.java:67)
at com.codingame.gameengine.core.RefereeMain.main(RefereeMain.java:50)

1 Like
#5

Got almost the same error message as Fine_mouche :

java.lang.ArrayIndexOutOfBoundsException: Index 0 out of bounds for length 0
at com.codingame.game.Player.getMove(Player.java:23)
at com.codingame.game.Referee.gameTurn(Referee.java:230)
at com.codingame.gameengine.core.GameManager.start(GameManager.java:122)
at com.codingame.gameengine.core.RefereeMain.start(RefereeMain.java:67)
at com.codingame.gameengine.core.RefereeMain.main(RefereeMain.java:50)

What’s causing it?

Edit : While debugging, I found that I could reproduce the error by outputting “#{nil} #{nil}” (which was basically what my faulty code was doing). So, this might have to do with how the game engine handles nil values.
Also, I’m doing the puzzle in Ruby.

1 Like
#6

Try submitting your go as “x y” with a space in-between rather than a comma

#7

ok i will try

#8

Why the number of max turn reduce over runs ? it start 80 max turn and at a moment it end at 1 turn max …

#9

There is a bug in the judge’s code. If I play into one of my own eyes of size 1, I lose. I agree that it’s a bad move, but not that bad. :slight_smile: Note that this happens even if the resulting group has lots of liberties.

#10

hey there,
i m still a little clueless how to eavaluate each possible position and how far into the future i should look. Is there any “easy” evaluation of the board ? All i found on the internet are like 20 page papers that look way to complicated haha

#11

You can actually evaluate the security of each group separately most of the time. You don’t need to look at the whole position as such. And it’s made easier by the fact that you don’t have to evaluate territory, only number of groups that you can capture and prevent capture of.

My current version does some super simple things:

  1. Check if an enemy group only has one liberty and, if so, capture it.
  2. Check if one of my groups only has one liberty and, if so, try to extend it to save it.
  3. If none of these apply, make a random move.
    And with that simple strategy, my program is number 5 already in league number 3. I’m pretty sure that if I start to do willful atari’s on other groups and avoid self-atari I will get to league 2 already.
#12

That sounds pretty interesting! I m trying to get my code efficient enough to calculate 4 steps ahead but it always time-outs … are you working with the strings given as an input or which kind of data-structure do you use ?

Also what i noticed by your rule 2: That often leads to some situation, where you place like 10 stones head to head with the enemy and than it takes like 15 stones, feels like looking at one liberty at your own groups might be sth to adjust, what do you think ?

#13

I think that some go knowledge will beat any lookahead if you don’t know what you’re evaluating for. I think you should be able to calculate 4 steps ahead, but only for a subgoal like capturing or defending a group.

Regarding data structures, I an working with a 2-dimensional array of ints (1=ME, 2 = THEM, 0 = EMPTY) but I will switch this to a 1-dimensional representation very soon. At some point, e.g. where I need to calculate the neighbors of a position I will still need 2D because points at the edge only have 3 neighbors and points in a corner only have 2. But those cases are not that common, and I can write a macro or function to handle it.

To really move up in the leagues, I think you need to start using more go knowledge like good shape and creating eyes for your groups.

#14

Also note that some lookaheads like ladders easily can go 20 moves deep but they are extremely narrow in the search.

#15

Sadly for me, i cant even calculate 2 moves ahead for every possible position without getting a timeout. But as you said, i might just lack the knowledge about GO to know what i’m actually looking for. I m using a lot of functions, e.g. get_neighbors.

def get_neighbors(board, board_size, x, y):
   neighbors = []
   if x > 0:
       neighbors.append((x-1,y))
   if y > 0:
       neighbors.append((x,y-1))
   if x < board_size-1:
       neighbors.append((x+1,y))
   if y < board_size-1:
       neighbors.append((x,y+1))
   return neighbors

Is that in generell the right approach ?

And your 2-dim array, is it for just counting pieces and empty fields or is it a list of coordinations ?

#16

The get_neighbors() function looks good. But getting neighbors is easy, the problem is what to do with them.

I have a an array[][] of ints to represent the board. From that I extract the groups, which I store in a vector. Each group looks like this:
struct Group {
Group(int color, int firstPos);
void maybeAddStone(int pos);
void maybeAddLiberty(int lib);

int       color;
int       startPoint;
set<int>  stones;
set<int>  liberties;
int numLibs;
int numStones;

};
The functions add a stone or liberty to the respective set if it’s not already a member. (Btw, liberty is a go term for an open space which is a neighbor of a group of stones.) Currently I use this struct to decide whether I can attack an enemy group (numLibs <=2) or if I need to defend one of my own groups (numLibs == 1).

Right now, I’m not using lookahead at all, but I’m pretty sure that I will need to in the higher leagues. But I’m never going to do full board lookahead, only for attacking/defending a single group at a time. So the goal for the lookahead would be to kill or defend one group, not get an evaluation of the full board.

Another thing that I probably need to do to get something useful out of just 100 ms is a bitboard representation of groups and other sets of positions. Another key to successful lookahead is to limit the set of moves that you try out and to always look at the . But for that you need a little go knowledge. An easy way is to always attack on the liberty first that would give enemy group most new liberties if they were to play there themselves.

#17

Btw, another tip to make your program stronger easily: Don’t play at the edge in the beginning. Those stones are very weak and can be easily attacked.

#18

I fixed my code to not play at the edge until it’s necessary and to not fill my own eyes and now I’m #1 in league 3. Actually I thought that I’d move up with those changes but it seems that it’s missing a lot of opportunities by discarding all edge moves instead of just in the beginning.

Next I’m going to try to attack weak enemy groups, i.e those with number of liberties == 2. I’m sure that will be enough.

#19

Interesting Point, just watched a battle of us two and it seems in generell, that mine is a bit more aggressive and good at taking early points, but at the end i play a lot of stupid moves just giving you kind of free points. You said before if there is no good move, you just play a random one. That doesnt seem to work out for me … Is it intentionall at one point of the game if you have only safe groups and more points to just PASS for the rest of the game ?

#20

Yeah, not filling in your own eyes is very intentional. If you do, that’s the best way of losing a winning position. :slight_smile:

My bots’ opening is very bad and that’s caused by the random moves. I want to have a stable foundation before I start working on that, and being decent at attack and defense is part of that. I have rewritten part of the core of my engine now but it’s not in action yet.

Previously I tried to generate moves and then evaluate how valuable they were, given what they captured or defended. Now I have split up the process into 3 steps:

  1. Analyze the situation. Right now, this only means finding attack and defense points of all the groups but in the future it could involve other considerations like number of eyes or connectivity between groups.
  2. Generate move reasons. That could be “capture a group”, “defend a group”, connect 2 weak groups to make one strong, split the opponent into 2 weak groups, and so on.
  3. Combine all the reasons to move to a specific point and make a combined value.

The third step is the main reason for the rewrite. Before it was very difficult to see that attacking one group of the opponent at the same time defends one of my own. That is now trivial. So I can find out properties separately from valuating them in combination with other reasons.

The next version of my bot will have one more feature than the old one: Attacking groups with 2 liberties. Before I only captured what was put into my mouth, so to speak, i.e. groups with only 1 liberty.

But after this change, it will be much, much easier to add new move reasons and to combine them into a good evaluation of a move. It will also be easier to set up a sound opening so that I don’t leave cheap points to the opponent that I have then take back later. :slight_smile: What will still be lacking is good tactical lookahead since that is much more complicated.

Could you give me a link so that I can check out the same game as you looked at?