| |
In lugnet.org.ca.rtltoronto, Derek Raycraft writes:
> I did a quick look through some pages on game theory and it appears
> there are forced win scenarios for the first player. Now I don't know
> if you can get the algorithm to fit into a RCX but it does make the game
> kind of pointless if you can.
This interested me for a while-- I wrote a recursive program once that would
look X ply into the game, though because I never stored state information,
it took ridiculously exponentially longer with each value of X. Something
like 6 ply was simply unplayable-- it would take 20+ minutes to move. But
theoretically, if you had enough memory/CPU, you could probably run it and
guarantee winning each game (probably 50 zillion times faster but more
memory intensive if you store state info). Dunno if you could recursively
nest functions that deeply on an RCX tho... Max would be what? 42 moves?
I also made a MUCH quicker algorithm that worked fairly well, considering it
didn't really use more than a 1-ply look-ahead:
Initialize:
Evaluate each square of the board according to how many ways there are to
win using that square:
,---------------------,
| 3 4 5 7 5 4 3 |
| 4 6 8 10 8 6 4 |
| 5 8 11 13 11 8 5 |
| 5 8 11 13 11 8 5 |
| 4 6 8 10 8 6 4 |
| 3 4 5 7 5 4 3 |
`---------------------'
(huh, without the fancy ASCII border, the LUGNET web-interface thought this
was a DAT!)
Next, re-evaluate each square by discounting higher rows (-1 per
elevation... to avoid repeat-stacking):
,---------------------,
|-2 -1 0 2 0 -1 -2 |
| 0 2 4 6 4 2 0 |
| 2 5 8 10 8 5 2 |
| 3 6 9 12 9 6 3 |
| 3 5 7 9 7 5 3 |
| 3 4 5 7 5 4 3 |
`---------------------'
Algorithm basics:
Phase 1:
If you can win in one move, go there.
Phase 2:
If your opponent can win in one move, go there.
Phase 3:
Select the highest valued square on the board.
Phase 4:
If your opponent can win by moving on *top* of the desired move, subtract
100 from the value of the square, and go back to phase 4.
Phase 5 (beginner's trap clause):
If two spaces on the bottom row are taken (by opponent) within 3 spaces of
each other, AND no spaces are taken by me within 2 spaces of either of these
already taken spaces, choose the highest valued spot within that range.
Tiebreaker clause:
If two spaces match in value:
- take the space adjacent to more of your own already-taken squares
- If adjacent counts are the same, choose based on the 'non-biased' grid
(I.E. the one that doesn't account for top-to-bottom values)
- If these squares are the same, go to the square with more adjacent
squares owned by the opponent.
- Else, just pick at random :)
You can also re-evaluate the board at each stage dynamically according to
who owns which squares, but that starts to take longer per iteration--
especially considering you want to consider both what's valuable to you
*and* to your opponent, so you've got to evaluate the board twice, and do
extra logic.
DaveE
|
|
Message is in Reply To:
 | | Re: connect four
|
| I did a quick look through some pages on game theory and it appears there are forced win scenarios for the first player. Now I don't know if you can get the algorithm to fit into a RCX but it does make the game kind of pointless if you can. Derek (22 years ago, 19-Mar-03, to lugnet.org.ca.rtltoronto)
|
40 Messages in This Thread:
 
 
- Entire Thread on One Page:
- Nested:
All | Brief | Compact | Dots
Linear:
All | Brief | Compact
|
|
|
|
