guessnum.cpp

猜数字游戏的小AI,有一定的准确程度,有兴趣的人可以

/*
* 文件名称: GuessNum.cpp
* 程序描述: 实现GuessNum类
* 编制日期: 2003-05-28
* 程序作者: realfun
* 联系方式: [e-mail]
*/
#pragma warning(disable:4786)

#include <iostream>
#include <algorithm>
#include <ctime>
#include <strstream>
#include <cmath>
#include "GuessNum.h"

const int GuessNum::m_base[5] = {0, 5, 9, 12, 14};

GuessNum::GuessNum()
{
	m_times = 0;

	//产生m_setAll
	unsigned int num=123;
	char a[10];
	while (num < 10000)
	{
		bool valid = true;	//表示数字没有重复
		sprintf(a, "%04u", num);
		for (int i=0; i<4; i++)
		{
			for (int j=i+1; j<4; j++)
				if (a[i]==a[j]) valid = false;
		}
		if (valid) m_setAll.push_back(a);
		num++;
	}//#while(num)
}//#GuessNum()

void GuessNum::Guess(void)
{
	//重置数据集
	m_setCurr.clear();
	list<string>::iterator itCopy = m_setAll.begin();
	while(itCopy != m_setAll.end())
		m_setCurr.push_back(*itCopy++);
	m_stack.clear();
	m_times = 0;

	//随机产生第一次猜测
	srand((unsigned)time(NULL));	//随机数种子
	bool valid = false;
	unsigned int iCode;
	while (!valid)
	{
		iCode = rand();
		while (iCode > 9999) iCode /= 10;
		char a[10];
		sprintf(a, "%04u", iCode);
		valid = true;
		for (int i=0; i<4; i++)
			for (int j=i+1; j<4; j++)
				if (a[i] == a[j]) valid = false;
		if (valid) m_lastGuess = a;
	}
	while (!GuessNext());

}//#Guess()

bool GuessNum::GuessNext(void)
{
	m_times++;
	//进行猜测，获取猜测结果
	string result;
	cout << "\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n";
	PrintStack();
	cout << "第 " << m_times << " 次猜测: " << m_lastGuess << endl;
	cout << "请输入结果[?A?B]:";
	bool valid = false;
	while (!valid)
	{
		cin >> result;
		//判断输入是否合法
		if (result.length() == 4 &&
			result[0] >= '0' && result[0] <= '4' &&
			result[2] >= '0' && result[2] <= '4' &&
			(result[0] + result[2]) <= ('0' + '4') &&
			toupper(result[1]) == 'A' && toupper(result[3]) == 'B')
		{
			valid = true;
		}
		if (!valid) cout << "输入不合法，请重新输入:";
	}//#while
	//将结果入栈
	strstream strm;
	strm << "第 " << m_times << "次: " << m_lastGuess << " -> " << result << endl;
	string strTemp;
	getline(strm, strTemp);
	m_stack.push_back(strTemp);
	if (result[0] != '4')
	{
		//尚未猜对, 进行数据集的约简
		list<string>::iterator itRemove;
		itRemove = m_setCurr.begin();
		while (itRemove != m_setCurr.end())
		{
			if (!ConfirmAB(m_lastGuess, *itRemove, result))
				itRemove = m_setCurr.erase(itRemove);
			else
				itRemove++;
		}

		//@@
		if (m_setCurr.size() == 0)
		{
			cerr << "你检查一下，肯定是哪一步输入错误！" << endl;
			cerr << "程序结束" << endl;
			exit(1);
		}else if (m_setCurr.size() == 1)
		{
			m_lastGuess = m_setCurr.front();
			return false;
		}

		//@@
		cout << "m_setAll.size() = " << m_setAll.size() << endl;
		cout << "m_setCurr.size() = " << m_setCurr.size() << endl;

		//产生下一个猜测数据
		double eMax = 0;	//max entropy, 最大信息量
		string strMax;		//提供最大信息量的那个数串
		list<string>::iterator itEn = m_setCurr.begin();
		//计算用每一个数来做区分时的信息量，取提供最大信息量的那个
		double eCurr = 0;
		int abList[15];	//从0a0b到4a0b共15种情况
		memset(abList, 0, 15 * sizeof(int)/sizeof(char));
		while (itEn != m_setCurr.end())
		{
			list<string>::iterator itTemp = m_setCurr.begin();
			while (itTemp != m_setCurr.end())
			{
				abList[GetABValue(*itEn, *itTemp)]++;
				itTemp++;
			}
			//统计熵

			//@@
//			cout << "sigh.." << *itEn << endl;

			double eTemp = 0;
			double eDiv = 0;
			for (int i=0; i<15; i++)
			{
				if (abList[i] != 0)	//避免0*log0
				{
					eDiv = double(abList[i]) / double(m_setCurr.size());
					eTemp += -eDiv * log(eDiv);
				}
			}
			if (eTemp > eMax)
			{
				cout << "here eMax = " << eMax << endl;
				eMax = eTemp;
				strMax = *itEn;
			}
			itEn++;
		}//#while(itEn)
		m_lastGuess = strMax;
		return false;
	}//#if(result[0] != 4)
	else// result[0] == 4
	{
		cout << "\n答案是: " << m_lastGuess << endl;
		cout << "一共用了 " << m_times << "次" << endl;
		PrintStack();
		return true;
	}
}//#GuessNext()

void GuessNum::PrintStack(void)
{
	for (int i=0; i<m_stack.size(); i++)
		cout << m_stack[i] << endl;
}//#PrintStack()

inline bool GuessNum::ConfirmAB(string first, string second, string ab)
{
	int a = 0, b = 0;
	for (int i=0; i<4; i++)
	{
		for (int j=0; j<4; j++)
			if (first[i] == second[j])
				if (i==j)	a++;
				else	b++;
	}
	if (ab[0] == char(a+'0') && ab[2] == char(b+'0'))
		return true;
	else
		return false;
}//#ConfirmAB()

inline int GuessNum::GetABValue(string first, string second)
{
	int a = 0;
	int b = 0;
	for (int i=0; i<4; i++)
	{
		for (int j=0; j<4; j++)
			if (first[i] == second[j])
				if (i==j)	a++;
				else	b++;
	}
	return m_base[a] + b;
}//#GetABValue()