"Dodgem" . . . any info?
Marc Fleury
mentioned in this group's charter. It is called "Dodgem" in _Winning Ways
For Your Mathematical Plays_ by Berlekamp, Conway and Guy. (which I
figured would be this group's Bible!)
Anyway, the game is credited to Colin Vout. It's a brilliant and
deceptively simple game played on a 3x3 grid. Each player, sitting
crosswise from the another, must attempt to move his "cars" off the far
end of the board. Cars may only move forward (in respect to the player)
or laterally, not backwards. The strategy comes about in using your cars
to block your opponent's motion while furthering your own progress.
Even on a 3x3 board, some clever strategies can be acheived. The
game can also be made more complex by playing on a larger board.
I'm wondering if anyone has any further information on this game
or its creator.
-- Fleury.
Jeff Erickson
>(Oh... any chance of you still having that program around? I'm just
>starting to learn C, so I can't write my own quite yet. What method did
>you use for the computer AI? On a small board, I'm wondering if genetic
>(evolutionary) algorithms would be worthwhile. After dividing by two for
>symmetry, I calculated the number of legal positions at 666 on the 3x3
>board. Seems small enough to handle.)
A complete table of legal positions on the original 3x3 board and who
wins them (left, right, first, or second) is on page 686 of Winning
Ways. No doubt one of the authors (or perhaps Colin Vout) computed it
by hand. This is small enough that you could easily compute an
explicit winning strategy in a few milliseonds. There's no need for
"AI" when brute force will do!
Not surprisingly, there are only three positions (six if you count
reflections along the diagonal) that the second player wins with
perfect play. Hopefully my notation is obvious.
. > > > . . > > .
. . ^ ^ . . . . ^
. . . . . . . . ^
On a chess board (8x8), there are roughly 40 trillion (4 x 10^13)
positions with all the stones on the board, and a few more with one or
more stones off the board, which is just a little too large to store
explicitly. I'd guess that most of these positions are trivial wins
for one player or the other --- just run off the board as fast as
possible, ignoring the other player's moves entirely. These positions
could probably be identified just be counting distances to the goal.
There might be few enough "interesting" positions to store a complete
winning strategy. (This is all just guessing. I haven't actually
tried.)
I wouldn't expect the computer implementation to get really
interesting until you start playing on a go board.
One final question: On a 3x3 board, infinite play is possible, but
stupid. Is there a Dodgem position, on a board of some larger size,
where perfect play results in a hung game? I strongly suspect the
answer is no, but I don't see how to prove it.
--
Jeff Erickson
je...@cs.berkeley.edu
http://www.cs.berkeley.edu/~jeffe
Martin M|ller Pedersen
>One final question: On a 3x3 board, infinite play is possible,
How ? You are not allow to move back !?
Martin M. Pedersen
David McBryan
|> Thus spake je...@ocarina.CS.Berkeley.EDU (Jeff Erickson):
|>
|> >One final question: On a 3x3 board, infinite play is possible,
|>
|> How ? You are not allow to move back !?
But you can move sideways. Although infinite play is theoretically possible,
it should never arise. As I have said before, player 1 can always win, and if
he makes any error, player 2 can win - there is no draw position.
David.
Marc Fleury
|
|je...@ocarina.CS.Berkeley.EDU (Jeff Erickson) writes:
|
||> Is there a Dodgem position where OPTIMAL play forces the game to go on
||> forever? In such a position, neither player could move a car closer
||> to his goal without losing.
|
|Isn't this fairly simple, or am I being dense? On a 4x4 board...
|
| . . . .
| . . . .
| . . > ^
| . . . .
|
|for ever.
|
|OK ?
|
|Bill Taylor w...@math.canterbury.ac.nz
Not OK. Down is an illegal move for ^. (You cannot move away from the
exit line.) The situation you describe is a win for > by one move.
-- Fleury.
David desJardins
of the following sort:
. . . X
. . O X
. . . X
. . . .
(X to move, X moving up, O moving right.)
David desJardins
--
Copyright 1996 David desJardins. Unlimited permission is granted to quote
from this posting for non-commercial use as long as attribution is given.
David desJardins
plenty of drawn positions on a 4x4 board, but the start position is one
of them. Since the start position is a draw, there are many drawing
lines, but a reasonable example of how to get to a draw (i.e., an
example of perfect play by both sides) goes as follows:
(Note: ! denotes the only drawing move in a position.)
4 O . . .
3 O . . .
2 O . . .
1 . X X X
a b c d
1. d1-d2 a4-b4
. O . .
O . . .
O . . X
. X X .
2. d2-d3 b4-c4
. . O .
O . . X
O . . .
. X X .
3. d3-d4 a3-b3
. . O X
. O . .
O . . .
. X X .
4. c1-c2 c4-c3!
. . . X
. O O .
O . X .
. X . .
5. b1-b2 a2-a3!
. . . X
O O O .
. X X .
. . . .
6. c2-d2 c3-c2
. . . X
O O . .
. X O X
. . . .
7. d2-d3 a3-a2
. . . X
. O . X
O X O .
. . . .
8. d3-c3 a2-a3!
. . . X
O O X .
. X O .
. . . .
9. b2-a2 b3-b2
. . . X
O . X .
X O O .
. . . .
10. c3-c4 c2-c1
. . X X
O . . .
X O . .
. . O .
11. d4-off c1-c2
. . X .
O . . .
X O O .
. . . .
12. d3-off b2-b3
. . . .
O O . .
X . O .
. . . .
13. Draw agreed?
David desJardins
legal position with X to move, either X wins, or O wins, or it is a
draw). There aren't any surprises: 5x5 Dodgem, like 4x4 Dodgem, is
still a draw. In fact, even the terrible move 1. b1-a1 is enough to
draw the 5x5 game. (It loses on a 4x4 board.)
Anyway, since I have the table, I should be able to answer most
reasonably well-posed questions about the game. Not surprisingly, as
the board gets larger the game seems to become more drawish: I think
about 40% of 5x5 positions are draws.
It must be true that NxN Dodgem is a draw for every N > 3. However,
proving it would seem to be difficult.
Glenn Rhoads
>I now have a complete table of 5x5 Dodgem positions (i.e., for each
>legal position with X to move, either X wins, or O wins, or it is a
>draw).
Could you make the 4x4 and 5x5 tables available? I'm sure at least a few
people would be interested.
-- Glenn Rhoads
Dan Hoey
> I now have a complete table of 5x5 Dodgem positions (i.e., for each
> legal position with X to move, either X wins, or O wins, or it is a
> draw). There aren't any surprises: 5x5 Dodgem, like 4x4 Dodgem, is
> still a draw. In fact, even the terrible move 1. b1-a1 is enough to
> draw the 5x5 game. (It loses on a 4x4 board.)
Wow, great work. Of course, it would be more startling to see a board
in which the second player can still draw after 1. (not b1-a1), a2-a1.
It seems to me that the reason the game gets so drawish is that
many sheepdogs can gang up on one sheep, forcing a draw even if the
rest of the flock gets away. Does this work even if the flock has a
larger field to run on? Suppose we call N-of-M Dodgem the game played
on an N x N board with M pieces on each side. So regular Dodgem is
2-of-3 and you've looked at 3-of-4 and 4-of-5. What about 3-of-5?
3-of-6?
A surer way of making the game drawless is to forbid repeated
positions. Thus the rule "you lose if you prevent your opponent from
moving" is extended to "... to a position not encountered before." I
imagine this might have a chilling effect--perhaps we might find the
first player losing on some boards. But it also makes the game much
harder to analyze exhaustively.