一种棋类游戏

mathe · 发表于 2009-10-13 22:15:32

穷举也是一种策略. 不过这里发现还可以优化. 考虑到不同的状态,它们所有棋子所在格子和邻居覆盖的集合可能相同.采用这个集合作为hash表的关键字更加好,应该可以大量降低表格的大小,从而大量节省内存空间

〇〇 · 发表于 2009-10-15 10:22:30

有结果了么

mathe · 发表于 2009-10-15 12:02:08

8*8先手败

056254628 · 发表于 2009-10-15 20:34:32

可以以n为奇数(n*n的棋盘)来验证程序的正确性。只有对于所有的n(n为奇数)结果都是先手胜，程序才有可能是正确的。

mathe · 发表于 2009-10-15 22:13:26

// chp.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <string.h>
#include <assert.h>
#include <stdlib.h>
#define N 8
#define BITS (N*N)
typedef unsigned long long SET;
SET nghb[BITS];
#define EMPTY_SET 0LL
#define INDEX(x,y) ((x)*N+(y))
#define GET_X(ind) ((ind)/N)
#define GET_Y(ind) ((ind)%N)
#define ADD_INDEX(s, ind) ((s)|=1LL<<(ind))
#define TEST_INDEX(s, ind) (((s)&(1LL<<(ind)))!=0)
#define CORNMASK (3|(3<<N))
#define TEST_BIT(x, b) (((x)&(1LL<<(b)))!=0)
#define SET_BIT(x, b) ((x)|=(1LL<<(b)))
#define GET_CORN(x) (((x)&3)| (((x)>>N)&3)<<2)
#define DISP_CORN(x) (((x)&3)| ((((x)>>2)&3)<<N))
#define ECVALUE(x) (((x)&~CORNMASK)|DISP_CORN(cr[GET_CORN(x)]))
#define STABLE 50000033
#define WALK 1000
int hc;
int ec;
int nec;
int lec;
long long htable[STABLE];
long long htable2[STABLE];
char cr[16]={1,-1,-1,-1,-1,-1,-1,-1,4,-1,5,-1,3,-1,11,7};
char rc[16]={-1,0,-1,12,8,10,-1,15,-1,-1,-1,14,-1,-1,-1,-1};
FILE *fout;
void dump(long long v)
{
int i,j;
for(i=0;i<N;i++){
for(j=0;j<N;j++){
if(TEST_BIT(v,i*N+j)){
fprintf(fout,"1 ");
}else{
fprintf(fout,"0 ");
}
}
fprintf(fout,"\n");
}
fprintf(fout,"\n");
}
void copy_ec(long long *p)
{
int i,t;
for(i=0,t=0;i<STABLE;i++){
if(htable[i]!=-1LL){
if(cr[GET_CORN(htable[i])]!=-1){
p[t++]=htable[i];
}
}
}
}
void dump_ec(long long htable[])
{
int i;
fout = fopen("dump.txt","w");
for(i=0;i<STABLE;i++){
if(htable[i]!=-1LL){
if(cr[GET_CORN(htable[i])]!=-1){
dump(htable[i]);
}
}
}
fclose(fout);
}
void init()
{
memset(htable,-1,sizeof(htable));
memset(htable2,-1,sizeof(htable2));
}
int hash(SET s)
{
return (int)(s%STABLE);
}
int add_hash(long long htable[],long long key, bool eq)
{
int v=hash(key);
long long ev;
ev=ECVALUE(key);
if(hc>=STABLE){
fprintf(stderr,"out of hash table range\n");
exit(-1);
}
do{
if(htable[v]==-1LL){
if(eq){
htable[v]=ev;nec++;
}else{
htable[v]=key;
ec++;
}
hc++;
return v;
}else if(htable[v]!=key&&htable[v]!=ev){
v=(v+WALK)%STABLE;
}else{
if(eq){
assert(htable[v]==ev);
}else{
assert(htable[v]==key);
}
return v;
}
}while(1);
}
int query_hash_entry(long long htable[],long long key)///return index to hash table
{
long long ev=ECVALUE(key);
int v=hash(key);
do{
if(htable[v]==-1LL)return v;
if(htable[v]==key||htable[v]==ev)
return v;
v=(v+WALK)%STABLE;
}while(1);
}
void init_neighbour()
{
int i,j;
for(i=0;i<N;i++){
for(j=0;j<N;j++){
SET s=EMPTY_SET;
ADD_INDEX(s,INDEX(i,j));
if(i>0&&j>0){
ADD_INDEX(s,INDEX(i-1,j-1));
}
if(i>0){
ADD_INDEX(s,INDEX(i-1,j));
}
if(j>0){
ADD_INDEX(s,INDEX(i,j-1));
}
if(i>0&&j<N-1){
ADD_INDEX(s,INDEX(i-1,j+1));
}
if(j<N-1){
ADD_INDEX(s,INDEX(i,j+1));
}
if(i<N-1&&j>0){
ADD_INDEX(s,INDEX(i+1,j-1));
}
if(i<N-1){
ADD_INDEX(s,INDEX(i+1,j));
}
if(i<N-1&&j<N-1){
ADD_INDEX(s,INDEX(i+1,j+1));
}
nghb[INDEX(i,j)]=s;
}
}
}
void visit(long long neighb)
{
int i;
int e=query_hash_entry(htable,neighb);
if(htable[e]==neighb){
int ee=query_hash_entry(htable2,neighb);
if(htable2[ee]==-1){
htable2[ee]=neighb;
lec++;
for(i=0;i<BITS;i++){
if(TEST_BIT(neighb,i)==0){
long long newneighb=neighb;
newneighb|=nghb[i];
visit(newneighb);
}
}
}
}else{
for(i=0;i<BITS;i++){
if(TEST_BIT(neighb,i)==0){
long long newneighb=neighb;
newneighb|=nghb[i];
int e2=query_hash_entry(htable,newneighb);
if(htable[e2]==newneighb){
visit(newneighb);
break;
}
}
}
}
}
int query(long long neighb)
{
int e=query_hash_entry(htable,neighb);
if(htable[e]!=-1)
return e;
int i;
for(i=0;i<BITS;i++){
if(TEST_BIT(neighb,i)==0){
long long newneighb=neighb;
newneighb|=nghb[i];
int r=query(newneighb);
if(htable[r]==newneighb)
break;
}
}
if(i<BITS){///find any status is newneighb
return add_hash(htable,neighb,true);
}else{
return add_hash(htable,neighb,false);
}
}
int cmpll(const void *p,const void *q)
{
const long long *lp=(const long long *)p;
const long long *lq=(const long long *)q;
if(*lp==*lq)return 0;
if(*lp<*lq)return -1;
return 1;
}
int _tmain(int argc, _TCHAR* argv[])
{
int i,j;
init();
init_neighbour();
int s=query(0LL);
if(htable[s]==0LL){
printf("First fail\n");
}else{
printf("First successful\n");
}
printf("Total table size %d\n",hc);
printf("Total eq stat found %d\n",ec);
printf("Total neq stat found %d\n",nec);
visit(0LL);
printf("Total lec stat found %d\n",lec);
// dump_ec(htable2);
#if 0
for(i=0;i<BITS;i++){
long long r=nghb[i];
printf("%d set={ ",i);
for(j=0;j<BITS;j++){
if(!TEST_BIT(r,j)){
long long newneighb=r;
newneighb|=nghb[j];
int u=query_hash_entry(htable,newneighb);
if(htable[u]==newneighb){
printf("%d ",j);
}
}
}
printf("}\n");
}
#endif
return 0;
}

复制代码

〇〇 · 发表于 2009-10-16 08:21:38

15# mathe 用什么编译器编译 C:\vc6>cl ch.cpp Microsoft (R) 32-bit C/C++ Optimizing Compiler Version 12.00.8168 for 80x86 Copyright (C) Microsoft Corp 1984-1998. All rights reserved. ch.cpp ch.cpp(4) : fatal error C1083: Cannot open include file: 'stdafx.h': No such file or directory C:\vc6>cl ch.cpp Microsoft (R) 32-bit C/C++ Optimizing Compiler Version 12.00.8168 for 80x86 Copyright (C) Microsoft Corp 1984-1998. All rights reserved. ch.cpp ch.cpp(10) : error C2632: 'long' followed by 'long' is illegal ch.cpp(32) : error C2632: 'long' followed by 'long' is illegal ch.cpp(33) : error C2632: 'long' followed by 'long' is illegal

风云剑 · 发表于 2009-10-16 08:48:08

VC7,8,9,gcc

风云剑 · 发表于 2009-10-16 08:54:05

要多大内存啊？我1G内存的电脑都跑不动。

mathe · 发表于 2009-10-16 09:16:51

那么把main函数中对visit的调用删除(那部分没有用,是我自己调试用的)然后将全局变量htable2也删除,visit函数删除

mathe · 发表于 2009-10-16 09:17:21

如果在vc6下,将所有long long 改为__int64.

账号		自动登录	找回密码
密码			欢迎注册

[讨论] 一种棋类游戏