I've learned something new

[rjgibert]

I was looking up a number of topics related to hill climbing algorithms and stumbled across this:

http://en.wikipedia.org/wiki/Bidirectional_search

Bidrectional search is O(b^(d/2)). Does this mean that for 2 player games where the number of goal states is finite (this excludes chess), alphabeta in combination with bidirectional search can in general solve such games in O(b^(d/4))? Surely, this is too good to be true.

The fly in the ointment is if alpha beta cannot be applied in reverse from a goal state. I find this a bit confusing to think about. So my question is, can alphabeta be applied in reverse from a goal state? What would be a clear explanation for why it is not possible?

[Vinvin]

For information, this Sokoban solver : http://codecola.net/sps/sps.htm work with Bidrectional search.

[bob]

I was looking up a number of topics related to hill climbing algorithms and stumbled across this:

http://en.wikipedia.org/wiki/Bidirectional_search

Bidrectional search is O(b^(d/2)). Does this mean that for 2 player games where the number of goal states is finite (this excludes chess), alphabeta in combination with bidirectional search can in general solve such games in O(b^(d/4))? Surely, this is too good to be true.

The fly in the ointment is if alpha beta cannot be applied in reverse from a goal state. I find this a bit confusing to think about. So my question is, can alphabeta be applied in reverse from a goal state? What would be a clear explanation for why it is not possible?

Isn't this exactly what Schaeffer did for checkers? Searching from the front of the game to hit endgame tables, which are constructed starting at the end of the game and working backward. If you just study that idea in a pure geometrical sense, which has the most area. (a) a triangle of height H (where the vertex is at the root, and the base represents the breadth of the full tree) or (b) two triangles of height H/2, where one vertex is at the top, the other is at the bottom, and the two bases are adjacent?

That's the idea that led to solving checkers, otherwise it would still be an impossible task to search from the initial position to a forced win/lose/draw along every path...

The problem with this (particularly with respect to chess) is that the area of the two triangles is about 1/2 the size of the single triangle, but that is still an enormous area...

[wgarvin]

I was looking up a number of topics related to hill climbing algorithms and stumbled across this:

http://en.wikipedia.org/wiki/Bidirectional_search

Bidrectional search is O(b^(d/2)). Does this mean that for 2 player games where the number of goal states is finite (this excludes chess), alphabeta in combination with bidirectional search can in general solve such games in O(b^(d/4))? Surely, this is too good to be true.

The fly in the ointment is if alpha beta cannot be applied in reverse from a goal state. I find this a bit confusing to think about. So my question is, can alphabeta be applied in reverse from a goal state? What would be a clear explanation for why it is not possible?

Isn't this exactly what Schaeffer did for checkers? Searching from the front of the game to hit endgame tables, which are constructed starting at the end of the game and working backward. If you just study that idea in a pure geometrical sense, which has the most area. (a) a triangle of height H (where the vertex is at the root, and the base represents the breadth of the full tree) or (b) two triangles of height H/2, where one vertex is at the top, the other is at the bottom, and the two bases are adjacent?

That's the idea that led to solving checkers, otherwise it would still be an impossible task to search from the initial position to a forced win/lose/draw along every path...

The problem with this (particularly with respect to chess) is that the area of the two triangles is about 1/2 the size of the single triangle, but that is still an enormous area...

[Edit: actually I think they were not "Searching from the front of the game to hit endgame tables"... they had three phases. Endgame tables, backward search (or GTV proving) from the endgame table positions to middlegame positions, and forward search from early positions to the middlegame positions. They probably switched back and forth between forward and backward search so they could target the searches towards the same set of middlegame positions once they had figured out which middlegame positions would be most useful to have proved. I can't remember the details but I'm sure they're on the Internet somewhere.]

The cryptography guys call this sort of thing a "time-memory trade-off". The "memory" part of it comes in along that tallest line between the two triangles... or perhaps at a (large!) set of interesting positions scattered around in the two triangles, but (probably) mostly clustered around that tallest line. After you prove something about the GTV of a middlegame position using a backward search, you have to store it somewhere.

Now since the branching factor for checkers is around 10 and the branching factor for chess is around 35... this was way more practical for checkers than it is for chess. I remember reading somewhere that once they had 8-piece databases for Chinook, it was able to hit some tablebase positions in its forward search *from the initial position*. We're never ever going to be able to do that for chess!

I think in chess, you would also not get much benefit from a giant database of positions with proved GTVs. Put another way: Maybe you could prove things about a bunch of positions that occur around 6 to 10 plies before a tablebase position is reached? But how useful would that really be... for the huge amount of storage it would require, your forward search would be able to see a W/L/D result maybe 6 to 10 moves earlier than it could see it with tablebases anyways.

It probably makes more sense to try and figure out how to more efficiently represent the knowledge that is captured in tablebases. I keep waiting for someone to invent a clever way of accurately representing 90% of the positions of 5- and 6-man tablebases using an order of magnitude less space than current bitbases. When we can fit accurate info for most 6-man endings in RAM, I'll be seriously impressed.