From:tetsuo@fox.nstn.ca (Marc Fleury)Date:1 Mar 1996 00:24:04 GMTNewsgroups:rec.games.abstractSubject:"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.abstractSubject:Re: "Dodgem" . . . any info?Date:3 Mar 1996 14:55:01 GMTOrganization: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.abstractSubject:Re: "Dodgem" . . . any info?Date:4 Mar 1996 03:32:57 GMTOrganization: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.abstractSubject:Re: "Dodgem" . . . any info?Date:4 Mar 96 19:18:33 GMTOrganization: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.abstractFrom:davidmb@aisb.ed.ac.uk (David McBryan)Subject:Re: "Dodgem" . . . any info?Organization:Dept of Artificial Intelligence, Edinburgh University, ScotlandDate: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.abstractSubject:"Dodgem" againDate:11 Mar 96 23:57:25 GMTOrganization: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.abstractSubject:Re: "Dodgem" . . . any info?Date:18 Mar 1996 22:34:10 -0500Organization: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.abstractSubject:Re: "Dodgem" . . . any info?Date:19 Mar 1996 20:47:40 -0500Organization: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.abstractSubject:Re: "Dodgem" . . . any info?Date:20 Mar 1996 20:05:09 -0500Organization: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.abstractSubject:Re: "Dodgem" . . . any info?Date:26 Mar 1996 17:02:52 GMTOrganization: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