[ProgClub list] ai-checkers in jj5-test

John Elliot jj5 at progclub.org
Sun Oct 16 18:10:03 AEDT 2011

On 16/10/2011 4:04 PM, sanguinev at progsoc.org wrote:
> 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

OK, thanks. Checked out the URL but didn't really understand their 
approach to measurement.

> 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 don't understand how that is different to enumerating the entire space 
of possible games. But yes, that's what I'm trying to find.

> 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)?

Yeah, I was thinking "can you force a win against a perfect opponent?"

In one scenario it's white's move, and in another scenarios it's red's 
move, and for each scenario is it possible for either player to force a win?

The other question that I raised was: is the board in a legal state? 
I.e. could the current configuration have been reached by a valid game? 
I suspect that it is, but haven't proved it.

> 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.)

I haven't got that far along in my simulation. At the moment I'm just 
trying to get the basic "move enumeration" facility to work, i.e. to 
have the game know what are valid future states given whose move it is. 
This is hard because "jumps" are "forced" and "continuous" (i.e. if you 
can jump a piece you have to jump it, but if you can jump two pieces you 
can choose which to jump, and if you jump a piece and then can make more 
jumps then you have to keep jumping).

I had planned on a depth first search with cycle detection. Not entirely 
sure how I will handle a cycle, but know that I intend to detect a cycle 
by keeping a history of antecedent board states (i.e. the moves that 
lead to the current position). If a cyclic state is detected there is no 
need to continue the depth-first search through that state, as it is 
already being searched further up the tree.

> 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

I think C was a bad language to pick. I have buffer overflows in my 
code, and I'm not planning to fix them. My data structure for my board 
state uses at least 2x (or up to ~5x) more space than necessary, and 
consequently takes more time than necessary too. I haven't actually 
broached the sticky issue of memory management yet -- I'm not that far 

I did actually give my choice of language a heart-wrung five minutes 
worth of thought before I started, and landed on C because I'm still 
trying to learn more about that language. C#, JavaScript, Python and 
Lisp were the other languages I considered, probably listed here in 
order of preference.

If there are any developments on my game simulation I'll let you know. I 
hope that if you pick up this problem you will do the same!

More information about the list mailing list