Connect-4
Mark Kern
Hi,
A couple of guys here at the U of R are trying to write connect-4
programs in Scheme. Does anyone have any good ideas for heuristics? Our
programs are due very soon, so if you could, a prompt reply would be
greatly appreciated. Other languages (Prolog, etc.) would be fine too.
A problem that I've been having, is how to recognize that peices are
in a line (diagonal/horiz/vertical). Thanks.
Mark E. Kern
--
=========================================================================
Mark Edward Kern, mek4...@uhura.cc.rochester.edu A.Online: Markus
Quagmire Studios U.S.A. "We not only hear you, we feel you !"
=========================================================================
David A. Lyons
>A couple of guys here at the U of R are trying to write connect-4
>programs in Scheme.
I'm not too familiar with Scheme, but it's similar to LISP, right?
>Does anyone have any good ideas for heuristics?
I like to play (and win) the game, so I've got a couple ideas. A few years
ago I messed around with writing a Connect-4 in BASIC and 6502 machine
language, but the strategy was pretty basic. It was just an N-ply
minimax lookahead checking the number of wins, open 3-rows, open 2-rows, and
open 1-rows for one player, minus the same stuff for the other player,
with fun-to-twiddle coefficients on everything (not just made up, really :-).
BTW, "N" was about 4 in practice...more than that & I got Bored waiting
for it to move.
Anyway, as far as heuristics, here's some of what I try to do when I'm
playing.
Get pieces so that they can help form a 3- or 4- row *later*, even though
they don't right away.
Fix it so there are TWO places I can win, stacked up vertically. If the
opponent blocks the first, I can take the 2nd.
Fix it so there are TWO places I can win on the same move, so my opponent
can block at most one of them.
If my opponent has a potential win somewhere, I try to fix it so either
(1) he can't force me to take the space underneath it, or (2) he must take
the space underneath it, so that I can block.
I haven't tried implementing heuristics like these--if you do, I'd like
to know how it works out. (I'd like to play against the program, too!)
>A problem that I've been having, is how to recognize that peices are
>in a line (diagonal/horiz/vertical). Thanks.
This sounds like a problem expressing your thoughts in the language
you're required to use (I hope?).
It's hard to help without knowing what sort of data structures you're
using for the board.
--
David A. Lyons, Apple Computer, Inc. | DAL Systems
Apple II Developer Technical Support | P.O. Box 875
America Online: Dave Lyons | Cupertino, CA 95015-0875
GEnie: D.LYONS2 or DAVE.LYONS CompuServe: 72177,3233
Internet/BITNET: dly...@apple.com UUCP: ...!ames!apple!dlyons
My opinions are my own, not Apple's.
Felix Lee
version). Below, two articles from my games folder.
--
Felix Lee fl...@shire.cs.psu.edu *!psuvax1!flee
------- Forwarded Messages
From: jamesa%betel...@Sun.COM (James D. Allen)
Newsgroups: rec.games.programmer
Subject: First player can win at Connect-Four
Message-ID: <71...@sun.uucp>
Date: 1 Oct 88 03:07:43 GMT
The game solved is the original 7-by-6 Connect-Four, not the 8-by-8 version
sometimes implemented as a computer game. The game was solved in about 250
hours on a Sun 4/110 workstation. The software examined 22 million positions
per hour. If there's interest I'll post the program.
Although the result was proven exhaustively in the sense that relevant
games were played out to the "bitter end", several heuristics were used
to speed up search:
- curtail search of irrelevant subtrees (alpha-beta pruning)
- killer move prediction (this selected a killer as first
choice over 90% of the time that a killer was available)
- a cache of previously examined positions chosen by
difficulty and recency of use
- a form of breadth-first search which in effect looked
several plys down to see if a killer move could
be found via the cache
There are about 10^23 possible games; without alpha-beta pruning and the
other heuristics, brute-force solution would require about 1 trillion years.
Most of the speedup is due to alpha-beta by itself, but nearly a century
would still have been required without the cache.
For the record, X's winning move is to play in the central column. (I
have not yet checked whether other first moves also win.) The second move
must be chosen with care:
a b c d e f g a b c d e f g
| | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | |
|O| | |X| | | | | |O| |X| | | |
--------------- ---------------
X's second move: a) ? a) ?
b) ? b) ?
c) ? c) ?
d) ? d) doesn't win
e) wins e) doesn't win
f) ? f) wins
g) ? g) ?
a b c d e f g a b c d e f g
| | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | |
| | | | | | | | | | | |O| | | |
| | |O|X| | | | | | | |X| | | |
--------------- ---------------
X's second move: a) ? a) doesn't win
b) doesn't win b) doesn't win
c) draws c) doesn't win
d) doesn't win d) wins
e) doesn't win e) doesn't win
f) wins f) doesn't win
g) ? g) doesn't win
Since some very plausible moves do not win, we can say that X
"just barely" has a won game.
------- Message 2
From: vic...@cs.vu.nl
Newsgroups: rec.games.programmer,comp.ai
Subject: AI program solves Connect Four
Message-ID: <15...@kappl.cs.vu.nl>
Date: 16 Oct 88 14:06:58 GMT
Organization: VU Informatica, Amsterdam
An AI program has solved Connect Four for the standard 7 x 6 board.
The conclusion: White wins, was confirmed by the brute force check made by
James D. Allen, which has been published in rec.games.programmer at October 1st.
The program called VICTOR consists of a pure knowledge-based evaluation
function which can give three values to a position:
1 won by white,
0 still unclear.
- -1 at least a draw for Black,
This evaluation function is based on 9 strategic rules concerning the game,
which all nine have been (mathematically) proven to be correct.
This means that a claim made about the game-theoretical value of a position
by VICTOR, is correct, although no search tree is built.
If the result 1 or -1 is given, the program outputs a set of rules applied,
indicating the way the result can be achieved.
This way one evaluation can be used to play the game to the end without any
extra calculation (unless the position was still unclear, of course).
Using the evaluation function alone, it has been shown that Black can at least
draw the game on any 6 x (2n) board. VICTOR found an easy strategy for
these boardsizes, which can be taught to anyone within 5 minutes. Nevertheless,
this strategy had not been encountered before by any humans, as far as I know.
For 7 x (2n) boards a similar strategy was found, in case White does not
start the game in the middle column. In these cases Black can therefore at
least draw the game.
Furthermore, VICTOR needed only to check a few dozen positions to show
that Black can at least draw the game on the 7 x 4 board.
Evaluation of a position on a 7 x 4 or 7 x 6 board costs between 0.01 and 10
CPU seconds on a Sun4.
For the 7 x 6 board too many positions were unclear. For that reason a
combination of Conspiracy-Number Search and Depth First Search was used
to determine the game-theoretical value. This took several hundreds of hours
on a Sun4.
The main reason for the large amount of search needed, was the fact that in
many variations, the win for White was very difficult to achieve.
This caused many positions to be unclear for the evaluation function.
Using the results of the search, a database will be constructed
of roughly 500.000 positions with their game-theoretical value.
Using this datebase, VICTOR can play against humans or other programs,
winning all the time (playing White). The average move takes less
than a second of calculation (search in the database or evaluation
of the position by the evaluation function).
Some variations are given below (columns and rows are numbered as is customary
in chess):
1. d1, .. The only winning move.
After 1. .., a1 wins 2. e1. Other second moves for White has not been
checked yet.
After 1. .., b1 wins 2. f1. Other second moves for White has not been
checked yet.
After 1. .., c1 wins 2. f1. Only 2 g1 has not been checked yet. All other
second moves for White give Black at least a draw.
After 1. .., d2 wins 2. d3. All other second moves for White give black
at least a draw.
A nice example of the difficulty White has to win:
1. d1, d2
2. d3, d4
3. d5, b1
4. b2!
The first three moves for White are forced, while alternatives at the
fourth moves of White are not checked yet.
A variation which took much time to check and eventually turned out
to be at least a draw for Black, was:
1. d1, c1
2. c2?, .. f1 wins, while c2 does not.
2. .., c3 Only move which gives Black the draw.
3. c4, .. White's best chance.
3. .., g1!! Only 3 .., d2 has not been checked completely, while all
other third moves for Black have been shown to lose.
The project has been described in my 'doctoraalscriptie' (Master thesis)
which has been supervised by Prof.Dr H.J. van den Herik of the
Rijksuniversiteit Limburg (The Netherlands).
I will give more details if requested.
Victor Allis.
Vrije Universiteit van Amsterdam.
The Netherlands.
vic...@cs.vu.nl
------- End of Forwarded Messages
John Wilber
writes:
> A problem that I've been having, is how to recognize that peices are
>in a line (diagonal/horiz/vertical). Thanks.
Don't know how to help with any heuristics about placement of moves,
but for many games, the best way to determine if someone has x number
of pieces in a row is to use a "brute-force" type of algorithm (IMHO,
at least) that simply searches the playing field for all possible
combinations of "x in a row"- diagonally, horizontally, or vertically.
This should be pretty quick no matter what language you are using.
/***********************************************************************\
* John J. Wilber * "Im Himmel gibts kein Bier zum trinken wir *
* wil...@nunki.usc.edu * es hier" -German Proverb *
* Student, partier, beer * "In heaven there's no beer, so we might as *
* drinker, fun-loving guy. * well drink it here" -Translation *
*************************************************************************
* "I woke up this morning and I got myself a beer" -The Doors *
\***********************************************************************/
David A. Lyons
>In article <54...@ur-cc.UUCP> mek4...@uhura.cc.rochester.edu (Mark Kern)
>writes:
>> A problem that I've been having, is how to recognize that peices are
>>in a line (diagonal/horiz/vertical). Thanks.
>Don't know how to help with any heuristics about placement of moves,
>but for many games, the best way to determine if someone has x number
>of pieces in a row is to use a "brute-force" type of algorithm (IMHO,
I've done it brute-force in the past...but come to think of it, it would
be pretty neat to keep track of the row sizes in the board data structure,
something like this:
type
PieceType = (empty, red, black);
DirType = (horizontal, vertical, diag1, diag2);
Piece = record
kind: PieceType;
RowSize: array[DirType] of Integer;
end;
Board = array[1..7][1..6] of Piece;
For example, theBoard[3][4].RowSize[horizontal] would be the total number
of pieces of the same color extending to the left and right of that piece.
This way you can update the row counts on the fly (whenever a new piece is
added), without having to scan the whole board. Depending on what sort of
scoring function is being computed, you may be able to update it incrementally
too, instead of recomputing the whole thing.
A Delta array pre-filled with the dx and dy values needed to "move" in any
direction would be handy.