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:

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

Replies are listed 'Best First'.
Re: Status of HAKMEM proposed programs?
by ariels (Curate) on Mar 13, 2002 at 07:51 UTC

    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!
[reply]

      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

[reply]
        "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.

[reply]
        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.
[reply]
      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.

[reply]
[reply]

Back to Meditations