Status of HAKMEM proposed programs?

[patgas]

I came across this node today: Struggling for puzzles and projects?, in which larsen shares a link to http://www.inwap.com/pdp10/hbaker/hakmem/hakmem.html, the HAKMEM document from MIT. A lot (nearly all of it) is over my head, but there is a page about proposed computer programs. I thought the problem of finding the smallest squared square was interesting, and started researching it. Of course, since that HAKMEM memo is now 30 years old, the smallest possible squared square has been well-documented. So now I'm wondering which, if any, of the other problems have been solved too.

Here's a quick list of the problems, in case one sparks a memory:

• 77: Count polyominos to order 20.
• 78: Solve minichess.
• 79: Solve the tiger sliding-block puzzle.
• 80: Find the smallest squared square.
• 81: Count the magic squares of order 5.
• 82: Count the semigroups of 7 elements, and the groups of 256 elements.
• 83: Compute the integer-valued step function F(R), 0<R<1, the number of circles of radius R which fit into a unit circle.
• 84: Solve pentominos on an 8x8 checkerboard.
• 85: Dissections.
• 86: Find the number of domino coverings for various objects.
• 87: Analyze giveaway chess.
• 88: Analyze escalation chess.
• 89: Prove the pawns win in "4 Pawns."
• 90: Solve Teeko.
• 91: Solve Five-in-a-row on an infinite board.
• 92: Solve Tic-Tac-Toe on a 4x4x4 board.
• 93: Solve Checkers.
• 94: Solve Hex on large boards.
• 95: Solve Chess.
• 96: Solve Go.

Update: Added a few strikethroughs. I'll keep adding them as I discover which problems have been solved.

"As information travels faster in the modern age, as our days are crawling by so slowly." -- DCFC

[ariels]

AFAIK:

• #77, #94, #95, #96 are still wide open.
• #93 is open, although Chinook played an excellent game of checkers.
• #91 was solved! Victor Allis' Ph.D. thesis has a chapter on this ("Go-Moku"). Note that Black's advantage in Go-Moku is considered huge, so in a sense this was unsurprising. What is surprising is that Allis managed to do it!

[patgas]

Well maybe you can help clear something up for me, since I'm not too familiar with game theory. What exactly does it mean to "solve chess?" Does that mean to find a winning solution for say, white, given any board layout?

"As information travels faster in the modern age, as our days are crawling by so slowly." -- DCFC

[dragonchild]

"Solving" a game means to be able to state an algorithm by which the best move in any situation can be determined, solely by looking at the board (and possibly the moves that have happened already). For example, there is a very simple algorithm that solves Tic-Tac-Toe.

------
We are the carpenters and bricklayers of the Information Age.

Don't go borrowing trouble. For programmers, this means Worry only about what you need to implement.

[danichka]

To put it another way chess would be solved if we knew what conclusion best play from the position would reach. Whether it be a win for white, a win for black, or a draw. We would also know the fastest way to reach that conclusion for the winning side and the longest way to hold that conclusion off for the losing side.

Some endgames have already been solved. All 3 piece and all 4 piece endgames for example. Some of these are really not relevant however, because they are so lopsided it was rather useless to solve. If you want to play around with some of these EGTB visit Robert Hyatt's site.

[dragonchild]

Could someone describe what a polyomino is?

------
We are the carpenters and bricklayers of the Information Age.

Don't go borrowing trouble. For programmers, this means Worry only about what you need to implement.

[belg4mit]

polyomino

--
perl -pe "s/\b;([st])/'\1/mg"