[ProgClub list] ai-checkers in jj5-test

sanguinev at progsoc.org sanguinev at progsoc.org
Sun Oct 16 16:04:55 AEDT 2011


-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
 
On 16/10/2011 6:26 AM, John Elliot wrote:
> I've added a new project at ProgClub called 'jj5-test'. I haven't
created the project page on the wiki yet, but I will eventually. At the
moment the project is only in svn:
>
> http://www.progclub.org/pcrepo/jj5-test/trunk/
>
> The first 'test' project that I've started was inspired by a lecture
from the AI class:
>
> http://www.jj5.net/sixsigma/AI_class#Checkers
>
> Essentially a checkers board is shown, and I was curious as to whether
red (x) or white (o) could win (depending on who moves first). So I
intend to enumerate all possible games and see what the story is.
 
If you are interested in the state-space complexity for all the possible
moves then some comparison and information is here:
http://en.wikipedia.org/wiki/Game_complexity
 
Generally, enumerating the entire space of possible board positions, and
then moves is going to be difficult. On the other hand, the question
"could win" might make it very easy... I would approach this by
detecting states from which winning is impossible: i.e. every possible
sequence of moves leads to losing.
 
I guess it depends on how much freedom you are offering the players.
When you search for "could win", do you mean where the opponent is
actively trying to lose? Or is the question: can you force a win against
a perfect opponent (as the other extreme)?
 
>
> I have no idea if my approach is computationally feasible or not, and
I'm only about 20% of the way into a solution, but my code is in C and
available here if you're interested:
>
> http://www.progclub.org/pcrepo/jj5-test/trunk/ai-checkers/checkers.c?view=markup
>
> I accidentally started on this and have now been working on it all
night. I think that was a pretty big mistake given the homework for both
of the classes I'm enrolled in is due Monday morning, and I'm nowhere
near finished. Whoops. :P
 
I don't have time to read the code in detail (specially with limited
comments). Care to put a really simple summary of your algorithm here?
(E.g. depth first search on each possible set of moves by piece.)
 
>
> Now that the project is in svn I'll stop working on it, and pick it up
again later on when I have some spare time. If you're interested in
working on it for me, please be my guest. To do this you would just need
to use your ProgClub member login to checkout from the read-write
repository and then checkin your edits. The URL to checkout for the
project is:
>
> https://www.progclub.org/svn/pcrepo/jj5-test/trunk/ai-checkers/
>
> There are 'compile' and 'test' scripts in the project folder which show
how to compile and test the application.
>
I'm interested to see how the code pans out in the long run... and when
I have time to look. In the mean time I must resist the urge to try and
write my own code (probably in another language though). :P
 
- - SanguineV
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.10 (MingW32)
 
iQIcBAEBAgAGBQJOmmX2AAoJEI+NvFGSwhPnl+sP/1nY6YuzoittIX+g4I0erp2l
OXn1/QYxsHQjKJEBOYWri0Nu8HaQPOzu6oK2WbS3RoI8Bgr/qvpSPXGDdFfLpcQN
DceHLEk1JW0LrjhkCVLRjkJ9tWOf7OMNfagoIh97sJR/6wE1LOJzHs4oUk0aRRWM
jdo+O714VuxkEgN9bly96HMO64zxnjEXaIJ6sM6K3rdvX05Fz0UokNVn97AqtU2f
Bv19R3Nt+djVDVFqkzTD/+tXSJf8ST35e351/DG4ISw1zbMNoA3M9z7cK05Ea2na
xe3kM/2cr5YzDE43jfm96LOsFBHZt2D5Ymnt0pPHngdV4vPNEKW+xlx3c5jafxtb
KAYwxg+W9AribE6YZfsH6G6ACucy8KENpiXUfM2U0ai267Nft8r/JpDxc7XF4diq
dPkNu8P/wGFtz7EVgRdomAaxjnPcSetjWVcf6XadcR2gmXwGOMSJSQtgeQsspyD9
rxGa8uTHgXKXHYydPAWmwv9sMe4Okmhk7/RyV70HJV0IaxEcUedaDWciw5ZymCSs
WFQ5CnWg8gCBkphMj2eM6MeqCYaxR5ctseGG/d2nfYPOJaacQcrJJqw9cSUd9KWY
+B2uzPFmvmh8Jxv5Wnv5w245oYAQblRiav4goAMS4z/G83GLgtsJaE7p2dS/PfXy
pRpOrP9CiZMc7aLn78UI
=aAct
-----END PGP SIGNATURE-----



More information about the list mailing list