历史与文化

扑克有悠久的历史, 最早见于9世纪中国的唐朝(618-907). 打扑克有记载的最早文献之一是868年唐代诗人Su E记载的唐乙宗女儿同昌公主和她丈夫打牌[3]. 宋代文学家欧阳修认为扑克/纸牌的出现和书从卷轴到线装本的发展过程有关.

在欧洲, 扑克/纸牌的出现开始于14世纪末期. 最早的一种纸牌游戏叫做naib. 1430年左右, 意大利出现了tarot deck, 后来流传到欧洲各国. 现在常用到的法国纸牌体系出现于1480年的法国, 16世纪流行于英国, 并于之后流传到包括北美的各个英国殖民地. 

在日本, 一种流行的纸牌游戏hanafuda来源于16世纪的葡萄牙deck.

现在最常用的52张纸牌体系, 包括四种花色(club, diamond, heart, spade), 每种13张牌, 2-10AJQK, 称为Anglo-American deck.

纸牌游戏主要的特征包括: 牌手的数目和关系, 出牌方向, 由谁发牌, hands/rounds/games, 洗牌(shuffle), 发牌(deal), 及规则.

比较正式的作为运动的纸牌游戏是桥牌. 赌场有poker, blackjack. 现在中国民间有争上游, 千分, 拖拉机/双抠等热门打法. 电脑上总会提供叫Solitaire的纸牌游戏, Solitaire原指一种单人纸牌游戏. 

从纸牌游戏里还发展出一种寻找最长递增子序列(Longest Increasing Subsequence, LIS)的算法, 叫patience sort [7], 用binary search优化之后复杂度为O(nlog(n)).

以上介绍主要来自[3]. 更多细节见[1][2][3][4][5].



一些相关的词汇: 
一套牌可以称为Pack(UK English), Deck(US English), or Set(Universal). 一个牌手持有的牌叫做a hand. 牌面叫做the face/front of a card.

A deck of 52 playing cards in the French deck contains:
13 ranks: Ace, 2-10, Jack, Queen, King
4 (french) suits: Club, Diamond, Heart, Spade

可能有2张王: 2 Jokers.

A game of poker starts with shuffling of the playing cards.
The dealer then deals the cards to the playing hands.

如图[4]:


设计Poker

如何设计扑克(Poker)? 设计方法多种多样. 一般希望能体现出面向对象OOP的原则.

OOP设计:

首先需要关于牌本身的class: Card. 必要的性质包括value/rank, suit.
其次对于一副牌的class: Deck/Game. 必要的方法包括shuffle和deal. 此外可以包括记录(log), 评分(scoring), 判定输赢(win/lose)等方法.

可能涉及的design patterns包括observer, visitor, singleton等.

例如[6]:

// forward declarations
class Suit;
class Value;
class Card {
public:
   Card();
   Card(const Card& c);
   ~Card();
   Card& operator=(const Card& c);
   virtual Suit get_suit() = 0;
   virtual Value get_value() = 0;
private:
   Suit _suit;
   Value _value;
};
class QueenOfDiamonds : public Queen, public virtual Diamond { 
   // ...
};
class Deck {
   Deal(std::vector<Player>& p) {
      // some hair-brained visitor pattern
   }
   Shuffle() {
      // magic
   }
   // a singleton, nat&uuml;ralich
   // implementation and thread safety discussion for the reader
};
bool operator<(const Card& a, const Card& b) {
   // implementation details left up to the reader
}
//...


比较简单的非OOP设计[6]:

#define NCARDS 52
#define NSUITS 4
char values[] = "23456789TJQKA";
char suits[] = "cdhs";
char suit(int card) { return suits[card % NSUITS]; }
char value(int card) { return values[cards/NSUITS]; }

int deck [52];


洗牌算法

这里, 洗牌是个小有意思的问题. 最好的办法是Knuth的O(N)洗牌算法, 详见"The Art of Programming". C/C++实现如下:

void shuffle(vector<int> & A) {
    srand(time(NULL));
    for (int i = 52; i > 1; -- i) {
        swap(A[i-1], A[rand() % i]);
    }
}


也可以使用C++的标准函数: std::random_shuffle().

    // initialize
    vector<int> A(N);
    for (int i = 0; i < N; ++ i) A[i] = i + 1;

    int B[N];
    for (int i = 0; i < N; ++ i) B[i] = i + 1;

    // shuffle
    random_shuffle(A.begin(), A.end());
    random_shuffle(B, B+52); 

    // recover order
    sort(A.begin(), A.end());
    sort(B, B+52);


参考文献:
[1] Card game
[2] Poker
[3] Playing card
[4] Standard 52 card deck
[5] List of poker hands
[6] Design a deck of cards
[7] Patience sort

(本文来自homecox.com)