一种策略游戏 - 第2页 - 难题征解 - 数学研发论坛

hujunhua 发表于 2012-4-12 12:02:37

规则规定归零的手关闭（既不予取，也不许入）是必要的，否则游戏不会有胜负。

hujunhua 发表于 2012-4-12 13:03:25

局面的合并与过滤

本帖最后由 hujunhua 于 2012-4-13 07:13 编辑

一个局面 M 完整的表达可用$((a,b),(c,d))$, 其中(a,b),(c,d)都是无序对。定义$M*k:=((a*k, b*k),(c*k, d*k))$, *是四则运算符。

合并法则：M×k等价于M，当gcd(k,N)=1时。
过滤法则：若从$((1,1),(1,1))$开始博弈，那么M×k可以从全体局面集中滤掉，当gcd(k,N)>1。

1~9中任意意都可以乘以适当的k变成1，2，5之一，所以不妨让a限于1，2，5而b,c,d取1~9中适当的值。

如此一来，7#的内容可以简化为：当两人手中都有一数归零（mod10）后，就只有16种局面，而且不存在策略了。这16种局面不难划分出胜负和。红色为先胜局面（7个），黑色为先负局面（6个）：{11} → {12} → {23} → {15} →{52} →{27} → {17} → {14} → {25} → {51} → {16} → {29} →{19} → {10}, 判和的局面共3个，形成一个循环{1, 3} → {1, 8} → {2, 1} → {1,3}

056254628 发表于 2012-4-12 16:16:41

我觉得程序不能判断胜负和的局面应该也是构成循环，因此也是属于和的局面。
这样的话大部分局面都属于和。1111也是其中的一个。

hujunhua 发表于 2012-4-12 21:48:45

我觉得程序不能判断胜负和的局面应该也是构成循环，因此也是属于和的局面。
这样的话大部分局面都属于和。1111也是其中的一个。
056254628 发表于 2012-4-12 16:16 http://bbs.emath.ac.cn/images/common/back.gif
楼主这话是否暗示有非循环和局？

056254628 发表于 2012-4-12 23:49:34

14# hujunhua
误会我的意思了。
我的程序是这样的。
f(a,b,c,d)的值表示胜负和。 (a<=b,c<=d)
0 表示负，1表示和，2表示胜。
x表示未知，可能是0，可能是1，也可能是2.
其中f(0,b,0,d)值，已经知道,分别是0、1、2.

对于其他的f(a,b,c,d)初始都是x
接着对所有的a、b、c、d运行以下程序：
(a,b,c,d)有四种变化，（a、c中有1个0，变化减少2个。）
(a1,b1,a,b),(a2,b2,a,b),(a3,b3,a,b),(a4,b4,a,b) 我的表示法是先手的数字放后面
具体判断如下：
这四种局面的f值中：
*如果没有x，那么f(a,b,c,d)=2-min(f(a1,b1,a,b),f(a2,b2,a,b),f(a3,b3,a,b),f(a4,b4,a,b))
*如果有x，那么只要有一个0，f(a,b,c,d)=2
*有x，没有0，那么f(a,b,c,d)=x (即f值没有变化)
-------------------------------------------------------------------------
这样，对所有的a、b、c、d每循环上述程序一次，f值等于x的局面个数就会减少。
一直到f值等于x的局面个数不变为止。
按照我的设想，所有的局面最后都会归结于(0,b,0,d)局面，f值等于x的局面个数最后归0，这样所有的局面都有最终的结果，或胜或负或和。
但实际上不是如此，f值等于x的局面个数最后稳定在2000以上。
所以我才说大多数局面无法得到确切的结果。
想想原因可能是这样的：f(a,b,c,d)的值取决于其他局面的值，其他局面的值取决于......，最后又取决于前面出现过的局面的值，这样就形成了循环，双方为了不形成必胜局面给对方，谁都不愿意从循环局面中离开，所以这些局面都是和局。

056254628 发表于 2012-4-13 00:13:27

对于f(a,b,c,d)=2-min(f(a1,b1,a,b),f(a2,b2,a,b),f(a3,b3,a,b),f(a4,b4,a,b))
f(a1,b1,a,b),f(a2,b2,a,b),f(a3,b3,a,b),f(a4,b4,a,b)中有x,没0的情况：
可以简化，把所有值为2的删除，最后剩下的都是值为1，或x。
选择值为1的变化，就保证和局，选择为x的变化，比如f(a1,b1,a,b)=x，
那么一直选择值为x的变化，如(a,b,c,d) -->(a1,b1,a,b) -->(a2,b2,a1,b1)-->(a3,b3,a2,b2)-->......
最后陷入循环之中（这个循序是费脑力的，必须时刻保持正确的选择，否则会输），或者在中间的某个局面选择值为1的变化，最后归于双方只有一个数字的和局循环之中（这个循环不需用脑，没得选择）。

hujunhua 发表于 2012-4-13 07:38:12

算法很妙，但是初值很重要。仅限于f(0,b,0,d)不够。f(a,b,0,d)=2,当a+d=0(mod10)或者b+d=0(mod10)时，它下一步终止于f(0,0,a,b)而不是f(0,b,o,d)型初值。

这个算法很容易实现递归程序，但递归层次会不会太深，尤其是对局面数不作合并与过滤的情况下。

mathe 发表于 2012-4-13 07:49:17

// sf.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <map>
#include <vector>
#include <list>
#include <algorithm>
using namespace std;

#define MOD 10
unsigned char mullist={3,7,9};
#define MC (sizeof(mullist)/sizeof(mullist))
//we must make sure a<=b and c<=d
#define MAKE_STATE(a,b,c,d) ((((unsigned)(unsigned char)a)<<24)|(((unsigned)(unsigned char)b)<<16)|(((unsigned)(unsigned char)c)<<8)|(((unsigned)(unsigned char)d)))
#define GET_A(x) ((unsigned char)(((unsigned)(x))>>24))
#define GET_B(x) ((unsigned char)(((unsigned)(x))>>16))
#define GET_C(x) ((unsigned char)(((unsigned)(x))>>8))
#define GET_D(x) ((unsigned char)(((unsigned)(x))))

unsigned int make_state(unsigned char a, unsigned char b, unsigned char c, unsigned char d)
{
unsigned char t;
if(a>b){t=b;b=a;a=t;}
if(c>d){t=d;d=c;c=t;}
return MAKE_STATE(a,b,c,d);
}
typedef map<unsigned int, int> IdMap;
IdMap myIdMap;
vector<unsigned int> idToState;
vector<unsigned int> result;
#define UNKNOWN 0
#define FIRSTWIN1
#define FIRSTLOST 2
struct Edges{
int e;
};

vector<Edges> prev,next;
list<int> losers;
vector<int> winers;
int lc,wc;
int getStateId(unsigned int x)
{
IdMap::iterator it;
it=myIdMap.find(x);
if(it==myIdMap.end())return -1;
return it->second;
}
void init()
{
unsigned char a,b,c,d;
int id=0;
int i;
myIdMap.clear();
for(a=0;a<MOD;a++)for(b=a;b<MOD;b++)for(c=0;c<MOD;c++)for(d=c;d<MOD;d++){
unsigned int state = make_state(a,b,c,d);
int i;
for(i=0;i<MC;i++){
IdMap::iterator iit=myIdMap.find(make_state((a*mullist)%MOD,(b*mullist)%MOD,(c*mullist)%MOD, (d*mullist)%MOD));
if(iit!=myIdMap.end()){
myIdMap.insert(make_pair(state,iit->second));
break;
}
}
if(i==MC){
myIdMap.insert(make_pair(state,id));
idToState.push_back(state);
id++;
}else{
continue;
}
}
for(i=0;i<id;i++)result.push_back(UNKNOWN);
for(id=0;id<idToState.size();++id){
unsigned int state=idToState;
unsigned char a,b,c,d;
a=GET_A(state);
b=GET_B(state);
c=GET_C(state);
d=GET_D(state);
if(c==0&&d==0){
Edges e;
e.e=e.e=e.e=e.e=-1;
next.push_back(e);
continue;///terminate states, no out edges
}
int cc=0;
int j;
Edges e;
if(c!=0){
if(a!=0)
e.e=myIdMap.find(make_state(c,d,(a+c)%MOD,b))->second;
if(b!=0)
e.e=myIdMap.find(make_state(c,d,a,(b+c)%MOD))->second;
}
if(d!=0){
if(a!=0)
e.e=myIdMap.find(make_state(c,d,(a+d)%MOD,b))->second;
if(b!=0)
e.e=myIdMap.find(make_state(c,d,a,(b+d)%MOD))->second;
}
sort(&e.e,&e.e);

for(i=1,j=1;i<cc;i++){
if(e.e==e.e)continue;
e.e=e.e;
j++;
}
cc=j;
for(i=cc;i<4;i++){
e.e=-1;///mark invalid edges
}
next.push_back(e);
}
for(id=0;id<idToState.size();++id){
unsigned int state=idToState;
unsigned char a,b,c,d;
a=GET_A(state);
b=GET_B(state);
c=GET_C(state);
d=GET_D(state);
if(a==0&&b==0){
Edges e;
e.e=e.e=e.e=e.e=-1;
prev.push_back(e);
continue;
}
int cc=0;
int j;
Edges e;
if(a!=0){
if((c-a)%MOD!=0)
e.e=myIdMap.find(make_state((c-a+MOD)%MOD,d,a,b))->second;
if((d-a)%MOD!=0)
e.e=myIdMap.find(make_state(c,(d-a+MOD)%MOD,a,b))->second;
}
if(b!=0){
if((c-b)%MOD!=0)
e.e=myIdMap.find(make_state((c-b+MOD)%MOD,d,a,b))->second;
if((d-b)%MOD!=0)
e.e=myIdMap.find(make_state(c,(d-b+MOD)%MOD,a,b))->second;
}
sort(&e.e,&e.e);

for(i=1,j=1;i<cc;i++){
if(e.e==e.e)continue;
e.e=e.e;
j++;
}
cc=j;
for(i=cc;i<4;i++){
e.e=-1;///mark invalid edges
}
prev.push_back(e);
}
for(id=0;id<idToState.size();++id){
unsigned int state=idToState;
unsigned char a,b,c,d;
a=GET_A(state);
b=GET_B(state);
c=GET_C(state);
d=GET_D(state);
if(c==0&&d==0&&(a!=0||b!=0)){
result=FIRSTLOST;
losers.push_back(id);
lc++;
}
if(a==0&&b==0&&(c!=0||d!=0)){
result=FIRSTWIN;
wc++;
}
}
}

void dumpstate(int i){
unsigned int state=idToState;
unsigned char a,b,c,d;
// if(result!=FIRSTLOST)return;
a=GET_A(state);
b=GET_B(state);
c=GET_C(state);
d=GET_D(state);
printf("state[%d:%d;%d:%d] is ",a,b,c,d);
if(result==FIRSTWIN){
printf("first user win\n");
}else if(result==FIRSTLOST){
printf("first user lost\n");
}else{
printf("tie \n");
}
}

int _tmain(int argc, _TCHAR* argv[])
{
int i;
init();
start:
while(losers.size()>0){
int id = losers.front();
losers.pop_front();
for(i=0;i<4;i++){
int pid=prev.e;
if(pid<0)break;
if(result==UNKNOWN){
result=FIRSTWIN;
wc++;
winers.push_back(pid);
}else if(result!=FIRSTWIN){
fprintf(stderr,"Invalid 1\n");
return -1;
}
}
}
int c=winers.size();
for(i=0;i<c;i++){
int id = winers;
int j;
for(j=0;j<4;j++){
int pid=prev.e;
if(pid<0)break;
if(result==UNKNOWN){
int k;
for(k=0;k<4;k++){
if(next.e<0)break;
if(result.e]!=FIRSTWIN)break;
}
if(k==4||next.e<0){//all next are first_win
result=FIRSTLOST;
lc++;
losers.push_back(pid);
}
}
}
}
if(losers.size()>0)goto start;
c=result.size();
printf("win count=%d, lost count=%d, undertermined=%d\n",wc,lc,c-wc-lc);
for(i=0;i<result.size();i++){
if(result!=UNKNOWN){
dumpstate(i);
}
}
return 0;
}

mathe 发表于 2012-4-13 07:50:45

程序使用了hujunhua的等价类合并方法，所以一个状态可能代表两个或四个等价状态
win count=117, lost count=49, undertermined=607
state is first user win
state is first user win
state is first user win
state is first user win
state is first user win
state is first user win
state is first user win
state is first user win
state is first user win
state is first user win
state is first user win
state is first user win
state is first user win
state is first user win
state is first user win
state is first user win
state is first user lost
state is first user win
state is first user lost
state is first user lost
state is first user lost
state is first user win
state is first user win
state is first user win
state is first user win
state is first user win
state is first user win
state is first user win
state is first user win
state is first user win
state is first user win
state is first user win
state is first user win
state is first user win
state is first user win
state is first user win
state is first user win
state is first user lost
state is first user win
state is first user win
state is first user win
state is first user lost
state is first user win
state is first user win
state is first user lost
state is first user win
state is first user lost
state is first user win
state is first user lost
state is first user win
state is first user win
state is first user win
state is first user win
state is first user win
state is first user win
state is first user win
state is first user lost
state is first user win
state is first user win
state is first user win
state is first user win
state is first user win
state is first user win
state is first user win
state is first user win
state is first user win
state is first user win
state is first user win
state is first user win
state is first user win
state is first user win
state is first user win
state is first user win
state is first user lost
state is first user lost
state is first user win
state is first user win
state is first user win
state is first user win
state is first user win
state is first user win
state is first user win
state is first user win
state is first user win
state is first user lost
state is first user win
state is first user lost
state is first user lost
state is first user lost
state is first user win
state is first user win
state is first user win
state is first user win
state is first user lost
state is first user win
state is first user win
state is first user win
state is first user win
state is first user lost
state is first user lost
state is first user lost
state is first user lost
state is first user win
state is first user lost
state is first user win
state is first user lost
state is first user win
state is first user win
state is first user win
state is first user win
state is first user win
state is first user lost
state is first user win
state is first user win
state is first user win
state is first user win
state is first user lost
state is first user lost
state is first user win
state is first user win
state is first user win
state is first user lost
state is first user win
state is first user lost
state is first user win
state is first user win
state is first user lost
state is first user lost
state is first user lost
state is first user win
state is first user lost
state is first user lost
state is first user lost
state is first user lost
state is first user lost
state is first user lost
state is first user lost
state is first user win
state is first user win
state is first user win
state is first user win
state is first user lost
state is first user lost
state is first user win
state is first user win
state is first user win
state is first user win
state is first user win
state is first user win
state is first user win
state is first user lost
state is first user lost
state is first user lost
state is first user win
state is first user win
state is first user lost
state is first user lost
state is first user lost
state is first user lost
state is first user win
state is first user win
state is first user win
state is first user lost
state is first user lost
state is first user win
state is first user win

056254628 发表于 2012-4-13 11:09:46

标题

17# hujunhua
(0,0,a,b)局面的初值我没有设置，直接在程序里判断，能变化成该局面的f值为2.,当然，把它们设成初值为0也行。

页: 1 [2] 3

数学研发论坛's Archiver

局面的合并与过滤

标题