前言
大二感觉真的特别水，第一次感觉到自己啥都不会，同时啥也不愿意学，整个人和一个废人差不多，博客也没怎么更新（说到底还是太懒，下面都是替自己找个借口）这次的训练题实际算是半个月之前就已经做完，上个星期排出成绩，最近又是信号报告，数学建模上机报告，数据结构课程设计报告，搞得天天特别狼狈，而且这次的题最后的模拟退火算法也没有实现，感觉能力还是欠缺了很多吧，算法真的很重要。
至于博客也不是神马论文，很多地方也不用那么文绉绉的吧，当然格式也不可能那么的规范。
我们队的思路可能比较简单，而且效果不算是很好，希望各位大佬能够给指点一下。
问题
问题重述
UNO的wiki
“UNO是一种趣味性比较强的游戏，它基于颜色和数字不断的轮流出牌，并含有各种功能牌（大部分带有惩罚的性质），最终出完或者剩余牌计分最低的赢得比赛。
牌的类型
普通牌
有红，黄，蓝，绿四种颜色，每种颜色都有
0号牌1张
1-9号牌两张
共计76张
功能牌
有红，黄，蓝，绿四种颜色，每种颜色都有
阻挡牌（skip）2张
反转牌（reverse）2张
罚两张（draw tow）2张
共计24张
万能牌
可以当作任意颜色的牌打出，分两种：
变色牌（wild）4张
王牌（wild four）4张
共计8张
游戏玩法
初始时有n位玩家，每个人从洗过的牌中分别取出7张牌，并假设假设一个初始的游戏方向。
首先n个人先来决定谁是庄家,然后取牌堆最上面的一张牌，即为手牌，出牌的原则：
庄家必须出一张和牌堆最上面的一张牌面值或者功能一样的或者颜色一样的牌，出牌后，如果为非功能牌或者万能牌，到下一个玩家出牌；如果是功能牌或者万能牌就按照牌的功能进行操作，如果没有则从牌堆摸一张牌，重复上面的操作。如果还没有则跳到下一个玩家。
下一个玩家重复上一个玩家的操作。
如果牌堆无牌或者一位玩家所有牌出完则结束，每个人手里剩下的牌来进行计分，打完手上牌者记0分，普通牌按面值计分，功能牌计20分，万能牌计50分，得分少的玩家获胜。
功能牌和万能牌
| 阻挡牌(skip) | 下一个玩家不能出牌 |
| 反转牌(reverse) | 改变游戏的方向 |
| 罚两张(draw two) | 下一个玩家不能出牌并且从牌堆中抽2张牌 |
| 变色牌(wild) | 发牌者可以随意指定下一个玩家出牌的颜色。该牌可以在任何时候打出。如果该牌是首牌，则由庄家的上一个玩家任意指定出牌颜色。 |
| 王牌(wild four) | 牌者可以随意指定下一个玩家出牌的颜色。同时下位玩者停止出牌一次，并罚抽4张牌。该牌智能在手上没有符合的数字或颜色牌时才能发出。 |
所求问题
通过建立多种自动出牌的模型，使其胜率尽可能高
吐槽一下，我看题第一眼感觉这是在搞Alphago吗，我要搞出来还做啥数模(笑哭)，直接去谷歌工作就行了
问题分析
这道题我感觉第一个难点就是怎么去把规则制定下来，以及通过合理的假设将问题简单化。说实话，这个规则真的太灵活了，100局能有100局的玩法，于是花了很长时间把这个规则以及后面的假设，后期随着设计也不停地改进和完善。
题目的要求是进行模拟自动游戏，使玩家的胜率尽可能的多。实际影响一个玩家胜率的因素主要在两个方面，一是运气等偶然因素，这些因素是不可抗拒的，也不在我们的考虑方面内，同时也告诉我们要进行多组测试，一组测试偶然性太大。另一个就是玩家的出牌策略，也就是我们建模的核心，玩家自动出牌模型，一个好的自动出牌模型可以让玩家的胜率大大提升。
这个问题可以看做一个求全局最优解的问题。而关于自动出牌模型，最简单的模型像游戏托管一样出牌，只是根据上一家的手牌和自己现有的手牌进行出牌，不进行任何的优化。这种模型显然是低效率的。但是我们可以通过贪心算法对模型进行优化，同时可以通过引入多个影响因素来优化模型，使该自动出牌模型的效率更高。
简单假设
- 假设游戏开始是都是以正向为开始方向
- 游戏的玩家遵守游戏规则，如wild four只在无牌可出时才出，只剩一张牌时自动喊出”UNO”等
- 不考虑有符合规则的牌不出的情况
- 在指定出牌颜色是一个随机的过程，不受其他因素的影响
- 不存在一次出牌打出多张牌的情况，即同时打出一对颜色、面值相同的牌或者多张功能牌的情况
- 如果面对当前的牌下家无法做出回应，跳过该玩家后下一个玩家仍需要对这张牌做出回应，直到有玩家对该张做出回应
- 罚2（draw two）或王牌(wild four)的效果可以有累加,例如假设游戏方向为正方向，当玩家1出draw two,玩家2页有draw two并且打出，玩家3没有draw two，那么玩家3会跳过出牌，并且被罚从牌堆中摸4张牌。
- 游戏庄家为初始手牌分数最高的玩家
数据表示
牌
对于牌的数据我们可以使用一个类来表示，一个类中包括两种数据类型，加上判断类型的函数
颜色
可用枚举类型red, yellow, blue, green, blank表示, 注意变色牌blank可适用于任意颜色.
牌的分值
普通牌直接面值就是数字, 后续的数字:
- 10表示阻挡牌（skip）
- 11表示反转牌（reverse）
- 12表示罚两张（draw two）
- 13表示变色牌（wild）
- 14表示王牌（wild four）
牌堆
牌堆我们可以用一个栈来表示，栈顶元素来表示牌堆中上面的一张牌，通过出栈操作来实现发牌。刚开始用一个list双向链表来存储牌，然后利用random函数将其中的元素无重复的取出，然后将元素入栈，重复该过程来实现洗牌。
玩家
玩家可以定义一个基本类player，用list来存储该用户手中的牌，定义出牌，判断上一张是不是draw two或者wild four，是否追加使用draw two或者wild four以及出牌规则等虚函数。下面的各个模型作为player的子类继承玩家类的几个方法并且进行重写。同时设计一个可以手动出牌的玩家，方便进行测试，同时侧面显示模型的好坏。
游戏过程
玩家可以定义一个基本类player，用list来存储该用户手中的牌，定义出牌，判断上一张是不是draw two或者wild four，是否追加使用draw two或者wild four以及出牌规则等虚函数。下面的各个模型作为player的子类继承玩家类的几个方法并且进行重写。
模型
模型一
普通模型
初始有n位玩家, 每人从混洗之后的牌中分别取出7张牌，开始进行游戏。
如果当前的颜色为C面值为K的情况，下一个玩家的出牌策略：
- 1.如果当前有K面值(1-12均可)的牌, 按照该玩家取牌的先后次序出一张K面值的牌；
- 2.如果当前没有K面值的牌, 则从C颜色中按照该玩家取牌的先后次序出一张牌(出完普通牌才能出功能牌)；
- 3.如果颜色和面值都不符合则出万能牌；
- 4.无牌可出则从牌堆中取出牌，重复1~3过程一次；
- 5.如果仍然无牌可出，则跳到下一个玩家。
模型二
这种模型是根据第一种的托管模型进行了爬山算法优化，由于UNO是一种积分的游戏，为了尽可能的赢牌，我们可以优先的将大分值的牌优先打出，小分值的牌后打出。也就是我们尽可能的取当前的最优解，而不在意全局情况，尽可能的通过局部最优解来获得全局最优解。
初始有n位玩家, 每人从混洗之后的牌中分别取出7张牌，开始进行游戏。
如果当前的颜色为C面值为K的情况，下一个玩家的出牌策略：
1. 如果有变色牌先出变色牌；
2. 如果有符合要求的功能牌则出功能牌；
3. 如果当前有K面值或者C颜色牌，那么就尽可能的取面值较大的牌；
4. 无牌可出时则出王牌，否则从牌堆中取出牌，重复1~3过程一次；
5. 如果依然无牌可出，则跳到下一个玩家。
模型三
在爬山算法模型中，用局部最优解去逼近全局最优解，但也发现很多的时候求解会陷入到局部最优解，无法跳出，影响获得全局最优解。因此我们可以通过模拟退火算法来接受一个比当前解要差的解，有可能会跳出这个局部的最优解，达到全局的最优解
初始有n位玩家, 每人从混洗之后的牌中分别取出7张牌，开始进行游戏。
如果当前的颜色为C面值为K的情况，下一个玩家的出牌策略：
1.定义一个flag=false;
while(!flag) {
//如果有变色牌，调用接受函数
if(出变色牌) {
flag = true;
break;
}
//如果有符合要求的功能牌，调用接受函数
if(出功能牌) {
flag = true;
break;
}
//如果有K面值或者C颜色牌，选出面值较大的牌，调用接受函数
if(出牌) {
flag = true;
break;
}
//无牌可出时则出王牌，调用接受函数
if(出王牌) {
flag = true;
break;
}
if(第一次执行)
//从牌堆中取出牌
}
//跳到下一个玩家核心思想：
1.产生一条新的出牌策略P(i+1)，计算出牌策略P(i+1)的权值L( P(i+1) )
2.若L(P(i+1)) < L(P(i))，则接受P(i+1)为新的出牌，否则以模拟模拟退火的那个概率接受P(i+1) ，然后降温
3.重复步骤1，2直到满足退出条件
实现代码
最后是关于以上几种模型假设的C++代码实现
#include <iostream>
#include <stdio.h>
#include <queue>
#include <stack>
#include <list>
#include <string>
#include <memory>
#include <time.h>
#include <set>
#include <cmath>
#ifdef _WIN32
# include <Windows.h>
#endif
using namespace std;
enum card_color { red = 1, yellow = 2, blue = 3, green = 4, blank = 0 };
#define CV_BLOCK 10
#define CV_REVERSE 11
#define CV_DRAWTWO 12
#define CV_WILD4 14
class card {
public:
card_color color;
int value;
int uniq_id;
static int uniq_seq;
static card nil() {
return card(blank, 0);
}
card(card_color c, int val)
: color(c), value(val), uniq_id(uniq_seq++) {}
card(const card &c)
: color(c.color), value(c.value), uniq_id(c.uniq_id) {}
card &operator=(const card &c) {
color = c.color;
value = c.value;
uniq_id = c.uniq_id;
return *this;
}
bool is_nil() const {
return color == blank && value == 0;
}
bool operator==(const card &c) const {
return uniq_id == c.uniq_id;
}
bool is_value_card() const {
return value >= 0 && value <= 12;
}
std::string to_string() const {
if(is_nil())
return string("[ ]");
else if(value == 14)
return string("[ 王 牌 ]");
else if(value == 13)
return string("[ 变 色 ]");
else {
char buf[16];
sprintf(buf, "[%s %s]", color_name(), value_name());
return string(buf);
}
}
int score() const {
if(value <= 9)
return 10;
else if(value <= 12)
return 20;
else if(value <= 14)
return 50;
else
return 0;
}
int color_value() const {
if(value == 14 || (value == 13 && color == blank))
return 13;
switch(color) {
case red: return 12;
case yellow: return 14;
case blue: return 9;
case green: return 10;
default: return 7;
}
}
bool next_can_be(card &c) {
if(is_nil())
return true;
if(!is_value_card())
return true;
if(!c.is_value_card())
return true;
return c.color == color || c.value == value;
}
const char *color_name() const {
switch(color) {
case red: return "红";
case yellow: return "黄";
case blue: return "蓝";
case green: return "绿";
default: return "";
}
}
protected:
const char *value_name() const {
switch(value) {
case 0: return "0 号";
case 1: return "1 号";
case 2: return "2 号";
case 3: return "3 号";
case 4: return "4 号";
case 5: return "5 号";
case 6: return "6 号";
case 7: return "7 号";
case 8: return "8 号";
case 9: return "9 号";
case CV_BLOCK: return "阻挡";
case CV_REVERSE: return "反转";
case CV_DRAWTWO: return "罚二";
default: return " ";
}
}
};
class player {
public:
list<card> cards;
string name;
player(const string &n) : name(n) {}
player(const char *n) : name(n) {}
player(const player &p) : name(p.name), cards(p.cards) {}
virtual void pick_cards(stack<card> &c) {
for(int i = 0; i < 7; i++) {
cards.push_back(c.top());
c.pop();
}
}
virtual card put_card(card ¤t) = 0;
virtual bool has_drawtwo(card_color color) {
for(auto it = cards.begin(); it != cards.end(); it++)
if(it->color == color && it->value == CV_DRAWTWO)
return true;
return false;
}
virtual bool has_wildfour() {
for(auto it = cards.begin(); it != cards.end(); it++)
if(it->value == CV_WILD4)
return true;
return false;
}
virtual void draw_cards(stack<card> &c, int n) {
for(int i = 0; i < n; i++) {
cards.push_back(c.top());
c.pop();
}
}
virtual int score() {
int s = 0;
for(auto it = cards.begin(); it != cards.end(); it++)
s += it->score();
return s;
}
virtual ~player() {}
};
#define ITERATE_ALL_CARDS \
for(auto it = cards.begin(); it != cards.end(); it++)
#define PUT_CARD { card selection = *it; \
cards.remove(*it); \
return selection; }
class primary_player : public player {
public:
primary_player() : player("primary") {}
virtual card put_card(card ¤t) {
if(current.is_nil()) {
card c = cards.front();
cards.pop_front();
return c;
}
// 如果当前有K面值(1-12均可)的牌,
//按照该玩家取牌的先后次序出一张K面值的牌
if(current.is_value_card()) {
ITERATE_ALL_CARDS {
if(it->is_value_card() && it->value == current.value)
PUT_CARD;
}
}
// 如果当前没有K面值的牌,
//则从C颜色中按照该玩家取牌的先后次序出一张牌
ITERATE_ALL_CARDS {
if(it->color == current.color && it->value <= 9)
PUT_CARD;
}
// 出完非功能牌才能出功能牌
ITERATE_ALL_CARDS {
if(it->color == current.color) PUT_CARD;
}
// 如果颜色和面值都不符合则出万能牌
ITERATE_ALL_CARDS {
if(it->value == 13 || it->value == 14) {
card selection = *it;
cards.remove(*it);
if(selection.value == 13)
selection.color =
card_color((rand() % 4) + 1);
return selection;
}
}
// 无牌可出则从牌堆中取出牌
return card::nil();
}
};
class greedy_player : public player {
public:
greedy_player() : player("Greedy") {}
virtual card put_card(card ¤t) {
if(current.is_nil()) {
card c = cards.front();
cards.pop_front();
return c;
}
ITERATE_ALL_CARDS {
if(it->color == current.color &&
it->value > 9 && it->value < 13) {
PUT_CARD;
}
}
card tmp = *cards.begin();
// 如果当前有K面值(1-12均可)的牌,
//按照该玩家取牌的先后次序出一张K面值的牌
if(current.is_value_card()) {
//ITERATE_ALL_CARDS {
ITERATE_ALL_CARDS {
if(it->value == current.value) {
if(tmp.value > it->value) {
tmp = *it;
}
}
}
}
// 如果当前没有K面值的牌,
//则从C颜色中按照该玩家取牌的先后次序出一张牌
//ITERATE_ALL_CARDS {
ITERATE_ALL_CARDS {
if(it->color == current.color && it->value <= 9) {
if(tmp.value > it->value) {
tmp = *it;
}
}
}
card selection = tmp;
cards.remove(tmp);
return selection;
ITERATE_ALL_CARDS {
if(tmp.value == it->value && tmp.color == it->color) {
PUT_CARD;
}
}
// 如果颜色和面值都不符合则出万能牌
//ITERATE_ALL_CARDS {
for(list<card>::iterator it;it != cards.end(); it++) {
if(it->value == 13 || it->value == 14) {
card selection = *it;
cards.remove(*it);
if(selection.value == 13)
selection.color =
card_color((rand() % 4) + 1);
return selection;
}
}
// 无牌可出则从牌堆中取出牌
return card::nil();
}
};
class Anneal_player : public player {
public:
Anneal_player() : player("Anneal") {}
bool Accept(int step){
if(step <= 0) return true;
return rand() <= exp((step)) * RAND_MAX;
}
virtual card put_card(card ¤t) {
int step = 1;
if(current.is_nil() && Accept(step++)) {
card c = cards.front();
cards.pop_front();
return c;
}
if(Accept(step++)) {
ITERATE_ALL_CARDS {
if(it->color == current.color &&
it->value > 9 && it->value < 13) {
PUT_CARD;
}
}
}
card tmp = *cards.begin();
// 如果当前有K面值(1-12均可)的牌,
//按照该玩家取牌的先后次序出一张K面值的牌
if(current.is_value_card() && Accept(step++)) {
//ITERATE_ALL_CARDS {
ITERATE_ALL_CARDS {
if(it->value == current.value) {
if(tmp.value > it->value) {
tmp = *it;
}
}
}
}
// 如果当前没有K面值的牌, 则从C颜色中按照该玩家取牌的先后次序出一张牌
//ITERATE_ALL_CARDS {
if(Accept(step++)) {
ITERATE_ALL_CARDS {
if(it->color == current.color && it->value <= 9) {
if(tmp.value > it->value) {
tmp = *it;
}
}
}
}
card selection = tmp;
cards.remove(tmp);
return selection;
if(Accept(step++)) {
ITERATE_ALL_CARDS {
if(tmp.value == it->value && tmp.color == it->color) {
PUT_CARD;
}
}
}
// 如果颜色和面值都不符合则出万能牌
//ITERATE_ALL_CARDS {
if(Accept(step++)) {
for(list<card>::iterator it;it != cards.end(); it++) {
if(it->value == 13 || it->value == 14) {
card selection = *it;
cards.remove(*it);
if(selection.value == 13)
selection.color = card_color((rand() % 4) + 1);
return selection;
}
}
}
// 无牌可出则从牌堆中取出牌
return card::nil();
}
};
class manual_player : public player {
public:
manual_player() : player("User") {}
virtual card put_card(card ¤t) {
int i = 1;
cout<<endl<<"您当前手里有 "<<cards.size()
<<" 张牌。其中这些牌可以出："<<endl;
for(auto it = cards.begin(); it != cards.end(); it++) {
if(current.next_can_be(*it)) {
cout<<" "<<i<<": ";
#ifdef _WIN32
HANDLE hCon = GetStdHandle(STD_OUTPUT_HANDLE);
SetConsoleTextAttribute(hCon, it->color_value());
cout<<it->to_string()<<"\t";
SetConsoleTextAttribute(hCon, 7);
#else
cout<<it->to_string()<<"\t";
#endif
}
i++;
}
while(1) {
cout<<endl<<"请输入想要出的牌的编号(0=使用牌堆)：";
cin>>i;
if(i == 0) return card::nil();
i--;
ITERATE_ALL_CARDS {
if(i-- == 0) {
if(current.next_can_be(*it)) {
card c = *it;
cards.remove(*it);
if(c.value == 13) {
cout<<"您选择了一张变色牌，请指定颜色（1234=红黄蓝绿）：";
cin>>i;
c.color = card_color(i);
}
cout<<endl;
return c;
}
break;
}
}
cout<<"输入无效！请重试 ..."<<endl;
cin.clear();
}
}
};
#define PLAYER_COUNT 2
class game {
public:
stack<card> cards;
int current, direction;
card last_card;
shared_ptr<player> players[PLAYER_COUNT];
game(int seed) : direction(1), current(0), last_card(card::nil()) {
list<card> allcards;
add_color_cards(allcards, red);
add_color_cards(allcards, yellow);
add_color_cards(allcards, blue);
add_color_cards(allcards, green);
for(int i = 0; i < 4; i++) {
allcards.push_back(card(blank, 13));
allcards.push_back(card(blank, 14));
}
srand(seed);
while(allcards.size() > 0) {
int i = rand() % allcards.size();
for(auto it = allcards.begin(); it != allcards.end(); it++) {
if(i-- == 0) {
cards.push(*it);
allcards.remove(*it);
break;
}
}
}
}
void setup_player(int i, shared_ptr<player> p) {
players[i] = p;
players[i]->pick_cards(cards);
}
void setup_player(int i, player *p) {
setup_player(i, shared_ptr<player>(p));
}
void increment_current() {
current += direction;
if(current >= PLAYER_COUNT)
current %= PLAYER_COUNT;
else if(current < 0)
current += PLAYER_COUNT;
}
void step() {
last_card = players[current]->put_card(last_card);
if(last_card.is_nil() && cards.size() > 0) {
last_card = cards.top();
cards.pop();
cout<<" * 玩家 "<<current<<" <"<<players[current]->name
<<"> 正从牌堆抽牌"<<endl;
}
#ifdef _WIN32
HANDLE hCon = GetStdHandle(STD_OUTPUT_HANDLE);
char title[256];
SetConsoleTextAttribute(hCon, 0xf);
cout<<" * 玩家 "<<current<<" <"<<players[current]->name<<"> 出牌 - ";
SetConsoleTextAttribute(hCon, last_card.color_value());
cout<<last_card.to_string()<<endl;
SetConsoleTextAttribute(hCon, 7);
sprintf(title, "UNO - 牌堆剩余 %d 张", cards.size());
SetConsoleTitleA(title);
#else
cout<<" * 玩家 "<<current<<" <"<<players[current]->name<<"> 出牌 - "
<<last_card.to_string()<<endl;
#endif
// TODO: 根据玩家当前出牌进行惩罚
if(last_card.value == CV_REVERSE)
direction = -direction;
increment_current();
if(last_card.value == CV_BLOCK || (PLAYER_COUNT == 2 &&
last_card.value == CV_REVERSE))
increment_current();
else if(last_card.value == CV_DRAWTWO) {
int draw_card_count = 2;
while(players[current]->has_drawtwo(last_card.color)) {
draw_card_count += 2;
increment_current();
}
cout<<" * 玩家 "<<current<<" <"<<players[current]->name<<"> 被罚抽 "
<<draw_card_count<<" 张牌"<<endl;
players[current]->draw_cards(cards, draw_card_count);
increment_current();
}
else if(last_card.value == CV_WILD4) {
int draw_card_count = 4;
while(players[current]->has_wildfour()) {
draw_card_count += 4;
increment_current();
}
cout<<" * 玩家 "<<current<<" <"<<players[current]->name<<"> 被罚抽 "
<<draw_card_count<<" 张牌"<<endl;
players[current]->draw_cards(cards, draw_card_count);
increment_current();
}
}
bool over() {
for(int i = 0; i < PLAYER_COUNT; i++)
if(players[i]->cards.size() == 0)
return true;
return cards.size() == 0;
}
protected:
game(const game &g) : last_card(g.last_card) {}
static void add_color_cards(list<card> &allcards, card_color color)
{
allcards.push_back(card(color, 0));
for(int i = 1; i <= 12; i++) {
allcards.push_back(card(color, i));
allcards.push_back(card(color, i));
}
}
};
int card::uniq_seq = 0;
int main()
{
int cnt_1 = 0;
int cnt_2 = 0;
int cnt_3 = 0;
for(int k = 0;k < 1000;k++) {
game g((unsigned int)time(NULL));
g.setup_player(0, new primary_player());
//g.setup_player(1, new manual_player());
//g.setup_player(1, new greedy_player());
g.setup_player(1, new Anneal_player());
while(!g.over()) g.step();
cout<<endl<<" 玩家名称 分数"<<endl;
cout<<" +--------------+----------+"<<endl;
for(int i = 0; i < PLAYER_COUNT; i++) {
printf(" | %12s | %8d |\n", g.players[i]->name.c_str(), g.players[i]->score());
}
cout<<" +--------------+----------+"<<endl;
if(!g.players[0]->score()) {
cnt_1++;
} else if(!g.players[1]->score()) {
cnt_2++;
}
}
cout << cnt_1 << " " << cnt_2 << endl;
#ifdef _WIN32
system("PAUSE");
#endif
return 0;
}