I think that it may be interesting to add files to the chess board and make competition between programs when programs are practically forced to use selective search.
For example it is possible to have 10^15 files when most of the files are empty so programs will have to do selective search and even selective move generation(The computer has not enough memory to generate
almost 10^15 moves of Rook h1).
The opening position is going to be the same as the opening position in normal chess and the only difference from normal chess is having (10^15)-8 empty files right to the h file.
generalized chess(8*n for n>8) with empty files
Moderators: hgm, Rebel, chrisw
-
- Posts: 10282
- Joined: Thu Mar 09, 2006 12:37 am
- Location: Tel-Aviv Israel
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: generalized chess(8*n for n>8) with empty files
Some thoughts:
To manage 10^15 files would require to use a piece list as the only way of representing the board. Square IDs could be given by a 64 bit number of which the lowest (or highest) 3 bits represent the rank number (0..7) and the remaining bits represent the file number (about 0..10^15). The piece list could be organized such that you quickly find all pieces on a given rank, all on a given file and all of a given color + type, by adding some redundant data (a kind of indexing).
Move generation could be divided into horizontal moves of sliding pieces and all other moves:
- Horizontal slider moves could be represented using intervals, e.g.: piece A can move horizontally to the left from square [RANK,X] to all squares in the interval ( [RANK,X-1] ... [RANK,X-N] ).
- All other moves could be generated completely since there is no change w.r.t. standard chess for kings, knights, pawns, vertical moves and diagonal moves (of which there are 14 at most for each bishop or queen).
Therefore selectivity would have to be applied within the search regarding horizontal slider moves. It might be useful to determine an "interesting" set of horizontal moves somehow. That might be related to the closeness of target squares of those moves to friendly or enemy pieces. I could imagine that most rook or queen moves targeting to squares in the middle of a huge set of completely empty files are not significantly different from each other regarding their effect on the outcome of the game, as opposed to those few moves targeting to squares relatively close to any pieces. But that would be an assumption to be tested, of course.
In general I see only one major problem: a GUI like WinBoard would take a looooooong time to display the board
Sven
To manage 10^15 files would require to use a piece list as the only way of representing the board. Square IDs could be given by a 64 bit number of which the lowest (or highest) 3 bits represent the rank number (0..7) and the remaining bits represent the file number (about 0..10^15). The piece list could be organized such that you quickly find all pieces on a given rank, all on a given file and all of a given color + type, by adding some redundant data (a kind of indexing).
Move generation could be divided into horizontal moves of sliding pieces and all other moves:
- Horizontal slider moves could be represented using intervals, e.g.: piece A can move horizontally to the left from square [RANK,X] to all squares in the interval ( [RANK,X-1] ... [RANK,X-N] ).
- All other moves could be generated completely since there is no change w.r.t. standard chess for kings, knights, pawns, vertical moves and diagonal moves (of which there are 14 at most for each bishop or queen).
Therefore selectivity would have to be applied within the search regarding horizontal slider moves. It might be useful to determine an "interesting" set of horizontal moves somehow. That might be related to the closeness of target squares of those moves to friendly or enemy pieces. I could imagine that most rook or queen moves targeting to squares in the middle of a huge set of completely empty files are not significantly different from each other regarding their effect on the outcome of the game, as opposed to those few moves targeting to squares relatively close to any pieces. But that would be an assumption to be tested, of course.
In general I see only one major problem: a GUI like WinBoard would take a looooooong time to display the board
Sven
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: generalized chess(8*n for n>8) with empty files
Evaluation would be interesting, too. For instance, how to evaluate mobility? You would not want to count available rook or queen moves. But these pieces are clearly a lot stronger than usual in many cases, as opposed to bishops.
Pawns can never reach a file beyond file no. 14 ("n-file" - in theory, Ph2 could promote from m7 to n8 after 6 captures) so pieces beyond file no. 14 are always safe from being attacked by a pawn, which could make a difference in evaluation and also SEE.
Endgame theory could most probably be skipped for a while with such a board ...
Sven
Pawns can never reach a file beyond file no. 14 ("n-file" - in theory, Ph2 could promote from m7 to n8 after 6 captures) so pieces beyond file no. 14 are always safe from being attacked by a pawn, which could make a difference in evaluation and also SEE.
Endgame theory could most probably be skipped for a while with such a board ...
Sven
-
- Posts: 2929
- Joined: Sat Jan 22, 2011 12:42 am
- Location: NL
Re: generalized chess(8*n for n>8) with empty files
I don't think it's really interesting beyond N>24 or so, with the pieces centred on the board. This is about the action range of a pawn. Even then, I suspect it's not really interesting to follow what is happening far away from the king...Uri Blass wrote:I think that it may be interesting to add files to the chess board and make competition between programs when programs are practically forced to use selective search.
For example it is possible to have 10^15 files when most of the files are empty so programs will have to do selective search and even selective move generation(The computer has not enough memory to generate
almost 10^15 moves of Rook h1).
The opening position is going to be the same as the opening position in normal chess and the only difference from normal chess is having (10^15)-8 empty files right to the h file.
-
- Posts: 484
- Joined: Mon Mar 13, 2006 11:08 am
- Location: Klein-Gerau, Germany
Re: generalized chess(8*n for n>8) with empty files
There are a lot of 10x8 chess approaches. Already at a 10x8 board there are about 25% more moves each ply, which is of big impact to branching factors. In contrast to traditional 8x8 chess you often will find split battle fields and tactical challenges often starting before a finished development of all pieces. For 10x8 there already a GUI exists from H.G.Muller. It is hard for me to imagine that boards bigger than 10x8 could give any bigger challenge. Also Capablanca switched from 10x10 back to 10x8 boards after his experiments.
-
- Posts: 2929
- Joined: Sat Jan 22, 2011 12:42 am
- Location: NL
Re: generalized chess(8*n for n>8) with empty files
The addition of two major pieces (both of which can jump) helps with that, of course.smrf wrote:There are a lot of 10x8 chess approaches. Already at a 10x8 board there are about 25% more moves each ply, which is of big impact to branching factors. In contrast to traditional 8x8 chess you often will find split battle fields and tactical challenges often starting before a finished development of all pieces.
There are some 10x10 variants, but I haven't really spent enough time on them to judge how good they are compared to other variants. There's also Courier chess on 12x8, but that suffers from having a large array of worthless pieces (like the Ferz and Wazir).It is hard for me to imagine that boards bigger than 10x8 could give any bigger challenge. Also Capablanca switched from 10x10 back to 10x8 boards after his experiments.
-
- Posts: 27793
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: generalized chess(8*n for n>8) with empty files
I think the extra files wouldn't really add much to the game. If I were to write an engine for it, I would never make it move anything further than 7 files to the right of rightmost leaper itself, and when the opponent moves something more than 7 files to the right of that, assume it is on an unspecified file somewhere to the right, only accounting for the rank of the pieces there until they move back into the range of interest.
-
- Posts: 670
- Joined: Mon Dec 03, 2007 3:01 pm
- Location: Barcelona, Spain
Re: generalized chess(8*n for n>8) with empty files
I think most of the moves can be easily pruned as it is evident that they wouldn't add any additional value over certain other moves.
The real challenge however comes with making efficent use of the transposition table. Instead of using some piece/square encoding you would gain a lot by using some sort of piece/pattern approach.
The real challenge however comes with making efficent use of the transposition table. Instead of using some piece/square encoding you would gain a lot by using some sort of piece/pattern approach.