Source sent (and will send to any who want it). I’d never heard of Hare and Hounds before this thread, but assume the game we speak of is the one described at Wikipedia.
While this game has 11 cells and 3 hounds, there’s a similar game I played as a child, Fox and Dogs, with 32 cells and 4 dogs. But either of these games is easy to solve with computer, or even by hand. (In fact it is almost trivial to adapt the source I send for Fox and Dogs, though I’ll send source for that too if you need it. )
The claim that this game might not have been solved astounded me, frankly. The program I sent solves it with brute force in 1 millisecond or less, so computation isn’t the issue. (Perhaps I solved a different variant than is intended, but I think almost any variant would be similarly trivial.) While I’ll stipulate that most “programmers” wouldn’t have a clue how to solve a game, the number on the planet that could is at least 100,000, I’d guess, rounded to the nearest power of ten. Someone upthread mentioned an on-line player that learns a strategy interactively: that’s much harder than solving the game.
Of course, it’d be good to double-check it by pitting your code against one of the many Java versions of the game you can find online. Just have the two open in different windows, and copy the moves from one to the other. It might be that your implementation of the game is incomplete, and the existing implementations can win by making a move your code didn’t realize was possible.
I guess I failed to underline or emphasize the text which mentioned my solution was derived with computer. It would be hard for even a human to overlook a move in this game since there are so few. Hare must get to the very center to have as many as eight moves. I’m not sure of the status of the “Pentium bug” but even if it actually can’t count to eight – there may be no worry! Hounds are able to prevent Hare from getting to the center cell, at least in the common variation.
Thanks for allowing me to pit my code against just one on-line Java. I chose this one; set it to expert and played the Hounds. The final score was Player 4, Computer 0. This seemed to conclude the experiment as the Computer made exactly the same Hare moves in every game. The Hounds made the same ten moves each time, leading to checkmate. These moves (some of which may seem quite counter-intuitive) were
Center right
Center right
Center right
Bottom diagonal
Top down
Front down
Back up
Center Diagonal
Back Diagonal
Center Right checkmates
I’m sure your remarks were good-natured and well-intentioned, Mr. Chronos. I’d be curious, however, what your reaction would be if our positions were reversed, i.e. if I took a similarly condescending position in a thread, e.g. of physics, where you should be teacher, and I learner.
Interesting. I commented upthread that I didn’t know if it was solved only because I had actually never seen it before reading the OP, which posits the opposite results of your conclusion.
I will add that I actually came to the same conclusion as the OP after playing against the Java version of the game on expert: I was eventually able to always win as the Hare because of this rule: “…if the hounds move 10 times in a row without advancing (i.e. they only move up and down) then the hounds are stalling and the hare wins.” This occurs at the point where the hounds inevitably occupy each of the three center positions; the hare is moving back and forth from its starting position at the far right and just going back and forth from there to the top right hexagon (the rear hound will just go up and down 10 times, resulting in a draw which=hare wins).
OTOH, perhaps that is merely a flaw in the programming of the computer’s play. I don’t have the programming knowledge to map out all of the possible moves so I don’t know.
Yes, without the “hare wins in draw” rule, I think the game may always draw. So like many “pub or parlor games”, it’s just a fun novelty when you encounter it, and if you play infrequently (or are young or not too focused, or dare I say obsessed or smart enough to figure it out precisely) it is just good fun.
FWIW - I had also never heard of the game, but I immediately thought it to be imminently solvable. (I also solve games regularly for fun and profit, and this one appears trivial. If I have any downtime today, I might solve it myself…)
Having done both, I think computer programming is harder than physics, septimus. (Sorry, Chronos!)
There’s a bug in your program in determining hare wins by repetition. I can’t find it–the coding looks correct to me*, but something’s slipping through. Try selecting move A for the rabbit each turn. You’ll notice that the dogs’ seventh move repeats the position from after their fifth, and after this the program will happily enter an unlimited repetition. You can continue to enter A indefinitely, moving the rabbit back and forth along the lower-right diagonal, and the computer will respond by moving that same dog up and down along the back vertical. This should be a rabbit win after ten consecutive vertical moves (actually six, with the default MAXWAIT value you have set), but the program never acknowledges this …
*My C is rustier than you can possibly imagine. I didn’t really expect to be able to figure out a subtle bug. I may try to rework this in an OO language …
I’ve played it through many dozens of times and I can win it with the hare almost every time. The problem is the “draw=hare wins” rule. Every game I’ve played since learning how to win with hare eventually ends up with this arrangement, from which the hare has merely to stall for 10 turns to win, in which case it would seem that if the game were to be solved, it would be solved in the hare’s favor, not the hounds.
Maybe I’m a sadist but I inflicted a deliberate bug just to see if you were serious about running the program. The very last call to dog_canwin needs to increment that wait count argument; here’s the corrected line:
Septimus, when your program is run, can it force a win without ever getting in the position in DCnDC’s link, or can the dogs win from there?
Well, this is kind of lame. We’re all adults here, but whatever. So are you now saying your program always wins with the bug included, or are you saying the program always wins even without the bug?
ETA: DCnDC, in your position, is it the hare’s move, or the dogs?
In the position you refer to, I assume it is Hare’s move. This position seems to be key. This position is arrived at in the detailed ten-move checkmate I posted earlier, and, I think, in the game SCSimmons describes; Hounds’ last move was “Top Down”; after Hare moves up, you play “Front Down” to arrive at
* * R
* D D * *
* * D R=Hare; D=Hound
Hare moves down (at least at the Java page I mentioned); you play Back up; Hare goes right; you play “Center Diagonal” to arrive, with Hare to move, at
* * D
* D * * R
* * D
Sorry for the attempt at humor about the “bug” which affects only the demo play, not the solution. Hounds win if they’re allowed 5 vertical moves. If there’s interest I’ll post Hare’s strategy to beat Hounds when they’re allowed only 4 vertical moves. (Or SCSimmons can do so easily enough, now that we know he’s serious. )
and it is the hounds’ move. From this position, the hare can stall indefinitely, because moving the center hound is suicide, therefore only the front and back hounds are in play, in which case the hare can always force a draw, which = hare wins.
OK, I’m rarely serious, but I’m serious today. That was annoying. :mad: OK, mainly that I didn’t see that counter wasn’t incrementing.
It does work, though. Once the program can see the loops coming up, it adjusts its strategy … I can see where my intuition was leading me wrong, now. I had assumed that if a position repeats, then we had necessarily entered a loop. The program has the same input in that situation, so won’t it try the same move in response as it did the last time that position came up?
That’s true in the buggy version, but not when the code is corrected. I was surprised that the second time the row-of-three position came up in one of my tests, the computer made a different move that it had the previous time. But of course–the other piece of information it’s using isn’t on the board–it’s the number of consecutive vertical moves it’s already made. That closes off a bunch of trees on its search.
So, now to find that winning hare strategy when the hounds are limited to four vertical moves …
There’s a chapter on the Hare and Hounds in volume 3 of the second edition of “Winning Ways for your Mathematical Plays”, which is the definitive work on combinatorial game theory. I don’t have a copy of the book, but from what I’ve read in Amazon’s preview, it looks like the game is solved for small boards and at least one semi-infinite board.
It is the hounds’ move once the board is in this arrangement:
* * *
* D D D R
* * *
so if the front hound moves down, the rabbit moves up, and you get:
* * R
* D D * *
* * D
because the hounds’ only move, really, is to move either the front hound or back hound up or down, neither of which matters because the hare can simply go back and forth from the far right, forcing the hounds to return the to middle or leave an opening for the hare to escape.
Agreed that from here Hounds lose. So we need to examine prior moves and locate Hounds’ blunder.
To the contrary, I’m very impressed you almost found that bug. While my code has a nice tendency to behave as intended, my source is widely deprecated as indecipherable, useful mainly for obfuscation. :smack:
I’m not sure it’s possible to either not end up in that arrangement or otherwise win the game for hounds.
Let’s look at the alternative strategy which would be to advance all three hounds up the board.
Obviously, if the hare gets to the middle hexagon there is no way to stop it from escaping, so the hounds’ first priority no matter what is to occupy that space, yielding:
D * *
* * D * R
D * *
Then, if we move the other two hounds up, no matter what the hare does we’ll end up with:
* D *
* * D * R
* D *
and because there is no way we can advance the middle hound and not lose, another move later we get either:
* * D
* * D * *
* D R
or:
* D R
* * D * *
* * D
Now, at this point we’re essentially out of moves because we still can’t move out of that middle hexagon and advancing the forward hound gives the hare an out, so we can only repeatedly move our forward hound vertically and ten turns later we lose.
So I would have to conclude that you were correct, it is definitely solvable, but just for the opposite team. How does that look to you? Did I miss anything?
)
The very last call to dog_canwin needs to increment that wait count argument; here’s the corrected line:
)
But of course–the other piece of information it’s using isn’t on the board–it’s the number of consecutive vertical moves it’s already made. That closes off a bunch of trees on its search.
