# [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
along.

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