Connect 4 evaluation function
Chaitanya
I have to make a implement connect 4 in JAVA as a course project.I
used standard alpha beta and minimax algos and a simple but good
evaluation function. My code came to about 700 lines excluding the
gui. The problem for me is that i need to submit code of at least 2500
lines for the project. I cant figure out a good and long evaluation
function for the purpose. somebody please help me.
Chaitanya
ps- Please dont refer me to the thesis of L.Victor Allis. I've been
through it about 4 times but i find it unimplementable.
G Winstanley
overfloweth with the following:
How about adding extra code to the alpha-beta as well. Perhaps you could try
NegaScout?
Stan
Jan-Eric Duden
Iterative Deepening. This shoudn't be too hard and will give you good
results if your evaluation function is good. :)
Eric
"G Winstanley" <g.wins...@virgin.net> wrote in message
news:o4lqtt4idecubbp3k...@4ax.com...
James Gideon
> You could also check out (Alpha-Beta or Nega-Scout) with Moveordering and
> Iterative Deepening. This shoudn't be too hard and will give you good
> results if your evaluation function is good. :)
>
You forgot to mention transposition tables :).
James Gideon
Or even MTD(f). Takes some effort to get working though and you'd
need a hash table.
Linares
There are a lot of choices to implemente a *perfect* connect-4 player.
Whether you should
use one 2-plyr search algorithm or other depends upon various features.
One of them is,
obviously, the accuracy of the evaluation function (with a perfect
evaluation function, even
a Minimax ---brute-force--- search algorithm at depth 1 would give
you always the
right answer). If the evaluation function is not that good, alpha-beta
is well known to
propagate an error (at least, theoretically, as long as D.F.Beal has
shown in his PhD that
nobody has proved why Alpha-beta is that useful it is in practice).
MTD(f), by Aske Plaat, as suggested by James Gideon is a nice choice.
It can go faster (specially
if you use a hash table as suggested), and the nicest thing of all
is that using different
drivers you can emulate different 2-plyr search algorithms like Alpha-Beta,
SSS*, DUAL*, etc.
Besides, while making a decision about what is the right search algorithm
to use, you should
consider as well what are going to be the enhancements you will use
(hash tables, killer heuristic,
transposition tables, etc.). Regarding this, I strongly suggest you
to read a paper written by
Jonathan Schaeffer et al. where they introduce the generalization idea
(I do not remember the
whole title right now, but almost sure you will find the paper at the
Jonathan Schaeffer personal
home page at Alberta). Regarding using tables to save exploring some
subtrees, I reccomend
you all reading the PhD by Dennis Breuker.
Anyway, if I would be about to code a connect-4 plyr, I would have no
doubt. Excuse me, but
I have to refer Allis' work. However, do not read his PhD, maybe
ideas are not as much detailed
as they are in a paper Dr. Allis wrote for the Games Championship helded
in London, 1989, I
think. And, believe me, ... his idea, which consists of using 9 strategic
rules is very easily
implementable.
Regards,
-- Carlos Linares Lopez Ground Systems Engineering Division Payload Data Segment ESRIN - European Space Agency 00044 Frascati Italy +39 06 94 180 527
Tony Werten
extension as well.
Tony
"Chaitanya" <cmi...@iitk.ac.in> wrote in message
news:df8970b7.01102...@posting.google.com...