Rackin' up a game of Eight Ball

[thezip]

Howdy, pardners!

As I was shooting some pool this evening (8-ball, specifically), I stumbled upon what I think might be an interesting little programming diversion:

Given a standard set of fifteen pool balls and a triangular rack, write an algorithm in Perl that provides for the optimal placement of balls within this rack so that adjacency between solid and striped balls is minimized for a game of Eight Ball.

Note that the "one" ball and the "eight" ball must be placed in the standard positions:

        1
       . .
      . 8 .
     . . . .
    . . . . .

... and balls 1-7 are "solids" and 9-15 are "stripes". The 8-ball should be considered irrelevant for all adjacency pairings.</updated++>

Since everyone has their own way of rackin' 'em up, I'd like to see some real data that shows once-and-for-all which is the best WTDI.

More importantly, I'd like to see specific algorithms that solve this problem and that provide for the necessary statistical analysis.

Have fun!

<update>Minor text clarifications to improve readability (thanks to Lawliet and ysth)</update>

[McDarren]

"pool this evening (8-ball, specifically)"

That would be the American version of the game :)

There is of course another version of this game which is played in many countries, where there is no such thing as "stripes and solids". The balls are coloured red and yellow.

There is a standard method of racking the balls, commonly referred to as the "J" formation (note how the yellow balls form a letter "J").

This rack formation can also be applied to the numbered ball version of the game - and often is, I think.

Update: Here's an ascii-art representation of a standard rack setup for World Eight-Ball Pool...

    R
   Y R
  R B Y
 Y R Y R
R Y Y R Y

Note that the yellows and reds are interchangeable. That is, the "J" may be formed by either the reds or the yellows.

Cheers,
Darren :)

[kyle]

Here's my sort of quick and dirty...

Read more... (3 kB)

Here's the output:

        c
       s s
      c n c
     s s c s
    s c s c c

        1
       9 a
      2 8 3
     b c 4 d
    e 5 f 6 7

My rack is an array. I have a data structure to describe which elements are adjacent. With that, I wrote an assessment function to tell how many same-type balls are adjacent in a given rack. From there it's a matter of generating racks and massaging them into coherent output.

[telemachus]

I haven't had enough coffee yet to write an algorithm "that solve[s] this problem and that provide[s] for the necessary statistical analysis."

But in response to McDarren's comment about British rules, I found this site which specifies a more minimal set of American rules. (You have to love American sports organizations: that webpage's title is World Standardized Rules. Compare the saner "English Pool Association" from McDarren's link.)

However, in my experience, the standard in the US is one of two things: either it's utterly random, or it's very similar to the J-pattern McDarren mentions - except that you don't hook the J so perfectly by doubling inside the bottom row. Instead, you leave two of something (pretty much at random) adjacent in a bottom corner. Examples ('S' for solid and 's' for stripe):

    S            s
   s S          s S
  S 8 s        S 8 s  
 s S s S      s S s S
S s S s s    S s S s S

Most folks I know don't care if the 1-ball is uppermost, but the BCA website does include that specification. I'm not really sure why (other than "because it's the 1") since it has no significance in the game (unlike in 9-ball, where sequence matters and the 1-ball always goes at the top of the diamond).

A photo in the Wikipedia entry for eight-ball shows what I have in mind (without the 1-ball placed up top, though the image is supposed to show the World Standard rules).

Edit: thanks to ysth for pointing out that I had the wrong number of stripes and solids in my sad little examples. I'm going to blame that on the coffee deprivation.

[GrandFather]

TIMTOWTDI. A simple analysis demonstrates that there are multiple "optimal" solutions. The first row is dictated (it must contain the 1 ball). The second third and fourth rows are completely determined by choosing one of two alternatives for the second row. The last row has an odd number of balls, thus you can form a symmetrical pattern in that row giving four adjacent pairs of balls between the last two rows, or you can swap two balls of different stripe in the last row giving three adjacent pairs balls between rows and one adjacent pair within the last row.

Four equivalent solutions - very Perlish.