Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Computations Using Playing Cards

  1. Jul 13, 2016 #1
    EXPLORING THE POSSIBILITY OF PERFORMING COMPUTATIONS WITH PLAYING CARDS

    I was listening to an interview with John Conway yesterday and the conversation turned to his "Game of Life". Conway mentioned that Life can be configured in such a way that it can perform arbitrary computations. This got me thinking about what other seemingly inanimate things can be given a sense of "Life" to and made to behave like automata that could potentially be used to perform computations.

    In the same interview, Conway also spoke about a card game he played with his old professor, Besicovitch. I grabbed a deck of cards and made a few google searches to find rules for "Besicovitch's Game" but soon got distracted when I realised I'd just picked up a very good candidate for an automaton. The potential for such a system is intriguing: imagine playing a physical card game against an AI deck.

    The first thing I decided to try was to devise a sorting algorithm, it seems to me that if a deck of cards can be automatically sorted into arbitrary, discrete configurations then computation should possible.

    I set up a few basic rules for my algorithm to ensure the human component was simply following instructions and not influencing the sorting process. I decided to restrict myself to a "blind" sorting algorithm: the next action only being influenced by the previous card dealt. If I didn't specify this restriction I could have just looked at each card as it was dealt and sorted by eye, which is not interesting.

    I spent a good few hours performing some very odd and largely useless operations on the cards, because I had no idea what might have a useful effect and what wouldn't. Eventually I hit upon an algorithm that worked! (Well, there is a single case where it does not work but that's good enough for a proof of concept in my eyes.)

    I challenge you all to devise a sorting algorithm that works better than mine.


    HOW CAN REGULAR PLAYING CARDS BE "SELF-SORTED"?

    A curious challenge! Devise an algorithm to automatically sort a deck of cards (or into suits or divide by colour) with the following limitations:

    + Starting with a thoroughly shuffled deck, your algorithm must sort by colour/suit/value or any combination of these.
    + Your algorithm must display negative entropy, that is, it tends towards a sorted state, and once sorted does not tend to disorder.
    + You may split the deck into multiple decks if you wish.
    + You may deal the cards face-up into one or more piles.
    + You must determine where a card is to be dealt BEFORE dealing it; you must not relocate cards after they have been dealt.
    + You may count the number of cards split or dealt.
    + To provide logic to your algorithm, you may use two types of input to trigger conditional operations: the colour/suit/value of the previously dealt card, and the depletion of a deck.


    EXAMPLE SOLUTION TO SORT A DECK BY COLOUR (using two suits)
    (unfortunately doesn't work if bottom card is red)

    1. Split the deck exactly in half to create left and right decks.
    2. If this is the first iteration, the starting deck is the left deck.
    3. Deal a card from the starting deck face up into the central pile.
    4. If the previous card dealt was red, deal a card from the left deck as before, else deal a card from the right deck.
    5. Repeat the previous step until one of the decks has been depleated.
    6. If only the left deck remains, turn over the central pile and place the left deck on top of it. The left deck is the starting deck.
    7. If only the right deck remains, turn over the central pile and place it on top of the right deck. The right deck is the starting deck.
    8. Repeat the first step.
     
  2. jcsd
  3. Jul 13, 2016 #2

    jedishrfu

    Staff: Mentor

    Welcome to PF!

    What are you expecting from this site?

    We are a group of volunteers who help students with questions from mainstream STEM subjects. We don't discuss speculative science topics or personal theories here.

    Are you expecting us to peer review your original work?
     
  4. Jul 13, 2016 #3
  5. Jul 13, 2016 #4

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    Horribly inefficient, but working: Reserve space for 104 piles, they are later picked up in that order (e. g. the bottom card of pile 1 becomes the bottom card of the final combined stack). Deal the first card on pile 2. If it is not the first card in your sorting order, deal all remaining cards on pile 1. If it is the first card, deal the next card on pile 4. If it is not the second card in your sorting order, deal all remaining cards on pile 3. If it is the second card, deal the next card on pile 6, and so on.

    If your pile is sorted, you get your cards on all even piles in the right order. If a card doesn't fit to the sorting order, it is moved to the back while the first N sorted cards stay sorted.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted