From: tetsuo@fox.nstn.ca (Marc Fleury)
Date: 1 Mar 1996 00:24:04 GMT
Newsgroups: rec.games.abstract
Subject: "Dodgem" . . . any info?
I found an excellent abstract game, but it doesn't seem to be
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.
From: dboll@vcd.hp.com (David Boll)
Newsgroups: rec.games.abstract
Subject: Re: "Dodgem" . . . any info?
Date: 3 Mar 1996 14:55:01 GMT
Organization: Hewlett-Packard
: 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.
I enjoy the game also. I wrote a computer program to play it once that
seemed pretty strong. One big drawback I see: the first player has a
strong advantage; they can start with their 'outside' end piece, and
make sure they always keep it outside. That is, make sure no enemy piece
can beat it to the last row.
There's no obvious-to-me way to get around this first move advantage.
Providing a 'swap' option after the first move wouldn't do it, having
both sides move twice in a row after the first move wouldn't do it.
---------------
Dave Boll dboll@hp-vcd.vcd.hp.com
"The speed of time is one second per second"
From: tetsuo@fox.nstn.ca (Marc Fleury)
Newsgroups: rec.games.abstract
Subject: Re: "Dodgem" . . . any info?
Date: 4 Mar 1996 03:32:57 GMT
Organization: NSTN Navigator User
In article <4hcbs5$bme@news.vcd.hp.com>, dboll@vcd.hp.com says...
>
> I enjoy [Dodgem] also. I wrote a computer program to play it once that
> seemed pretty strong. One big drawback I see: the first player has a
> strong advantage; they can start with their 'outside' end piece, and
> make sure they always keep it outside. That is, make sure no enemy
> piece can beat it to the last row.
>
> There's no obvious-to-me way to get around this first move advantage.
> Providing a 'swap' option after the first move wouldn't do it, having
> both sides move twice in a row after the first move wouldn't do it.
Yes, the first player has a definite advantage. Here's what I do:
When a win is acheived, count up how many more moves it requires the loser
to clear his stones. This is the winner's "score" for the game. BUT! If
the winner played first, SUBTRACT ONE from his score -- this reflects the
advange of playing first. If the winner DID NOT play first, ADD one to
his score.
This way, if you begin, and you only win by one move, your win was an
"empty" one. It scored no points. Your win was based solely on the fact
that you got to play first.
I've also been developing my strategy as the second player. I find it
helps tremendously to keep my outside stone back a little, wait for the
opponent to rush to the corner, and then move my outside stone one step to
the inside. This allows me to slip my stone in behind his.
The added bonus is that I now have a wall two stones long in the next to
last row. Often, the opponent if forced to move his stones the long way
around to circumvent the wall (my opponents seem reluctant to push the
corner stone off the board, even though it is now useless strategically.
Usually, pushing off the corner stone will force me to separate my wall at
some point -- simply because I will have run out of other moves. This
then allows the opponent to slip a stone between mine, and he is back to
the "corner" advantage, though one line back from the actual corner.)
OY! I hope this wasn't too confusing. A little standard nomenclature
would have helped, I think.
PLEASE, more responses! If people are simply not responding because they
are not familiar with the game, get to know it! It's really fun!
(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.)
-- Fleury.
From: jeffe@ocarina.CS.Berkeley.EDU (Jeff Erickson)
Newsgroups: rec.games.abstract
Subject: Re: "Dodgem" . . . any info?
Date: 4 Mar 96 19:18:33 GMT
Organization: University of California, Berkeley
tetsuo@fox.nstn.ca (Marc Fleury) writes:
>(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
jeffe@cs.berkeley.edu
http://www.cs.berkeley.edu/~jeffe
Newsgroups: rec.games.abstract
From: davidmb@aisb.ed.ac.uk (David McBryan)
Subject: Re: "Dodgem" . . . any info?
Organization: Dept of Artificial Intelligence, Edinburgh University, Scotland
Date: Tue, 5 Mar 1996 12:51:31 GMT
In article <4h5g34$k4@news.nstn.ca>, tetsuo@fox.nstn.ca (Marc Fleury) writes:
|> I found an excellent abstract game, but it doesn't seem to be
|> 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.
I think I know this game. Tell me if this is right :
Each player (Black,White) has 2 pieces and the start position is :
_______
|B| | |
-------
|B| | |
-------
| |W|W|
-------
Forward for Black is to the right, whereas for white it is straight up.
If this is dodgems, then I know it well. We had to examine it as an example
in a planning an search assignment a couple of years ago. I proved that the
first player can always win. We also wrote a program to play this which
always wins when it plays first and can only be beaten in one way when it
plays second. The tactics for second player are quite interesting : easily
the best strategy is to aim for this position after two moves each :
(Where player one is white)
_______
| | |W|
-------
|B|B| |
-------
| |W| |
-------
This can usually be achieved, as if white has not advanced his rightmost
piece two spaces, he will lose.
From here white has to make the counterintuitive move of moving his piece
on the final row (top) to the left, as otherwise he will lose.
(If he removes it, black can move his leftmost piece up, and will win)
Any more discussion of this game welcome, although I fear the analysis has
all been done.
Dave.
From: jeffe@ocarina.CS.Berkeley.EDU (Jeff Erickson)
Newsgroups: rec.games.abstract
Subject: "Dodgem" again
Date: 11 Mar 96 23:57:25 GMT
Organization: University of California, Berkeley
At Paul Colley's instigation, I've started writing aprogram to serach
for drawn positions in Dodgem on small boards, thinking that the
serach space would be small enough that brute force would be usable.
I was wrong. As a first step, I wrote a small program to enumerate
legal Dodgem positions on an nxn board. My initial estimates for how
many positions there are were way too low. Here are the correct
values:
n=2: 21 positions
n=3: 1,495 positions
n=4: 303,433 positions
n=5: 197,841,801 positions
These numbers positions where all of one or both player's cars are
completely off the board, and do not take any symmetry into account.
Needless to say, I didn't even try the n=6 case, and brute force
search even on the 5x5 board is prohibitive.
The correct order of growth is something like n^{2n}. (I have an
exact formula, as the sum of products of binomial coefficients, which
I can post if anyone cares.)
I plan to completely analyze the 4x4 case. I expect not to find any
draws, but you never know.
--
Jeff Erickson
jeffe@cs.berkeley.edu
http://www.cs.berkeley.edu/~jeffe
From: desj@ccr-p.ida.org (David desJardins)
Newsgroups: rec.games.abstract
Subject: Re: "Dodgem" . . . any info?
Date: 18 Mar 1996 22:34:10 -0500
Organization: IDA Center for Communications Research, Princeton
There are many drawn positions on a 4x4 board. Perhaps the simplest are
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.
From: desj@ccr-p.ida.org (David desJardins)
Newsgroups: rec.games.abstract
Subject: Re: "Dodgem" . . . any info?
Date: 19 Mar 1996 20:47:40 -0500
Organization: IDA Center for Communications Research, Princeton
On further inspection of my results, I see that not only are there
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
--
Copyright 1996 David desJardins. Unlimited permission is granted to quote
from this posting for non-commercial use as long as attribution is given.
From: desj@ccr-p.ida.org (David desJardins)
Newsgroups: rec.games.abstract
Subject: Re: "Dodgem" . . . any info?
Date: 20 Mar 1996 20:05:09 -0500
Organization: IDA Center for Communications Research, Princeton
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.)
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.
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.
From: hoey@aic.nrl.navy.mil (Dan Hoey)
Newsgroups: rec.games.abstract
Subject: Re: "Dodgem" . . . any info?
Date: 26 Mar 1996 17:02:52 GMT
Organization: Navy Center for Artificial Intelligence
desj@ccr-p.ida.org (David desJardins) writes:
> 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.
Dan
Hoey@AIC.NRL.Navy.Mil