An idea: PotChess

[sje]

PotChess is the name of a set of chess-like games. The name comes from "power of two chess"; PotChess(n) is a chess-like game played on a square board with 2^n squares on a side.

PotChess(3) is very much like orthodox chess, except:

1) No double square pawn advance, so no en passant.
2) No underpromotion.
3) No castling.
4) Repeating a position just once is an immediate draw.

PotChess(n + 1) is like PotChess(n), except:

1) Twice the edge length and so four times the total number of squares.
2) Initial pawn placement moved one rank towards the middle of the board.
3) Home rank men are doubled via lateral duplication except each king gets another queen to the queen side.
4) The squares vacated by the pawns are filled with men cloned form those on the prior rank, excet that the king get gets yet another queen if needed.

So, for PotChess(4), there are 256 squares, 96 men, and White's first three ranks look like:

Code: Select all

PPPPPPPPPPPPPPPP
RRNNBBQQQQBBNNRR
RRNNBBQQQKBBNNRR

For PotChess(5), there are 1,024 squares, 256 men, and Black's first four ranks look like:

Code: Select all

RRRRNNNNBBBBQQQQQQQKBBBBNNNNRRRR
RRRRNNNNBBBBQQQQQQQQBBBBNNNNRRRR
RRRRNNNNBBBBQQQQQQQQBBBBNNNNRRRR
PPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP

For PotChess(8), there are 65,536 squares and 3,584 men.

Why all of this foolishness? The idea is do re-invigorate computer chess research by advancing the computational complexity of the game beyond what can be handled using the old and tired techniques on current hardware.

[Don]

PotChess is the name of a set of chess-like games. The name comes from "power of two chess"; PotChess(n) is a chess-like game played on a square board with 2^n squares on a side.

PotChess(3) is very much like orthodox chess, except:

1) No double square pawn advance, so no en passant.
2) No underpromotion.
3) No castling.
4) Repeating a position just once is an immediate draw.

PotChess(n + 1) is like PotChess(n), except:

1) Twice the edge length and so four times the total number of squares.
2) Initial pawn placement moved one rank towards the middle of the board.
3) Home rank men are doubled via lateral duplication except each king gets another queen to the queen side.
4) The squares vacated by the pawns are filled with men cloned form those on the prior rank, excet that the king get gets yet another queen if needed.

So, for PotChess(4), there are 256 squares, 96 men, and White's first three ranks look like:

Code: Select all

PPPPPPPPPPPPPPPP
RRNNBBQQQQBBNNRR
RRNNBBQQQKBBNNRR

For PotChess(5), there are 1,024 squares, 256 men, and Black's first four ranks look like:

Code: Select all

RRRRNNNNBBBBQQQQQQQKBBBBNNNNRRRR
RRRRNNNNBBBBQQQQQQQQBBBBNNNNRRRR
RRRRNNNNBBBBQQQQQQQQBBBBNNNNRRRR
PPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP

For PotChess(8), there are 65,536 squares and 3,584 men.

Why all of this foolishness? The idea is do re-invigorate computer chess research by advancing the computational complexity of the game beyond what can be handled using the old and tired techniques on current hardware.

There are other games which do that too. Go is one of them, however the big news is that go programs over the past decade have gotten much stronger and are succumbing to a different set of tired techniques. Another game is Arimaa, played on an 8x8 with chess pieces but not much like chess and not easy for computers.

Today's AI is tomorrows boring "tired" techniques but it's hard to argue with success. Increasing the branching factor has the effect of making it harder for a computer to play the game well but I'm not sure it makes the game more interesting as an AI target. Go has been considered a much better AI target due to the enormous branching factor compared to chess but strangely enough the reason for so much recent progress has been the addition of global search. Back to square one if that is what you are trying to avoid.

[Uri Blass]

PotChess is the name of a set of chess-like games. The name comes from "power of two chess"; PotChess(n) is a chess-like game played on a square board with 2^n squares on a side.

PotChess(3) is very much like orthodox chess, except:

1) No double square pawn advance, so no en passant.
2) No underpromotion.
3) No castling.
4) Repeating a position just once is an immediate draw.

PotChess(n + 1) is like PotChess(n), except:

1) Twice the edge length and so four times the total number of squares.
2) Initial pawn placement moved one rank towards the middle of the board.
3) Home rank men are doubled via lateral duplication except each king gets another queen to the queen side.
4) The squares vacated by the pawns are filled with men cloned form those on the prior rank, excet that the king get gets yet another queen if needed.

So, for PotChess(4), there are 256 squares, 96 men, and White's first three ranks look like:

Code: Select all

PPPPPPPPPPPPPPPP
RRNNBBQQQQBBNNRR
RRNNBBQQQKBBNNRR

For PotChess(5), there are 1,024 squares, 256 men, and Black's first four ranks look like:

Code: Select all

RRRRNNNNBBBBQQQQQQQKBBBBNNNNRRRR
RRRRNNNNBBBBQQQQQQQQBBBBNNNNRRRR
RRRRNNNNBBBBQQQQQQQQBBBBNNNNRRRR
PPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP

For PotChess(8), there are 65,536 squares and 3,584 men.

Why all of this foolishness? The idea is do re-invigorate computer chess research by advancing the computational complexity of the game beyond what can be handled using the old and tired techniques on current hardware.

There are other games which do that too. Go is one of them, however the big news is that go programs over the past decade have gotten much stronger and are succumbing to a different set of tired techniques. Another game is Arimaa, played on an 8x8 with chess pieces but not much like chess and not easy for computers.

Today's AI is tomorrows boring "tired" techniques but it's hard to argue with success. Increasing the branching factor has the effect of making it harder for a computer to play the game well but I'm not sure it makes the game more interesting as an AI target. Go has been considered a much better AI target due to the enormous branching factor compared to chess but strangely enough the reason for so much recent progress has been the addition of global search. Back to square one if that is what you are trying to avoid.

I do not find it strange that the global search help go programs.
The strange thing for me is to read that only now people added global search.

I also read that the main problem with go is not the branching factor but to have a good evaluation function that is clearly easier in PotChess because you have a simple factor like material.

[hgm]

Bad idea. PotChess(3) is already an almost unplayable and exceedingly boaring game that drags on forever. Because of the large number of pieces, the huge separation of the armies make it a very slow game.

On chessvariants.org someone recently presented the umptieth Chess variant, and IMO complety ridiculed his own game by ending the description with "in stead of a 50-move rule, a 500-move rule should be applied". This sounds like a game just like that.

If you want a Chess-like game where proven Chess techniques do not work well, try Shogi.

[kbhearn]

I'm not sure material really would be such a simple evaluation for potchess(5) as described. 23 queens and 48 of every other piece on the board for each side sounds more like a constant search for mating attacks with a material deficit being a relatively minor term.

That said, optimising a computer to play any specific game is a completely different target than developing "true" AI, and thus seeking a new game to advance the field of AI is irrelevant. In the case of potchess, by the time you're getting to n >= 5 (and maybe even n=4) you'll have come up with methods to deal with using the ridiculous amount of material and branching factor, the incredible slowness of pawns having to cross a massive board, etc, and probably will easily scale to higher n. What's more the optimum 'methods' will probably be simple predefined heuristics as opposed to any sort of learning on the part of the machine.

If you're looking to demonstrate AI, it seems more appropriate to look at a generalised game player capable of dealing with not just simple x by y grid deterministic turn based games but abstract game boards (hex grids, maps, paths, etc), incomplete information, auction mechanics, random events, and possibly real-time out of sequence play. It should be able to formulate plausible strategies by being supplied a copy of the rules, and refine on them through play.

[Daniel Shawul]

With the rules you gave, Nebiyu can already play it. Nonetheless the game offers nothing more than other existing big chess variants can't do. Bigger board size chesses are evaluated / searched same damn way using min-max and regular eval, absolutely useless to AI. IMO those variants that can offer something are:

a) multi-player chess . Add one more player who is not in collaboaration with other players and you have yourself a complex game whose out come depends on collaboration aspects. This has important contributions in economics f.i
b) games of incomplete information: simultaneous moves , some covered squares as in dark chess etc introduce probablistic aspects like in poker. Again this has a wider application.
c) games that can offer local analysis (local combats) while played on a bigger board. I can't think of a variant now, but Go is one example.
etc..

The recent google AI challenge Ants was far more interesting. It has all the above aspects and played on a big map of (200x200) so computers would never ever be able to brute force search it in a trillion years. Also it doesn't matter if they could, since it is incomplete information game. Bigger is not an answer.

[Uri Blass]

Bad idea. PotChess(3) is already an almost unplayable and exceedingly boaring game that drags on forever. Because of the large number of pieces, the huge separation of the armies make it a very slow game.

On chessvariants.org someone recently presented the umptieth Chess variant, and IMO complety ridiculed his own game by ending the description with "in stead of a 50-move rule, a 500-move rule should be applied". This sounds like a game just like that.

If you want a Chess-like game where proven Chess techniques do not work well, try Shogi.

I guess that you mean PotChess(5) because PotChess(3) is very similiar to chess except some moves that are not alllowed.

With the right time limit(blitz with no increasement) the game is not going to drag forever and playing many moves may be a problem for humans who play but no problem for engines.

[Jose Carlos]

I like the idea, and the suggestions by others. Here's my suggestion: random forbidden squares, I mean, squares that can't be occupied by any piece. This idea is meant to enforce the strategic understanding because there'll be some squares that will be more important, some strong points whose control can give a positional advantage, which is hard to quantify in advance by the programmer.

[Daniel Shawul]

If you're looking to demonstrate AI, it seems more appropriate to look at a generalised game player capable of dealing with not just simple x by y grid deterministic turn based games but abstract game boards (hex grids, maps, paths, etc), incomplete information, auction mechanics, random events, and possibly real-time out of sequence play. It should be able to formulate plausible strategies by being supplied a copy of the rules, and refine on them through play.

Absolutely. There is such endeavour at stanford http://games.stanford.edu/ .
The games are provided at runtime in prolog like language. You have to analyze the rules, pick suitable search/evaluation strategies, learn from the games etc .. all at run time. Ofcourse any pre-programmed domain specific knowledge is going to win any time but that has limited applications. They have a GUI for visualizing the state space,replaying actions , creating games etc... If one has to research on a certain aspect of AI, it is better make modifications that exagerate that aspect rather than making things bigger.

[Don]

PotChess is the name of a set of chess-like games. The name comes from "power of two chess"; PotChess(n) is a chess-like game played on a square board with 2^n squares on a side.

PotChess(3) is very much like orthodox chess, except:

1) No double square pawn advance, so no en passant.
2) No underpromotion.
3) No castling.
4) Repeating a position just once is an immediate draw.

PotChess(n + 1) is like PotChess(n), except:

1) Twice the edge length and so four times the total number of squares.
2) Initial pawn placement moved one rank towards the middle of the board.
3) Home rank men are doubled via lateral duplication except each king gets another queen to the queen side.
4) The squares vacated by the pawns are filled with men cloned form those on the prior rank, excet that the king get gets yet another queen if needed.

So, for PotChess(4), there are 256 squares, 96 men, and White's first three ranks look like:

Code: Select all

PPPPPPPPPPPPPPPP
RRNNBBQQQQBBNNRR
RRNNBBQQQKBBNNRR

For PotChess(5), there are 1,024 squares, 256 men, and Black's first four ranks look like:

Code: Select all

RRRRNNNNBBBBQQQQQQQKBBBBNNNNRRRR
RRRRNNNNBBBBQQQQQQQQBBBBNNNNRRRR
RRRRNNNNBBBBQQQQQQQQBBBBNNNNRRRR
PPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP

For PotChess(8), there are 65,536 squares and 3,584 men.

Why all of this foolishness? The idea is do re-invigorate computer chess research by advancing the computational complexity of the game beyond what can be handled using the old and tired techniques on current hardware.

There are other games which do that too. Go is one of them, however the big news is that go programs over the past decade have gotten much stronger and are succumbing to a different set of tired techniques. Another game is Arimaa, played on an 8x8 with chess pieces but not much like chess and not easy for computers.

Today's AI is tomorrows boring "tired" techniques but it's hard to argue with success. Increasing the branching factor has the effect of making it harder for a computer to play the game well but I'm not sure it makes the game more interesting as an AI target. Go has been considered a much better AI target due to the enormous branching factor compared to chess but strangely enough the reason for so much recent progress has been the addition of global search. Back to square one if that is what you are trying to avoid.

I do not find it strange that the global search help go programs.
The strange thing for me is to read that only now people added global search.

I also read that the main problem with go is not the branching factor but to have a good evaluation function that is clearly easier in PotChess because you have a simple factor like material.

The standard alpha beta search in Go was not particularly effective, but the breakthrough came with Monte Carlo Tree Search. Playing games at random (or at least semi-random with some heuristic guidance) and using the win statistics turned out to be a better evaluation function than anyone could come up with otherwise and the search was best first, using statistics to determine which node to expand and very highly selective. The search is not explicitly mini-maxed but the effect is the same.