Possible to check for mate?

[asdfjkl]

Is it possible to somehow detect whether the current position is mate or stalemate? One way to check would be to see if the list of moves is empty (than one or the other would hold), and then to confirm whether or not the king is in check...

If not, that would be a really really helpful feature...

[cgearhart]

The Game() class doesn't include a function to test for check, checkmate, or stalemate because it is easily inferred from the board state in exactly the way you've described. Lines 205-231 in game.py already verify that the king is not in check before allowing moves, so you could use something similar to make a test function for now.

I'll try to add functions for check(), checkmate(), and stalemate() to the first major version release.

[asdfjkl]

I've added rudimentary (slightly ugly) functions for checkmate and stalemate (see https://github.com/asdfjkl/jerry/blob/master/root/main/Chessnut/game.py ) [all code is Python 3]

[cgearhart]

I don't mean to leave you hanging here. I've been working on a rewrite of the library for V1.0. It should vastly improve performance, and as a side benefit it would make implementing this functionality a lot easier. If you don't get the functionality you want from the rewrite I can branch this version and pull in your updates.

[asdfjkl]

You don't leave me hanging at all. As I said, the way I wrote those functions is ugly, and if you are already rewriting and possibly adding the functionality, then better not pull from me. Anyway, again thanks for the lib, it saved me a lot of work...

[cgearhart]

I've finished the bulk of the rewrite, so have a look at the graph branch. It is not well-tested yet, but it has some caching built in to improve speed and the Game.status property tracks check/checkmate/stalemate after every change; e.g.,

g = Game()
g.status == Game.NORMAL  # True
g.set_fen(<checkmate fen>)
g.status == Game.CHECKMATE  # True

The only other public method I changed is to remove the Game.reset() method. If you decide to try it, open an issue for any bugs you find and I'll try to fix them.

[tobimensch]

Hi cgearhart,

so what happened to the rewrite? :-)

This looks like the perfect simple chess validation python library, and I'm thinking about using it for a simple chess client I'm writing just for fun.

Now I'm confused, should I use the version in master, or should I try what you have so far in the rewrite branch.

Please don't give up on this. The genius of this library is its simplicity.

Greetings... Tobi

[cgearhart]

Tobi -

I haven't given up, just gotten distracted. I finished the initial rewrite and wasn't satisfied with how complicated it made things. I haven't had time to take another run at it yet.

I'll try to back port the requested feature to the main branch this week (maybe tonight).

You can use either branch. If stability is more important than speed you should use the main branch. If you hit a performance bottleneck you should try the rewrite. The main branch is fairly well tested (no crashes in several thousand games).

-Chris

[cgearhart]

Tobi -

Try the new feature branch: https://github.com/cgearhart/Chessnut/tree/feat_status

You can access the new status as a property on a Game instance:

from Chessnut import Game
g = Game()
assert(g.status == Game.NORMAL)  # succeeds

I haven't done enough testing to use this as an update to the master branch yet. Let me know if this works for you.

-Chris

[tobimensch]

Hi Chris,

in the meantime I've started my own approach at this just for fun. Maybe you could even use this to simplify chessnut.

My idea is this: Precalculate all possible positions a piece of any type can reach from any position. And also precalculate all paths that exist between any two positions (that includes only paths with at least 1 intermediate step, and not knights, since they can jump wherever they want).

I save all this in sets and hashes for very quick efficient access, essentially there's 0 calculations after the intitial load (which is also rather quick), and you could alternatively even store those tables precalculated in a file as python dicts/sets. The file size of all those precalculated tables is only around 30k. (currently about 22k, but I'm still working on the path calculations now)

With this approach, it's very simple to see if a piece can in theory reach a given position, ie. to see if a piece COULD be in check from it:

table = cc.get_table("rook","white) #gets precalculated table if "a2" in table["a4"]: return True #this will return true because a2 is a precalculated position for a4

now that you know a4 COULD reach a2 you can use the path method to get the precalculated path between a2 and a4 if there is any

print cc.path("a2","a4")

prints "a3"

now all you need to check is, if there's a piece already on "a3" or any of the other positions in the path.

assuming that you have a set with all positions of all pieces:

for pathpos in cc.path("a2","a4"): if pathpos in piecepositions: return "this path is blocked on:"+pathpos

It's a very simple efficient approach, which I believe could be easily extended to make a complete move validator, and ie. base ChessNut on.

I spend only 2-3hours with it, but it seems to work. Let me know what you think.

Greetings Tobi

2014-12-12 6:04 GMT+01:00 cgearhart notifications@github.com:

Tobi -

Try the new feature branch: https://github.com/cgearhart/Chessnut/tree/feat_status

You can access the new status as a property on a Game instance:

from Chessnut import Game g = Game() assert(g.status == Game.NORMAL) # succeeds

I haven't done enough testing to use this as an update to the master branch yet. Let me know if this works for you.

-Chris

— Reply to this email directly or view it on GitHub https://github.com/cgearhart/Chessnut/issues/4#issuecomment-66732796.

[cgearhart]

Thats what Chessnut does now - and one of the most popular ways to handle representing chess boards. Have a look at moves.py and Game._trace() for the details.

Moves.py calculates all possible moves for each piece type from any position on an empty chess board as a set of "rays" - the lines extending out in the 8 possible directions of movement. Game calls the moves function during initialization and caches the result - all future lookups are dict key resolutions.

The _trace() method moves out from an arbitrary starting point along the rays for the type of piece at that location to find the last reachable square (occupied squares may be blocked or capturable).

Calculating the moves isn't such a big deal, but caching the moves for every turn is impractical because the fanout factor for the game tree can be enormous. The graph branch accomplishes this using more sophisticated caching that only recomputes the legal moves that are affected by each move applied to the board, and storing the move cache as a set of diffs from the starting point.

The slow part of the master branch is that testing for move legality requires simulating the move and testing to see if the king is in check at the end of the move, which currently requires creating a new Game() object and recalculating the legal moves for every possible move in the current set (calculating the entire move tree to a depth of 2 from the current state) - and almost all of the moves in every case are the same.

I can probably speed it up a little by filtering the list of starting points that could possibly reach the king first, but it will still require recalculating all of those moves every time - and they will only ever differ by at most fewer than a couple hundred moves.

The feature branch I added last night includes rudimentary caching so that any call to _all_moves() persists until the game state changes - so it dramatically cuts back on recalculation of moves (especially useful because get_moves() must be called by the new status property) - so there is no penalty to calling get_moves() and status in the same turn.

-Chris

[tobimensch]

Okay, that's cool.

Do you think that ChessNut is going to support fischer random/360 eventually? I don't care a lot about other chess variants, but this one is really going to be very popular in the future I think, and I'd like to integrate it in my game, too.

Essentially only the board creation and the castling changes, I think, so that shouldn't be extremely hard to implement. :-)

Greetings Tobi

2014-12-12 15:09 GMT+01:00 cgearhart notifications@github.com:

Thats what Chessnut does now - and one of the most popular ways to handle representing chess boards. Have a look at moves.py and Game._trace() for the details.

Moves.py calculates all possible moves for each piece type from any position on an empty chess board as a set of "rays" - the lines extending out in the 8 possible directions of movement. Game calls the moves function during initialization and caches the result - all future lookups are dict key resolutions.

The _trace() method moves out from an arbitrary starting point along the rays for the type of piece at that location to find the last reachable square (occupied squares may be blocked or capturable).

Calculating the moves isn't such a big deal, but caching the moves for every turn is impractical because the fanout factor for the game tree can be enormous. The graph branch accomplishes this using more sophisticated caching that only recomputes the legal moves that are affected by each move applied to the board, and storing the move cache as a set of diffs from the starting point.

The slow part of the master branch is that testing for move legality requires simulating the move and testing to see if the king is in check at the end of the move, which currently requires creating a new Game() object and recalculating the legal moves for every possible move in the current set (calculating the entire move tree to a depth of 2 from the current state) - and almost all of the moves in every case are the same.

I can probably speed it up a little by filtering the list of starting points that could possibly reach the king first, but it will still require recalculating all of those moves every time - and they will only ever differ by at most fewer than a couple hundred moves.

The feature branch I added last night includes rudimentary caching so that any call to _all_moves() persists until the game state changes - so it dramatically cuts back on recalculation of moves (especially useful because get_moves() must be called by the new status property) - so there is no penalty to calling get_moves() and status in the same turn.

-Chris

— Reply to this email directly or view it on GitHub https://github.com/cgearhart/Chessnut/issues/4#issuecomment-66776507.

[cgearhart]

I've looked at it before and it should be pretty easy, but it's not my highest priority for developing this library right now. Feel free to open a separate issue as an enhancement and I'll try to sort out how much would have to change to support it.

[tobimensch]

Hi Chris,

so far it seems to work. I test for status == Game.CHECK and at least that works fine so far. Good work, I'd say you can commit this to master.

Greetings... Tobi

2014-12-12 6:04 GMT+01:00 cgearhart notifications@github.com:

Tobi -

Try the new feature branch: https://github.com/cgearhart/Chessnut/tree/feat_status

You can access the new status as a property on a Game instance:

from Chessnut import Game g = Game() assert(g.status == Game.NORMAL) # succeeds

I haven't done enough testing to use this as an update to the master branch yet. Let me know if this works for you.

-Chris

— Reply to this email directly or view it on GitHub https://github.com/cgearhart/Chessnut/issues/4#issuecomment-66732796.

[cgearhart]

Pulled into the main branch and new revision released on pypi.