Coding Games and Programming Challenges to Code Better
Send your feedback or ask for help here!
Created by @User123,validated by @N3l,@Anonimee and @kozuechan.
If you have any issues, feel free to ping them.
This is a great puzzle. Thank you so much for contributing it.
I am having problems to understand the decision logic. Letās take the example āHold the Drawā from the examples provided:
O
.O.
..X
.X.
I have calculated, for each possible move of O, how many paths will lead to (a) O winning, (b) X winning, (c) tie. I get these three statistics for each possible move of O.
I define chance_of_O_winning = numer_of_paths_O_wins / (paths_X_wins + paths_O_wins)
By doing so, the center tile has the biggest chance of O winning. This follows the common sense logic of āgrab the middle if you canā.
The solution suggest that O places in the top left corner. The example name (āHold Drawā) suggests that the logic chooses this path, since it maximizes how long I can delay a draw.
I am having difficulty to understand what ādelaying the drawā seems to have been the deciding logic; and not āmaximizing chances of O winningā (which would be given by the middle field).
Thanks
Hi @Banta2000 ,
If you play the center tile, and I play the tile at the bottom right:
.O.
.OX
.XX
Iām sure to win the game ^^
@GFabian thank you so much!! This absolutely solved the mystery for me.
As a matter of fact, I assumed that the opponent would play all possible moves - and then I would compute the win / loss statistics. In fact, the opponent plays always optimal turns. Meaning, the opponent will not permutate through all possible moves, but rather only choose moves that will either force a win or a tie for the opponent.
This allowed me to solve the puzzle.
Thanks a lot.
Iām having a lot of fun with this puzzle, but there are two things that concern me.
Firstly, it seems to me that to do it without any hardcoding you would have to simulate every possible game recursively and filter the results down based upon the length of the resulting game while only keeping options with the best chance of winning or drawing (since I noticed that a high priority cell that wins in all but one situation is not preferred over a low priority cell that draws in every situation). A recursive search is probably reasonable considering it is only a 3x3 grid, but I didnāt like the thought so I hardcoded some things, such as, if there are only two pieces on the board and they do not share an axis, place the piece in the highest value cell that shares an axis with both. It seems to work. If those checks find nothing, I simulate the resulting game for every available move with the assumption that the other player will always choose an obvious best move (a defensive or winning move) or the cell with the highest priority, rather than checking every nested possible move and/or having to define the best move for all cases.
My other concern is that the validators may need some adjusting. Iām failing test cases 8 and 11 but passing all validators except 7. Itās always preferable to pass with bad code than fail with good code, so fixing validator 7 would suffice.
Edit: Turns out I hadnāt called the game over check at the start, validator 7 works now. I have no clue how I passed the test case before, must have managed to reach the cell assignment function with an empty list.
1 Like
Hey @Sflubaduba, thanks for checking out the puzzle! 
The puzzle is definitely brute force-able since there are only 3^9 = 19683 possible board states (including illegal ones)! Your two-piece shared axis heuristic does sound interesting though. I canāt think of any possible board states that would prove a counter-example of the best move off the top of my head, but maybe iterating over all possible turn 3 W/B states may yield something.
Not sure why you were failing tests 8 and 11, could you maybe provide more details? Is the validator set still of concern? Thank you!
Considering that validator 7 was entirely my error, the validators are probably fine. Now that Iām done getting sidetracked on the clash puzzle that this inspired, Iāll work on passing tests 8 and 11 and hopefully find out why I āfailed successfullyā. Iāll let you know if I do.
The TLDR:
All issues were of course errors that I had made, but I have ideas to make the validators as difficult as the test cases.
Test 8: originally timed out because the simulation was checking the original board for empty cells after new pieces had been placed. After fixing that, it would choose a move that could possibly win instead of holding the draw. I passed the test by adding a hardcoded check to the simulation: if, at any time, swapping the piece types and rotating the board 180 degrees returns the original board, save that game as a draw.
Test 11: was entering my two piece heuristic check but not doing anything because the pieces are on the same axis. After fixing that, I needed another hardcode to avoid entering the simulation and pass the test: if there are only two pieces, they share an axis and the centre cell is empty, place the piece in the centre cell.
______________________________________________________________
A More Detailed Analysis and Ideas for Validators: (relies on context from above)
Test 7:
No issue at all. Iām thinking I must have forgotten to run it again after turning the game over check into a function (and forgetting to call it), so I thought I had passed the test case when I hadnāt. Iāve just loaded the old code, it fails both cases.
Test 8:
Firstly, I have no idea why test 8 was the only one that timed out. The problem was that both players were repeatedly placing their pieces in the same cell because it was marked empty. I checked; tests 3, 6 and 8 and validators 3 and 11 all fail when I remove the simulation, so they should have failed before too. Try checking that all of the following are the same between pair 8 cases to hopefully make the validator fail under the same circumstance: total pieces on the board, game over status, maximum number of same type pieces in a line with no opponent pieces.
With that sorted, I was still failing the test but passing the validator. The simulation would find that, referring to cells by their value: after I place in 3, the opponent would choose 9, then I win by choosing 8. Thatās purely a limitation of my code because obviously the opponent would either block my corner gambit or continue with their one and win the game; however, we should be able to make the validator fail the same way simply by rotating or mirroring the board from the test case. Iāve run some tests, rotating and mirroring the board, the results are a bit all over the place, but my old code only seems to get the right answer if the right answer is 8 (thatās just my assumption of the right answer because Iām not performing full checks to find it).
Test 11:
The first fix for this one is nice and easy: the validator should have only two pieces, both on the same axis, ideally right next to each other (if it doesnāt already - I might have been getting lucky).
My second problem was that my simulation would absolutely never choose the centre cell when the two pieces were on the same axis. Thatās just a limitation of my code, but having the centre cell free and both pieces on the same axis for the validator would make it fail. The problem with that is, if my new heuristic is correct, the answer will always be 9. If you can find a situation where both pieces share an axis and the centre cell is not the best, that would be an awesome validator.
Another pair of test cases where there are two pieces, they share an axis and the centre cell is taken would be good too. Iām pretty sure my new code would fail that.
__________________________________________________________________
If you choose to make these changes, let me know, Iāll run my old versions and see if they fail. Maybe my new code will fail too and Iāll have to do it the right way.
Great puzzle, and thanks for your help with mine.
1 Like
Thanks for the detailed analysis @Sflubaduba! Iāve made edits to the test/validator sets accordingly 
1 Like
Perfect matches now and my new code fails. Good work 
I was struggling with Hold the Draw test case a lot. When I finally solved it, I got all IDE tests green, but Validator 8 is failing. Could someone help me with that? Maybe provide similar test case so that I could improve my code? My initial solution didnāt really use turns in the logic, at least not explicitly, I tried using them in the last submission, but it didnāt really help.
Turns out when I was investigating failing Validator 8 I already found possible issue - one move wasnāt added in specific case, but I forgot to add it to my submission. After adding it everything is green now! And thanks, @cedricdd, for the help.
This puzzle is missing C# solutions, guys! I wanted to see someone implement minimax here, as I didnāt use it in my solution. Another solution was good enough.