Subject:
|
Brickgame [connect 4] algorithm
|
Newsgroups:
|
lugnet.off-topic.geek
|
Date:
|
Tue, 30 Jan 2001 22:05:14 GMT
|
Viewed:
|
101 times
|
| |
|
|
Ok, I'm a geek. I admit that. But now that I've got that out of the way,
lemme say I've always loved connect 4, just because it's such a more
strategic game (like checkers, rather) than one typically accounts for--
rather than say, tic-tac-toe, which is vastly limited in possibilities.
Anyway, that said, I've thought about writing (just for the heck of it) an
algorithm for playing it. It seems to be pretty good-- I can beat it mostly,
but usually it does a pretty good job, which rather suprised me, since it's
a fairly simplistic algorithm.
Anyway, if ANYONE even REMOTELY cares:
Algorithm attempt #1:
Each square has X amount of ways to win associated with it. There's only 3
ways to win from a corner square for example. So, the 1st attempt (this
chart is important later) is to simply take the square with the most
possibilites to win. Using TLC's 7x7 board (not the traditional 7x6 board):
------------------------
| 3 4 5 7 5 4 3 |
| 4 6 8 10 8 6 4 |
| 5 8 11 13 11 8 5 |
| 7 10 13 16 13 10 7 |
| 5 8 11 13 11 8 5 |
| 4 6 8 10 8 6 4 |
| 3 4 5 7 5 4 3 |
------------------------
However, using this basic value system, I noticed that the algorithm tended
to build straight up to the top, while I had already focused a
'counter-attack' at a lower level that had lesser value for the algorithm.
Hence, I figured there should be some way to 'devaluate' the upper rows,
since most often, you can win without ever reaching that point. Hence, a new
value system for the squares, getting less valuable towards the top:
------------------------
| -3 -2 -1 1 -1 -2 -3 |
| -1 1 3 5 3 1 -1 |
| 1 4 7 9 7 4 1 |
| 4 7 10 13 10 7 4 |
| 3 6 9 11 9 6 3 |
| 3 5 7 9 7 5 3 |
| 3 4 5 7 5 4 3 |
------------------------
So now, the algorithm:
1. If I can win by going to a certain square, go there.
- End turn
2. If the other player can win by going to a certain square, go there.
- End turn
3. Go to the most highly valued available square on the board.
4. If the move chosen by #3 allows the other player to win (I.E. the space
ABOVE the chosen square), set the value of that square to -10, and go back
to step 3.
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.
- End turn
Tiebreaker clause:
If two spaces match in value:
- take the space adjacent to more of my 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 :)
Anyway, That's about it... Pretty simple, actually, without digging several
ply into the game... Or re-calculating the grid at each phase... Anyone got
any suggestions? Comments? Etc? Did you actually care about this message? :)
DaveE
|
|
Message has 2 Replies:
 | | Re: Brickgame [connect 4] algorithm
|
| (...) heh, I liked it. Never thought of trying a connect 4 game... I did write a tic-tac-toe that learned from experiance... hmmm... I'm trying to think of a way to quantify the killing play (one that leaves you two ways to win next turn) without (...) (24 years ago, 30-Jan-01, to lugnet.off-topic.geek)
| | | Re: Brickgame [connect 4] algorithm
|
| (...) I remember reading some years ago that this game has actually been solved; that is, there is a way for whoever goes first to win every time. *does google search* Yeah. Victor Allis of Vrije Universiteit in Amsterdam. (URL) (...) (24 years ago, 31-Jan-01, to lugnet.off-topic.geek)
|
5 Messages in This Thread:
  
- Entire Thread on One Page:
- Nested:
All | Brief | Compact | Dots
Linear:
All | Brief | Compact
|
|
|
|
