[Community Puzzle] Dots and Boxes

https://www.codingame.com/multiplayer/bot-programming/dots-and-boxes

Send your feedback or ask for help here!

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

@EricSMSO, it seems like the referee is returning score 1.0 for the winner and -1.0 for the loser. It would be better if it instead returned the real score (e.g. 25.0 vs 24.0) and used -1.0 only in case of timeout.

I thought setScore() was a true/false method. Do you mean It would be used in the leaderboard to make a difference between winning with a great score difference or winning with close scores?

Unless we speak about a different method, Player.setScore takes an int parameter, not a boolean. The integer parameter is used to rank the players, which is what will be used by the leaderboard. So using the real score (and -1.0 for timeouts) will not change the leaderboard. However, it is better practice: it makes it easier for community tools that parse replays to detect timeouts, and to learn information about the final score, which is otherwise hidden.

2 Likes

Ah ok, I will see if I can change this this weekend. I think I copied this behaviour from the Tic Tac Toe referee. Where did you get the information about the setScore() method from?

Done. Hope I haven’t broken anything.

1 Like

What are some strategies you used? I tried MCTS over MinMax due to the branching factor, but 100 ms is too little time for sufficient exploration on 7x7 (2x2 was no problem). Does the higher efficiency of minimax exploration compensate for the small achievable depth or do you have to rely on a very good heuristic function?

Edit: Minimax does work you just have to find out which moves are pretty much identical. No idea how @Crazy_Remi got his bot so good though :smiley:

My program is a simple alpha-beta.

Here is a collection of links I found useful:

I did not implement the Nim theory at all, but I will when someone beats my current entry.

13 Likes

Thanks a lot for sharing @Crazy_Remi!

1 Like

I’m trying to complete “Solve puzzle of the week” quest from the homepage. I did pass the first league and now I’m on 54th place in the second league. When will codingame consider this puzzle completed by me, so that I can get my sweet-sweet XP? Cheers!

This is a bug. Someone has already posted it in the forum.

Same, I would appreciate if i get my XP too :frowning:

Noice, dots and boxes nearly quadrapled this week.

Any tips on how to translate the box and sides format to something more easy to use?

Great I am very happy with this! The problem is now I am beaten by so many people.

1 Like

Is the way the validator provides the current board state to the program willfully unpleasant? The complete board state can’t even be derived from it, as far as I can see. Is it intended that you have to reverse the input to figure out what move your opponent made, so you can replay it in the internal representation of the board that you keep in memory? It would be much, much more convenient if you were just given the opponent’s move itself, to be quite honest…

Hi colinemonds, sorry it doesn’t please you but it was not on purpose, or was it?

  • The information is complete at every game turn.
  • Some people prefer to have only the opponent’s last move.
  • Some people prefer to have the complete board representation at every game turn.
  • The advantage of the second option is that any one can easily pick a playable move without even having an internal representation.
  • I admit I could have added the last opponent’s move but now it is too late. :confused:
1 Like

Technically you can do that with ‘EXPERT’ mode. See Othello. At first it didn’t have last opponent move, then struct updated that without breaking current bots. Still, I wonder if this feature is worth the trouble.

Love seeing this math puzzles in codingame