[数值计算] CWHGN比赛来啦！可以用任何语言任何算法来猜数哦！

tiger999

首先感谢 bbaa在排行版上面的制作和index的纠正
其次是这游戏
首先这游戏的灵感是来自于bbaa的猜数游戏
这个游戏和bbaa的猜数游戏有一点不一样
bbaa的游戏是反馈大和小，我的则是反馈A和B的数量

主页是
http://www.codetiger.win/extra/index.php

什么是A和B的数量呢？请看下面


这个游戏是著名的猜数字游戏
百度百科介绍，里面还有一些算法可以帮你！
是一个4位数用10个数字0-9(也就是5040种排列，PS不能有重复)
如果位置对了数字也对了那么就是一个A
如果数字对了但是位置错了那么就是一个B
举个例子答案是9124
我猜了9042
9是A 那就是1A
2是B 4是B 那就是2B
那么这个答案就是1A2B

现在说API端口
http://www.codetiger.win/extra/API.php (可能还没开放)
POST和GET都可以(我用的是request 2333)
参数:
passwordstring)
username:(string)
number:(int)
send:answer (必须只能是answer)
返回的是
Content-type: application/json
tokens:(int)
A:(int)
B:(int)
count:(int)
code:(int)

code的意义:
100对了！你是胜利者！
150全部符合要求，可是答案错了
200参数残缺！
300密码都错了，你还弄啥
400参数number的位数不是4位数
500参数number有重复数字
这里PS一下 tokens可以被理解为这一局的编号，如果tokens变了，证明有其他人做出来了
而count是自己目前的积分

还有请务必加群，因为这其实本身是群内的比赛，人不太够，并且这个比赛有奖品，所以如果你不加群我也不知道去哪里找你
对！这个比赛有奖品哦！参加过上次群里的比赛的人可能知道，这奖品奖金还挺多的哦！

523066680

回复 64# avgBullsCows

    感谢neo提供的最优搜索树，省去了筛选+处理数组的过程，本地效率大大提升。（后来我发现这个问题即使运行时效率提高了，网络不熟悉的话还是要吃大亏啊）
读取 JSON 进行刷题的 Perl 代码：

=info
523066680 2017-08
=cut

use JSON;
use IO::Handle;
use File::Slurp;
use LWP::UserAgent;
use Data::Dumper;
use Time::HiRes qw/sleep/;
STDOUT->autoflush(1);

our $user = "vic3";
our $pass = "tempcode";
our $website = 'http://www.codetiger.win/extra/API.php';
our $ua = LWP::UserAgent->new(  keep_alive=>1, agent => 'Mozilla/5.0', timeout => 0.2 );

my $json;
my $tree;
$json = read_file("crushBullsCows.json");
$json=~s/\'/\"/g;
$tree = decode_json($json);

AGAIN:
my $ref = $tree;
my $guess = $ref->{'xx'};
my $AB;
my ($curr, $prev) = (undef, undef);

while (1)
{
	($AB, $curr) = post_num( $guess );
    print " [$AB] [ $guess ] $curr\n";

    if ( $AB eq "40" ) {
        print "Success $guess\n\n";
        last;
    }

    if (defined $prev and ($curr ne $prev) ) 
    { 
        print "Tokens changed\n [$AB] [ @$guess ] $curr\n";
        goto AGAIN;
    }

    #update guess number, and $ref 
	for my $e ( @{$ref->{'c'}})
	{
		if ( exists $e->{$AB} )
		{
			#print $e->{$AB};
			$guess = $e->{$AB};
			$ref = $e;
			last;
		} 
	}
    $prev = $curr;
}

goto AGAIN;

sub post_num
{
    our($ua, $website, $user, $pass);
    my $n = shift;
    my $res;
    my $data;
    my $text;

    while (1)
    {
        $res = 
            $ua->post( 
                $website,
                [ username=>$user, password =>$pass, number=>$n, send=>'answer' ]
            );
        $text = $res->content();
        if ( $text =~/"A":\d,"B":\d/ ) { last }
        print ".";
        sleep 0.01;
    }

    #print $res->content(), " - $n\n";
    $data = decode_json( $res->content() );
    return $data->{A} . $data->{B}, $data->{tokens};
}
复制代码

523066680

观察比赛各玩家猜题速度的脚本。

=info
    Auth: 523066680
    Date: 2017-07
=cut

use JSON;
use Encode;
use Data::Dumper;
use Try::Tiny;
use Time::HiRes qw/time sleep/;
use IO::Handle;
STDOUT->autoflush(1);

use LWP::Simple;
use LWP::UserAgent;

our $user = "vic3";
our $pass = "tempcode";
our $website = 'http://www.codetiger.win/extra/score.json';
our $ua = LWP::UserAgent->new(  agent => 'Mozilla/5.0', timeout => 3 );

my %ever;
my %current;
getData( \%ever );

my $count = 0;
my $delta;
my $speed;
my $time_a = time();

while (1)
{
    getData(\%current);

    $count = 0;
    for my $k (reverse sort { $ever{$a} <=> $ever{$b} } keys %ever)
    {
        $delta = $current{$k} - $ever{$k};
        $speed = $delta / (time() - $time_a) * 60.0;

        printf "%-10s %5d + %-5d %.1f/min\n", 
            encode('gbk',  $k), 
            $ever{$k}, 
            $delta,
            $speed
            ;

        last if ($count++ > 5);
    }
    print "\n";

    sleep 10.0;
}

sub getData
{
    my $href = shift;
    my $res;
    my $data;

    while (1)
    {
        $res = $ua->get( $website );
        try { $data = decode_json( $res->content ); last; }
        catch { sleep 2.0; printf "repeat\n" }
    }

    for my $name ( keys %$data )
    {
        $href->{$name} = $data->{$name};
    }
}
复制代码

avgBullsCows

回复 74# 523066680

An secret number for bulls-cows game can be four-place decimal with different
digits from 0 to 9. Total amount of secret numbers is 10!/6! = 5040. For
mastermind secret number is four-place digital with digits from 0 to 5. Digits
can repeat. So total amount of secret numbers is 6^4 = 1296. In common case
such games have three parameters - number of positions, number of different
digits and repeatability (1 - yes, 0 -no). From this point of view bulls-cows game
has parameters (4, 10, 0), mastermind has parameters (4, 6, 1). Optimization
of two game types has two directions.
复制代码

我的理解是 bulls-cows 游戏是 参数描述(4, 10, 0) 4个位置, 10个符号, 符号不可重复
mastermind 参数描述(4, 6, 1) 4个位置, 6个符号, 符号可重复

不论哪种游戏, 算法优化有两个目标方向

 The goal is to find algorithm which minimizes amount of secret numbers which algorithm can guess ...
复制代码

crush 算法的优化目标, 搜索树空间回合总数最小化

 The second criterion is minimize average amount of turns for guess arbitrary secret number - minimal average game length
复制代码

avg 算法的优化目标, 平均搜索回合数(平均游戏长度)最小化

523066680

回复 73# avgBullsCows

avgBullsCows 好像是跑可重复数字的，平均速度4.x， crusBullsCows 是不可重复4位数字的，平均速率 5.25 和百度提到的一样
    http://slovesnov.users.sourcefor ... lish,crushBullsCows

更新一下现在的情况，还是 JAVA 对 PERL

Scallop    208598 + 1351  172.0/min
vic3       45021 + 722   91.9/min
bbaa         238 + 0     0.0/min
TJUGERKFER    55 + 0     0.0/min
adad          27 + 0     0.0/min
复制代码

差不多是2:1

另一个对比，分别 POST 网站 1000次，java 耗时大约52秒，perl 耗时大约64秒。

avgBullsCows

我想试试这棵树

http://slovesnov.users.sourceforge.net/index.php?bullscows_tree,english,avgBullsCows

这棵树的生成脚本

http://slovesnov.users.sourceforge.net/scripts/bullscows.js

整个脚本文件 1000+ 行, 就不贴了
复制代码

523066680

前面是个误会，链接的问题实在不应该，我们反复问楼主群号，他反复回答是在主题蓝色的链接里，
而楼主发的网站链接恰恰没有打上 url 标签，所以不是蓝色的，只有百度百科是蓝色的。
大写的懵（每一次看回复都是黑人问号脸）！

知道链接后就去试了，游戏规则之一是，post 4位不重复的数字测试结果。数字少了不行。
试了一阵子发现可以用字母做占位符，这个时候还不知道筛选法。

多线程？

第一个思路，跑10个线程，"0ABC","1ABC","2ABC" ... "9ABC"，等10个线程返回，
会得到1个 A1B0 和 3个A0B1 。也就是这10个里必然有一个位置正确，3个数字正确但位置不正确。
将3个B1取出，可以排6种情况，A1在开头，6个线程出去就有结果了。

优化空间

如果提前得到1个A1 和3个B1，线程可以提前kill掉。
第二轮6个排列出去，如果提前出现A4B0，可以提前kill线程，进入下个回合。


结果

刚开始 Scallop 没在跑，这方法大概是20/min的抢答速度。当他的程序跑起来的时候，
线程严重阻塞，10个线程都返回的时候 tokens 变了 3 到 4 次

筛选法

后面才搞清楚百科提到的筛选法，比较固执没去看，多亏happy66r指教。

先派出"0123"去试探，假设返回是A0B1，用5040个排列情况去和这个0123做比较，找出也是 A0B1 的排列，
这个时候缩小到 1440 种排列（可参考PAKTC提供的文档），答案就在这里面。
从1440中挑选一个去试探，假设是3987, 返回A0B2；再用1439个元素（去掉了3987）和 3987碰撞，筛选出
结果为A0B2的组合，这个有多少就交给程序了~
重复这个过程，备用组合不断缩小，最后得到A4B0。

这种方法需要自己写一个测试函数，返回AB数值。
试过所有情况，平均5.5次猜中一次，有优化空间，参考百度。

效率

用的Perl脚本，反复的数组操作和测试函数的调用消耗较大。假设post来回0.1秒，第一轮5040个测试
跑了0.3秒，别人已经三个post来回了。做了一些修改，

目前 Scallop 和 vic3 的猜题速度大概是 4:1 到 5:1，有空继续优化。

Scallop    77453 + 38    226.2/min
vic3       20333 + 13    77.4/min
bbaa         238 + 0     0.0/min
TJUGERKFER    21 + 0     0.0/min

Scallop    77453 + 79    235.5/min
vic3       20333 + 19    56.6/min
bbaa         238 + 0     0.0/min
TJUGERKFER    21 + 0     0.0/min
复制代码

其他优化

tokens 变化的时候，可以用当前反馈的数据更新筛选数组，接着跑；重置的话基本错过一个回合。

是否还考虑多线程？

由于现在服务端的处理机制（据说现在是文本存数据），我发现排队发送阻塞还少一点，多线程阻塞严重。
如果一定要多线程，参考前面提到的，单线程平均5.x次就能猜中一个。所以多线程不要超过5。假设是5线程，
第二回合你就该算出结果，不要超过两回合，别人已经刷了几个答案了。

当然了，如果服务端改了方案，多线程的利弊会有所改变。

Edit by 523066680

[Finished in 0.2s]

codegay

回复 70# PakTC


    最大的时间消耗应该都是网络IO上，直觉用什么语言差异都不大。算法和方法才有影响。

PakTC

提供一点资料
www.cs.nccu.edu.tw/~chaolin/papers/science3203.pdf
这个文档是中文的，讲了两个数字游戏，关于这次的游戏的分析和解法在后半部分。

另外给准备做这道题但是还未实践的小伙伴提一些建议：
服务器响应蛮快的，不要让程序在运算和筛选上面过多耗时，
尽量使用速度更快的语言，如果一定要用脚本，空间换时间吧。

a20150604

http://slovesnov.users.sourceforge.net/bullscows/bullscows.pdf

http://slovesnov.users.sourceforge.net/index.php?bullscows,english

tiger999

回复 59# 老刘1号


    2333333333333333333333333333333333

tiger999

回复 57# a2002


    >.<原来是这样的

tiger999

回复 54# a2002


    哦。。。。。sorry

a2002

这应该叫猜网址游戏

523066680

回复 57# a2002


    这就尴尬了。