发表于 | 分类于 ， |

曾有一个小小的黑色本子，记录了高中时期痴迷的诗词，还夹有已经干枯的叶子和花，仿佛给墨迹添了一圈香气。我把它视若珍宝，无奈终于在一次意外中遗失，一起遗失的还有一叠名为「遗忘」的信纸，至今耿耿于怀。

近来尤其喜欢苏轼的《临江仙·夜归临皋》，从前最喜欢的是这首词结尾两句：「小舟从此逝，江海寄余生」，现在重读却更为「家童鼻息已雷鸣，敲门都不应，倚杖听江声」句倾倒，真像极了辛帅写的「少年不识愁滋味，爱上层楼。爱上层楼，为赋新词强说愁」，从前哪里懂得「小舟从此逝，江海寄余生」的境界，只是被其中洒脱的仙气感染，觉得读上两句就能像向苏子一样超凡脱俗。

看过《中国诗词大会》和《中华好诗词》，尤其喜欢大学季恰同学少年专题节目，酣畅淋漓。后来偶然知道除了飞花令，还有单双飞花令，射覆飞花令，接龙各种诗词游戏玩法，和一群达人玩过一段时间后，偶尔会在一些诗句上卡壳，恰好前段时间在网上抓了一些诗词数据，一时兴起就想写一个自动生成双飞花和射覆游戏的小程序，实现了在群里自动飞花的程序。

素材准备

首先准备好诗词素材，这里我用的是从互联网上抓取的2万余作者信息的50余万篇诗词文赋，囊括了从古至今绝大部分的作者和作品。由于50多万作品中有很大一部分对我们是陌生的，因此我对它进行了筛选，尽量选择大家熟悉的作品，最终选定了14175篇放入素材池。

接口开发

使用Springboot开发Restful接口，通过docker部署到云服务器，接口调用方式如下：
http://tc.hakucc.com/api/shuangfei?clue=萧瑟秋风今又是 换了人间
http://tc.hakucc.com/api/shefu?clue=月明人倚楼 云7

自动回复

由于QQBot所依赖的SmartQQ协议停用，最后选择酷Q作为自动回复的工具。酷Q使用教程点此，配置完成后，编写CQPlusHandler.py如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
# -*- coding:utf-8 -*-

import cqplus
import requests
import random

    
class MainHandler(cqplus.CQPlusHandler):
    def handle_event(self, event, params):
        if event == 'on_private_msg':
            self.OnEvent_PrivateMsg(params)
        elif event == 'on_group_msg':
            self.OnEvent_GroupMsg(params)

    def OnEvent_PrivateMsg(self, params):        
        msg = params['msg']
        self.api.send_private_msg(params['from_qq'],msg)

    def OnEvent_GroupMsg(self,params):
        # 只针对特定的群
        if params['from_group'] in [642540069, 790583076]:
            result = self.shuangfei(params['msg'])
            if result != '':
                self.api.send_group_msg(params['from_group'], result)

    def shuangfei(self, clue):
        url = r'http://tc.hakucc.com/api/shuangfei?clue=' + clue
        r = requests.get(url)
        if r.json()['code'] == '0000':
            return r.json()['data'][random.randint(0, 20)]
        else:
            return ''

完成后无需执行CQPlusHandler.py，在酷Q中启用该应用即可。

参考
酷Q SDK-X

发表于 | 分类于 |

介绍

同源策略是浏览器端web应用安全的一个重要概念，在这个策略下，浏览器禁止页面中的脚本向其他域发送请求（如Ajax），以防止恶意站点读取其他站点的敏感信息；

场景分析

  • 假设有一个Web API地址为http://localhost:9000/api/values/
    该API返回一段简单的json数据，如下：
  • 有一个Web页面地址为http://localhost:8080
    页面中仅包含一段JavaScript脚本，请求上述api并在控制台显示返回结果，如果出错则显示错误信息，script内容如下：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    <script type="text/javascript">
        $.ajax({
            type: "GET",
            url: "http://localhost:9000/api/values/",
        }).done(function (data) {
            console.log(data);
        }).error(function (jqXHR, textStatus, errorThrown) {
            console.log(jqXHR.responseText || textStatus);
        });
    </script>

当打开页面，发现在控制台出现如下错误：

提示请求被cors策略限制，被请求的资源没有提供Access-Control-Allow-Origin头；出现此错误是由于同源策略的存在。

何为同源

只有协议，地址，端口均完全相同的URL才称为同源。
以下两个URL同源：

  • http://example.com/foo.html
  • http://example.com/bar.html
    以下四个URL和上两个URL均不同源：
  • http://example.net - Different domain
  • http://example.com:9000/foo.html - Different port
  • https://example.com/foo.html - Different scheme
  • http://www.example.com/foo.html - Different subdomain

http://localhost:9000/api/values/ 与 http://localhost:8080 不同源，因此从8080端口请求得到的JavaScript脚本中无法向9000端口提供的API发送请求。

解决跨域请求的几种方法

JSONP

在介绍JSONP之前，首先明确一点，即html可以通过script标签从不同的域获取JavaScript脚本，体现为在一个html页面中，可以从abc.com引入script1.js，同时从xyz.com引入script2.js，如下：

1
2
<script type="text/javascript" src="http://abc.com/jquery.min.js"></script>
<script type="text/javascript" src="http://xyz.com/bootstrap.min.js"></script>

实际上，对于支持src属性的标签，都是可以从不同的域引入资源的，比如通过img标签从不同的域获取图片资源等。在此前提下，是否可以将json数据放在JavaScript脚本中被获取呢？考虑一个特定场景，假设html中仅包含一段JavaScript脚本，如下所示，脚本中定义并调用了一个方法mycallback：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
<!DOCTYPE html>
<html>
<head>
	<title>JSONP</title>
</head>
<body>
	<script type="text/javascript">
		let mycallback = function(data){
			console.log(data);
		};

		mycallback("Hello Haku.");
	</script>
</body>
</html>

当打开页面，会在控制台看到Hello Haku.的输出；
当然也可以把调用mycallback的脚本放到单独的data.js文件，调整为如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
<!DOCTYPE html>
<html>
<head>
	<title>JSONP</title>
</head>
<body>
	<script type="text/javascript">
		let mycallback = function(data){
			console.log(data);
		}
	</script>
	<script type="text/javascript" src="data.js"></script>
</body>
</html>

data.js仅包含调用mycallback语句：

1
mycallback([{"name": "haku"}, {"name": "chihiro"}])

当刷新页面，会在控制台看到[{"name": "haku"}, {"name": "chihiro"}]的输出；

JSONP（JSON with padding）是一种通过注入<script>标签的方式请求数据的JavaScript模式，使得可以绕开同源策的略限制共享数据，此处padding实际上是指一个回调函数（如上例中的mycallback）。由于同源策略的存在返回纯JSON数据的service无法跨域共享数据，但是在<script>元素中可以执行从其他源获取的内容；于是可以在页面中增加一个src为所请求url的<script>元素，JSONP返回的数据不是JSON数据，而是一段script，以JSONP响应对象作为参数的回调函数，这就是为什么JSONP请求中会包含一个callback参数。若需要服务端返回一段JavaScript脚本而不是json格式数据，需要修改服务端代码，以C#为例，为了方便可以直接引入第三方库WebApiContrib.Formatting.Jsonp，在api的配置函数中定义Fomatter，返回一段被回调函数包裹的脚本，代码如下

1
2
var jsonpFormatter = new JsonpMediaTypeFormatter(config.Formatters.JsonFormatter);
config.Formatters.Insert(0, jsonpFormatter);

然后将前端页面修改为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
<!DOCTYPE html>
<html>
<head>
	<title>JSONP</title>
</head>
<body>
	<script type="text/javascript">
		let mycallback = function(data){
			console.log(data);
		}
	</script>
	<script type="text/javascript" src="http://localhost:9000/api/values?callback=mycallback"></script>
</body>
</html>

此时刷新页面，会在控制台看到[{"name":"abc","value":"cba"},{"name":"xyz","value":"zyx"}]的输出，并且可以发现返回头中显示的返回类型为JavaScript而不是json，返回的内容如下所示：

如果引入了JQuery，则不必手动创建script标签，jQuery会自动创建和插入，只需要在ajax请求中将dataType属性设置为jsonp ，将前端页面调整为如下所示，即我们常见的jsonp使用方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
<!DOCTYPE html>
<html>
<head>
	<title>JSONP</title>
</head>
<body>
	<script type="text/javascript">        
        $.ajax({
            type: "GET",
            url: "http://localhost:9000/api/values",
            dataType:"jsonp",
        }).done(function (data) {
            console.log(data);
        }).error(function (jqXHR, textStatus, errorThrown) {
            console.log(jqXHR.responseText || textStatus);
        });        
    </script>
</body>
</html>

此时刷新页面，会在控制台看到[{"name":"abc","value":"cba"},{"name":"xyz","value":"zyx"}]的输出。

CORS

Cross Origin Request Sharing(CORS) 是W3C标准，允许服务器端放松同源策略；通过CORS服务器可以显式地允许一些跨域请求，体现为在response header增加Access-Control-Allow-Origin等属性。CORS在服务器端设置，浏览器端不需要其他修改。
以ASP.NET WebAPI为例，引入Microsoft.AspNet.WebApi.Cors库；在VS 中Ctrl + Q 快速启动搜索cors，在NuGet窗口中安装最新版本Microsoft.AspNet.WebApi.Cors；或者在Package Manager Console窗口通过执行命令：

1
Install-Package Microsoft.AspNet.WebApi.Cors

此命令安装最新版本的包并更新依赖，包括System.Web.Cors 和 System.Web.Http.Cors；

在Web API的配置函数中，增加config.EnableCors();以启用CORS，并在Controller类或者方法上增加[EnableCors]特性，如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
using System.Web.Http;
using System.Web.Http.Cors;

namespace APIs
{
    //[EnableCors(origins: "http://localhost:8080", headers: "*", methods: "*")]
    public class ValuesController : ApiController
    {
        // GET api/values
        [EnableCors(origins: "http://localhost:8080", headers: "*", methods: "*")]
        public IEnumerable<object> Get()
                {
                    var resultList = new List<object>();
                    resultList.Add(new { name = "abc", value = "cba" });
                    resultList.Add(new { name = "xyz", value = "zyx" });
                    return resultList;
                }
}

前端页面的ajax请求中一处dataType，调整回：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
<!DOCTYPE html>
<html>
<head>
	<title>JSONP</title>
</head>
<body>
	<script type="text/javascript">        
        $.ajax({
            type: "GET",
            url: "http://localhost:9000/api/values",
        }).done(function (data) {
            console.log(data);
        }).error(function (jqXHR, textStatus, errorThrown) {
            console.log(jqXHR.responseText || textStatus);
        });        
    </script>
</body>
</html>

此时刷新页面，会在控制台看到[{"name":"abc","value":"cba"},{"name":"xyz","value":"zyx"}]的输出，并且响应头中显示返回类型为json，以及Access-Control-Allow-Origin: http://localhost:8080 ，如下图所示：

CORS 支持在Action级别，Controller级别以及全局级别设置；如需在全局应用CORS策略，只需向EnableCors方法传递一个EnableCorsAttribute实例，如下：

1
2
var cors = new EnableCorsAttribute("http://localhost:8080", "*", "*");
config.EnableCors();

请求转发

正如前文介绍，同源策略是浏览器安全策略，服务端与服务端的交互不受同源策略限制；
在无法控制请求资源所在的远端服务器，不能设置返回头Access-Control-Allow-Origin的情况下，可以通过请求转发间接获取资源，即在前端页面发送请求至同源的后端地址，由同源后端与目标服务器交互获取资源，再将数据返回给浏览器端；前端页面所在的web应用中新增一个接口，如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
@RestController
@RequestMapping(value = "/forward")
public class ForwardController {

    @RequestMapping(value = "/getvalues", produces = "application/json")
    public String getValues()
    {
        final String uri = "http://localhost:9000/api/values/";

        RestTemplate restTemplate = new RestTemplate();
        return restTemplate.getForObject(uri, String.class);
    }
}

WebAPI应用一处JSONP和CORS配置，将前端页面调整如下，发送请求至同源的http://localhost:8080/forward/getvalues/，由getValues()方法在服务器之间获取数据：

1
2
3
4
5
6
7
8
$.ajax({
    type: "GET",
    url: http://localhost:8080/forward/getvalues/,
}).done(function (data) {
    alert(data);
}).error(function (jqXHR, textStatus, errorThrown) {
    alert(jqXHR.responseText || textStatus);
});

此时刷新页面，会在控制台看到[{"name":"abc","value":"cba"},{"name":"xyz","value":"zyx"}]的输出。

小结

JSONP方式的本质是通过下载JavaScript脚本的方式获取数据，因此只支持HTTP GET方法，CORS更灵活也更安全，应尽量选择使用CORS而避免JSONP。

参考资料：
JSONP
Enable cross-origin requests

发表于 |

堆的特性

  • 堆是一棵完全二叉树（除了最底层，其余各层节点数都达到最大，最底层的节点都在左边）；
  • 堆的左右子树仍然是堆；
  • 堆中每个节点的值都不大于/不小于其子节点的值；

由于堆是完全二叉树，所以对于序号i的节点（根节点序号为0）, 其左子节点序号为2i + 1，右子节点序号为2i + 2， 父节点序号为floor((i-1)/2)；

堆的操作

调整节点

找到节点和其子节点中最大的那个，将它与该节点交换，如果节点本身就是最大则不发生交换；一次调整之后，子树不一定仍满足最大堆特性，因此需要继续调整，使整棵树保持最大堆特性。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
//调整最大堆，将值大的节点上移
private static void heapifyMax(int[] array, int index, int size)
{
    int left = 2 * index + 1;
    int right = 2 * index + 2;
    int max = index;

    if(left < size && array[left] > array[max])
    {
        max = left;
    }

    if(right < size && array[right] > array[max])
    {
        max = right;
    }

    // 有调整，将大的节点上移
    if(max != index)
    {
        swap(ref array[index], ref array[max]);
        heapifyMax(array, max, size);
    }
}

private static void swap(ref int a, ref int b)
{
    int temp = a;
    a = b;
    b = temp;
}

构造最大堆

从最后一个叶子节点的父节点开始调整节点，直到前面所有节点都调整完毕，最大堆即构造完成；

1
2
3
4
5
6
7
8
private static void buildMaxHeap(int[] array)
{
    // 从最后一个节点的父节点开始，向上调用调整最大堆
    for(int i = array.Length /2 -1; i >= 0; i--)
    {
        heapifyMax(array, i, array.Length);
    }
}

插入节点

将节点插入到二叉树的最后一个叶子结点位置上，然后将它与它的父节点比较，如果比父节点小则停下，如果大则交换位置，然后对父节点递归直到根节点；

堆排序

最大堆中，堆顶元素的值最大，取出堆顶元素后调整堆中余下节点，使继续保持最大堆的特性，再次取出堆顶元素，持续此过程直到最后一个元素。

1
2
3
4
5
6
7
8
9
10
11
// 初始化最大堆，堆顶元素最大，将堆顶元素和最后一个叶子结点交换，重新调整二叉树保持最大堆特
//性；下次操作时排除尾部已排序的元素（通过heapifyMax 方法的最后一个参数决定）
private static void heapSort(int[] array)
{
    buildMaxHeap(array);
    for(int i = array.Length - 1; i > 0; i--)
    {
        swap(ref array[0], ref array[i]);
        heapifyMax(array, 0, i);
    }
}

TOP K

从大量数据中找出前K 大的数。最直接的方法对所有数据进行排序后取前K 个。我们的目的是找到这K个数，既不需要管其他的数是何顺序，也不要求这K个数有序，数据量大时对所有数据进行排序性价比太低。一种思路是维护一个大小为K 的最小堆，首先将任意K 个数放入堆中，余下的每个元素依次与堆顶元素进行比较，如果它比堆顶元素大，则删除堆顶元素，并将新的元素放入堆中，重新调整堆；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 找到最大的K个元素
private static void topK(int[] array, int K, int[] kMax)
{
    for(int i = 0; i < K; i++)
    {
        kMax[i] = array[i];
    }
    buildMinHeap(kMax);
    for (int j = K; j < array.Length; j++)
    {
        if(array[j] > kMax[0])
        {
            swap(ref kMax[0], ref array[j]);
            heapifyMin(kMax, 0, K);
        }
    }
}

发表于 | 分类于 |

十月的天已经黑得很早，下班回家时天已经黑了八九分。

每次路过窗户的时候，我总喜欢停下来，对窗里的妈妈呼喊几声。以前天黑得晚，看到不进门在外张牙舞爪的我，她会习惯性的嗔骂一句，我就十分开心。

这一次我见厨房亮着灯，妈正用心地准备晚上的饭菜。我努力地蹦跳呼喊都没有被发觉，才意识到她在里头看不见一片漆黑中的我，也听不到我的声音：这扇窗就这样隔绝了我俩。慢慢地周围变得安静起来，时间的概念逐渐模糊，不知道经历了1秒还是10秒还是1分钟，我是旁观者凝望着只有影像没有声音的画面，心里暖暖的……

按下门铃我飞快回到窗前，她擦了擦手，转身要去开门，专注的脸上生出笑容。我的世界终于恢复如常。

发表于 | 分类于 |

今天是中秋假期的第一天，早晨眼睛睁开得很干脆，像是被一种力量召唤。

眼角余光察觉到窗帘被风吸出窗外，形成一片饱满的穹幕。轻风穿过薄被，透过皮囊，缓缓波动的穹幕就是我此刻的心情。

不知道是不是幻觉，房间亮的很清澈。浮动的帘幕遮挡住视线，却解放了想象力：我看到了晨光，听到了树叶的声音，站在了高耸入云的楼顶，在一刹那精骛八极，心游万仞……

兴冲冲，失落落，直为自己早早拉开窗帘的行为懊恼不已。

发表于 |

在学校的时候上王老师的人工智能课，了解博弈树、启发式搜索、剪枝这些基本概念，很遗憾在当时没有完成五子棋。最近在和x 下五子棋的时候突然念头一闪，于是有了这篇文章和基于Minimax 算法的五子棋程序。程序源码：https://github.com/VincentGau/TicTacToe 包含井字棋和五子棋代码；

五子棋游戏是一个两方博弈过程，双方都能获取局面的完备信息，交替行动，最终一人获胜或达到平局，典型的零和博弈。适合使用极大极小值搜索来求解。极大极小值搜索是实现这个五子棋程序的基础。

极大极小值搜索

极大极小值搜索过程的本质是回溯，以深度优先方式遍历多叉树。
以棋类游戏为例，对于一个局面，一方有多种可能的落子法，对于它的任何一种落子情况，对方也都有多种落子，如此轮流行动。以多叉树形式表示，树的每一个节点表示一种可能的盘面，子节点表示所有可行方案，树的每一层代表一方，双方在树中交替出现。为了获取最后的胜利，一方要在所有可选项中做出能将其优势最大化的决策，另一方则选择令对手优势最小化的方法。极大极小值搜索过程中，假设每一步对方也会按照它的最佳方案行动；我们将博弈树中的层分成Max 层和Min 层，为了保证自己的收益最大化，Max 层节点会始终选择值最大的子节点来更新自己的值，Min层则相反，始终选择值最小的子节点；因此这个算法被称为Minimax。 以一个简单的图理解Minimax 算法：

上图中，有两类节点，分别代表博弈双方，

  • 方块，Max 层节点，代表我方回合，他始终选择子节点中的最大值来更新自己的值；
  • 圆圈，Min 层节点，代表对方回合，他始终选择子节点中的最小值来更新自己的值；
    现在节点1有两种选择，它应该做出怎样的选择，就是Minimax 算法要解决的问题。
    节点1 处于Max 层，它要选择2、3 中评价值最高的那一个；节点2 处于Min 层，它取值为所有子节点中最小的值，也就是节点5，所以节点2 的值为 3；同理，节点3 的值为1； 节点1 的值为3；所以节点1 应该选择第一种下法；虽然第三层四个节点中，评价值最大的是节点7，但是如果节点1 选择第二种方案，到达节点3，到对方轮次，此时决定权已经到对方手中，为了使利益最大化，对方会选择到节点6；

搜索的目标是选择一处收益最高的位置落子，上面的例子里，我们认为叶子结点的值是已知的，而实际上对于五子棋游戏，我们还不知道节点的值，为此，我们需要设定一个评判标准给节点打分，这就是后面我们会提到的评价函数。

评价函数

评价函数是影响决策的关键。首先了解五子棋的一些特征局面，

  • 连五：出现连续五个同色棋子；
  • 活四，有两点可以连五；
  • 冲四：有一点可以连五；
  • 活三：可以形成活四的连三；
  • 眠三：只能形成冲四的连三；
  • 活二：可以形成活三的连二；
  • 眠二：只能形成眠三的连二；

评分规则

如果盘面中有我方成五，表示我方已经获胜，因此给这个局面一个很高的评分（比如10000分），如果有对方成五，则给一个很低的评分（比如-10000分）；除了成五之外，活四等也是一个有利的局面，只需一步就可获胜，我们也给他一个相对较高的评分，比如8000（对方活四的话就给 -5000分）；类似地给双冲四、冲四活三、单活三等其他情况都设定一个分数：

棋型 评分
成五 10000
活四、双冲四、冲四活三 5000
双活三 3000
活三眠三 2000
冲四 1000
活三 500
双活二 400
眠三 300
活二 200
冲二 100
活一 70
死一 50

我们对盘面上的每一个点进行评分（我方为正，对方为负）；盘面的评价函数定为所有点中最高得分和最低得分之和。

点的评价函数

给每一点估值时，向八个方向扩展若干个位置，

α-β 剪枝

理解α-β剪枝

alpha-beta 剪枝是在Minimax 算法基础上的优化，避免扩展哪些不会被选择的节点，减少无效操作从而提高搜索效率。继续使用前面的例子来理解剪枝的过程。

我们扩展节点2，得到它的值为3；继续扩展节点3，因为节点3 处于Min 层，且节点6 的值为1，所以节点3 的值不可能大于1， 因此不论节点3 后面的子节点的值是多少，节点1 一定会选择到节点2，所以在得知节点6 的值为1 之后，节点3 到节点7 这条分支可以直接忽略，这个过程称为剪枝；

这里只对剪枝做了大概的理解，更多参见α-β剪枝

算法实现

为每一个节点增加α 和β属性，α 表示最大下界， β表示最小上界；在节点扩展过程中持续更新α 和β 的值，在Max 层更新α， Min层更新β；如果发现α 大于β， 则进行剪枝，不再计算后续子节点；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
public int minimax()
{
    ...
       
    // Max layer, computer's turn 
    if (turn == 0)
    {
        int maxInChild = int.MinValue;
        foreach (var move in availableMoves)
        {
            BoardState childState = new BoardState(newBoard(move, Helper.AIMark), changeTurn(turn), depth + 1, alpha, beta);
            
            // 搜索到最大深度或者已分出胜负，直接计算盘面评分
            if (depth >= Helper.searchDepth || checkFinished(childState.board).Count == 5)
            {
                childScore = evaluateBoard(childState.board);
                nextState = childState;
            }
            // 否则，继续计算子节点的评分选取最大者
            else
            {
                childScore = childState.minimax();
            }


            if (childScore > maxInChild)
            {
                maxInChild = childScore;
                alpha = maxInChild;
                nextState = childState;
                nextMove = move;
            }

            // 剪枝
            if (alpha >= beta)
                break;
        }
        return maxInChild;
    }

    //Min layer, player's turn
    else if (turn == 1)
    {
        // 与上类似
    }

    return 0;

}

算法优化

了解了Minimax 算法之后，我们可以想象，随着搜索深度的增加，需要计算的节点呈指数增长，虽然相较围棋复杂度低很多，但是我们想要穷举搜索这颗博弈树的所有叶子结点（最终一方获胜或平局）依然是不可行的，因此我们需要对此做一个限制，有两个方向，一个是设定搜索深度，这个深度即AI思索的步数，另一个是缩小可行落子点的范围，对于一些明显不适合的落点我们不进行扩展。

缩小候选点范围

五子棋盘有 15 * 15个点，所有没有落子的地方都是可行的，我们不可能对每种可能的落子情况都进行扩展，这些点中有一些明显不符合最优解，比如边角处，远离棋子圈处，我们可以通过缩小候选落子点范围来提升效率。在实践中，我选择那些周围有棋子存在的空位作为可能的落子点，比如棋盘上对方下了第一步，我们只考虑它周围一圈的八个点，因为只有这八个点周围有棋子（棋盘上的唯一一颗棋子），这样极大第减少了需要扩展的点，这样选取候选点没有经过科学验证，虽然可能失去潜在的最佳方案，但是直觉上落子在远离其他棋子的地方不会获得太多收益；

候选点排序

剪枝算法的效率依赖于着法的寻找顺序。如果总是先去搜索最坏的着法，那么剪枝就不会发生，最终会找遍整个博弈树，这时该算法就如同极大极小算法一样，效率非常低。所以我们考虑对候选点进行排序来提升效率。这里涉及到对候选点进行打分，如果在一个候选点落子后可以形成连五（或者阻止对方成五），那么它的评分应该偏高。为此我们首先为各种棋型设定一个评分规则：
成五
活四、双冲四、冲四活三
双活三
活三眠三
冲四
活三
双活二
眠三
活二
冲二
活一
死一

五子棋盘有15 * 15 个落子点，这些点有一些明显不符合最优解，比如边角处，远离棋子圈处，缩小候选落子点范围能有效提升处理速度和效率；通常棋子圈附近是落子的好选择；刚开局时落子；
候选落子位置根据已落子点周围一圈时确定，搜索深度为四层时，时间过长，只计算到达第四层的盘面估值和已经分出胜负的盘面估值；即使一步即可获胜，也需要等到前面的节点完成深度搜索；可以尝试对第一层进行估值，使用最大堆保存估值较高的K 个节点进行深度搜索，可更快发现一步获胜局面；

棋型：
连五：出现连续五个同色棋子；
活四，有两点可以连五；
冲四：有一点可以连五；
活三：可以形成活四的连三；
眠三：只能形成冲四的连三；
活二：可以形成活三的连二；
眠二：只能形成眠三的连二；

评价函数是影响决策的关键：
是对整个盘面进行评估还是对单个落子点进行评估？ 评估是否应该与轮次挂钩？ 考虑一种情况：黑子（max）形成冲四，如果是黑子轮，黑子下在第五个延伸位置即可获得连五的分数，如果是白子轮，它下在第五个延伸位置对自己成五可能并没有收益，但是它还是应该下在这个位置防止对方获胜；评价函数用二者之差来表示，博弈树中黑子作为max层追求最大的估值，白子作为min层追求最小的估值，黑子落第五个位置可获得10000分，假设白子落此位置可获得 -10 分（白子连五获得-10000分），

发表于 |

大多数Web 应用都有用户的存在，有用户必然涉及到授权和认证来控制用户行为，除了页面资源以外，访问其他不允许匿名访问的资源（如webapi）也需要经过授权和认证，系统验证了用户身份的合法性之后用户才可以继续访问。这里分两步：授权和认证，认证（Authentication）验证用户的身份；授权（Authorization）决定用户是否有正确的权限获取指定的资源；授权、认证过程可以直接集成到单个应用程序中，对于由众多应用程序形成的生态系统，为其中每一个应用程序都开发自己的用户体系无疑是重复造轮子，而且会随之产生巨大的运维压力，用户信息的新增、撤销和修改需要在多处同时处理，若再有和外部系统对接的需求，则会使事情更加复杂，因此需要将用户授权认证模块从应用程序剥离，作为一个独立的模块供多个系统共用，基于声明（Claim-based）的联合授权认证是一个可行的方案。

基于声明的授权认证

基于声明的授权和认证并不是全新的概念，在联合安全模型中，认证和授权过程与应用程序本身分开，认证和授权是另外的单独的Web服务，即安全令牌服务（Security Token Service, STS），STS负责颁发安全令牌；信赖方应用程序（Relying Party，RP）不进行用户认证，不再保存用户名和密码，不关心认证方如何认证，在认证方认证成功之后接收返回的令牌，令牌中包含了信赖方需要的用户名、角色、权限等用来认证用户身份的信息。这种方式避免了针对一个用户需要管理多个副本的情况，密码同步的问题也不复存在，并且能满足单点登录（SSO）的场景，用户在登录一个应用程序之后无需再次进行身份认证即可获得访问另一个应用的权限。在基于声明的应用程序中，用户身份将通过一组声明来表示，一个声明可能是用户名，也可能是邮箱地址、年龄等等。
基于声明的联合认证方式具有以下特点：

  • 将身份验证机制从应用程序和服务中分离出来，实现与应用程序的松耦合；
  • 使用声明（Claim）代替角色（Role），声明是一种更灵活、更精确的对象，它可以包括角色及其他信息；
  • 安全令牌服务STS可以仅作为一个功能模块在用户管理系统中实现，并且依赖方应用程序可以很方便地与STS建立关系；

认证过程

在基于声明的应用场景中，通常包含三方参与者，分别是：应用程序自身，终端用户和STS。

  1. 用户访问依赖方应用程序，依赖方应用程序发现该未经认证的请求，于是重定向到STS 服务；
  2. STS 服务需要用户提供凭证以验证身份，认证成功之后STS 会颁发一个令牌给用户；
  3. 带着这个令牌，用户请求会被STS 服务重定向到依赖方应用程序；
  4. 依赖方应用程序提前通过配置信任该STS 和它颁发的令牌，它会取出令牌中的声明信息，实现用户验证，之后会生成一个cookie，以便下次访问；

也就是说，在依赖方与STS服务建立起信任关系之后，当用户请求依赖方应用的资源时，依赖方应用程序不关心登录过程，不关心用户角色，只需要把用户重定向到STS，由STS作验证和返回令牌，依赖方应用程序从令牌中获取需要的信息。

名词解释

声明是标识信息描述，如：用户名，部门，角色信息等。身份提供者验证成功后会返回一组声明，信赖方应用程序根据声明进行授权；应用程序接收到的声明越多，对用户的了解就越详细；应用程序并不会去某一个路径查询用户的声明，而是用户发送声明给应用程序，应用程序会检测这些声明，通过Issuer 字段表示知道声明的颁发者，应用程序只会接受受信任的颁发者生成的声明。
令牌是声明传输的载体，是发行机构（STS）签名的一组序列化的声明；用户会将一组声明和请求一起通过POST 方式发送给应用程序，在安全性要求不高的场景中也可以使用不签名的声明；
STS，安全令牌服务，一个负责认证用户并颁发令牌的服务，它把声明打包进令牌，对令牌进行签名和加密；
依赖方应用程序即依赖声明的应用程序，它将用户认证逻辑代理出去给STS，提取STS 颁发的令牌中的声明并将它们用于身份验证；

具体场景

下面以一个具体场景为例，分析访问过程中的具体HTTP请求进一步理解基于声明的认证：
场景中涉及两个应用：一个是依赖方应用（例子中地址为 http://localhost:19851/），需要验证用户身份；一个是用户管理应用，用户数据保存在这里，也在这里对用户信息进行增删改查，同时STS也包含在这个系统中（例子中地址为 http://localhost:62398/）；

  1. 用户访问依赖方应用；
  2. 如果已有登录凭据则直接进入访问对应资源；如果没有登录凭据，则跳转向STS服务请求安全令牌，并在请求中附带来源信息以便在登录之后重新跳转回去；
  3. 用户被重定向到Identity用户管理的登录页面；
  4. 用户登录成功后跳转回指定页面，生成Token；
  5. 经过权限验证之后用户被重定向至最初的依赖方页面；

这个过程中发生的HTTP请求有：

  • 请求依赖方地址http://localhost:19851/：
    request：GET / HTTP/1.1
    response：HTTP/1.1 302 Found
    Location:
    http://localhost:62398/?wa=wsignin1.0&wtrealm=http%3A%2F%2Flocalhost%3A19851%2F&wctx=rm%3D0%26id%3Dpassive%26ru%3D%252F&wct=2018-09-25T06%3A25%3A12Z
    请求依赖方地址，被重定向到STS。以上重定向地址的query string中：
    wa 取值wsignin1.0表示登录请求，wsignout1.0表示登出请求；
    wtrealm 表示依赖方应用的URI， STS通过它来决定是否颁发令牌以及给予哪些声明；
    wct 记录请求时间，STS用于校验判断请求是否超时；
    wtreply 可选项，表示依赖方希望被重定向到的地址；

  • 请求STShttp://localhost:62398/，被重定向到登录页面：
    request：GET
    /?wa=wsignin1.0&wtrealm=http%3A%2F%2Flocalhost%3A19851%2F&wctx=rm%3D0%26id%3Dpassive%26ru%3D%252F&wct=2018-09-25T06%3A25%3A12Z HTTP/1.1
    response：HTTP/1.1 302 Found
    Location:
    /login.aspx?ReturnUrl=%2f%3fwa%3dwsignin1.0%26wtrealm%3dhttp%253A%252F%252Flocalhost%253A19851%252F%26wctx%3drm%253D0%2526id%253Dpassive%2526ru%253D%25252F%26wct%3d2018-09-25T06%253A25%253A12Z&wa=wsignin1.0&wtrealm=http%3A%2F%2Flocalhost%3A19851%2F&wctx=rm%3D0%26id%3Dpassive%26ru%3D%252F&wct=2018-09-25T06%3A25%3A12Z
    由于用户没有登录，被重定向到STS的地址后再次被重定向到登录页面；

  • 请求登录页面http://localhost:62398/：
    request：GET
    /login.aspx?ReturnUrl=%2f%3fwa%3dwsignin1.0%26wtrealm%3dhttp%253A%252F%252Flocalhost%253A19851%252F%26wctx%3drm%253D0%2526id%253Dpassive%2526ru%253D%25252F%26wct%3d2018-09-25T06%253A25%253A12Z&wa=wsignin1.0&wtrealm=http%3A%2F%2Flocalhost%3A19851%2F&wctx=rm%3D0%26id%3Dpassive%26ru%3D%252F&wct=2018-09-25T06%3A25%3A12Z HTTP/1.1
    response：HTTP/1.1 200 OK
    显示STS登录页面，等待用户输入登录信息；

  • 用户登录http://localhost:62398/：
    request：POST
    /login.aspx?ReturnUrl=%2f%3fwa%3dwsignin1.0%26wtrealm%3dhttp%253A%252F%252Flocalhost%253A19851%252F%26wctx%3drm%253D0%2526id%253Dpassive%2526ru%253D%25252F%26wct%3d2018-09-25T06%253A25%253A12Z&wa=wsignin1.0&wtrealm=http%3a%2f%2flocalhost%3a19851%2f&wctx=rm%3d0%26id%3dpassive%26ru%3d%252F&wct=2018-09-25T06%3a25%3a12Z HTTP/1.1

    response：HTTP/1.1 302 Found
    Location:
    /?wa=wsignin1.0&wtrealm=http%3A%2F%2Flocalhost%3A19851%2F&wctx=rm%3D0%26id%3Dpassive%26ru%3D%252F&wct=2018-09-25T06%3A25%3A12Z
    Set-Cookie: .ASPXAUTH=blablabla; path=/; HttpOnly
    用户POST表单数据之后，被重定向回STS；

  • 请求STS地址http://localhost:62398/：
    request：GET
    /?wa=wsignin1.0&wtrealm=http%3A%2F%2Flocalhost%3A19851%2F&wctx=rm%3D0%26id%3Dpassive%26ru%3D%252F&wct=2018-09-25T06%3A25%3A12Z HTTP/1.1
    response：HTTP/1.1 200 OK

    带cookie请求STS地址，响应页面包含一个自动提交的form；

  • 自动提交表单http://localhost:19851/
    request：POST / HTTP/1.1
    .ASPXAUTH=blablabla
    response：HTTP/1.1 302 Found
    Location: /
    Set-Cookie: FedAuth=blablabla; path=/; HttpOnly
    Set-Cookie: FedAuth1=blablabla; path=/; HttpOnly
    自动提交表单，将token发送到依赖方地址；

  • 访问依赖方地址http://localhost:19851/：
    request：GET / HTTP/1.1
    response：HTTP/1.1 200 OK
    依赖方消费Token，用户最终访问到依赖方应用；

基于声明和基于角色的区别

在基于角色的访问控制（Role-based Access Control，RBAC）中，用户权限通过一个基于角色的应用程序来管理和执行，如果用户拥有执行一个动作需要的角色，则该动作被允许；和基于角色的模型相比，Claim-based的方式不与角色捆绑，具有更好的灵活性和扩展性，声明并不局限于角色和权限，还能附带用户的其他信息，比如邮箱、生日，比如还可以通过isOver18 声明在不透露用户具体年龄的情况下验证用户是否有权限等等，授权的决定基于声明中的有效数据的任意逻辑，而在RBAC中，唯一使用的声明就是角色。

Claims认证与OAuth

OAuth是用于授权的工业标准协议，基于声明的认证与OAuth有不同的适用场景：
Claim-based：

  • 用于应用程序和用户身份认证解耦；
  • 事前约定建立信任关系，用户声明由身份管理员维护；
  • 安全令牌服务将声明包含在令牌中颁发并提交给应用；
    OAuth：
  • 用户可选授权；
  • 用于与第三方合作，应用本身有自己的用户体系；
  • 获取访问令牌去资源服务器获取；

基于声明的Web应用的实现

WIF

Windows Identity Framework（WIF）是一组.Net Framework 类库，实现身份感知的（Identity-aware）、基于声明（Claim-based）的应用程序和服务，WIF 原本作为独立下载的类库发布，现已经集成到.Net 4.5 中。有了WIF，我们可以自定义安全令牌服务，更容易地开发基于声明的Web 应用而无需再安装其他组件。

依赖方应用配置

依赖方Web应用程序如需使用已有的自定义STS进行身份认证，需要给项目添加引用并修改配置文件：
需要添加的引用包括System.IdentityModel 和System.IdentityModel.Services；
需要编辑配置文件web.config，使用基于声明的认证方式：

1
2
3
4
5
6
<system.webServer>
    <modules>
      <add name="WSFederationAuthenticationModule" type="System.IdentityModel.Services.WSFederationAuthenticationModule, System.IdentityModel.Services, Version=4.0.0.0, Culture=neutral, PublicKeyToken=b77a5c561934e089" preCondition="managedHandler" />
      <add name="SessionAuthenticationModule" type="System.IdentityModel.Services.SessionAuthenticationModule, System.IdentityModel.Services, Version=4.0.0.0, Culture=neutral, PublicKeyToken=b77a5c561934e089" preCondition="managedHandler" />
    </modules>
</system.webServer>

配置URL地址与处理程序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
<system.identityModel>
    <identityConfiguration saveBootstrapContext="true">
      <issuerTokenResolver type="SimpleWebToken.CustomIssuerTokenResolver, SimpleWebToken">
        <AddAudienceKeyPair  symmetricKey="wAVkldQiFypTQ+kdNdGWCYCHRcee8XmXxOvgmak8vSY=" audience="http://localhost:19851/" />
      </issuerTokenResolver>
      <issuerNameRegistry type="RelyingParty.TrustedIssuerNameRegistry, RelyingParty"/>
      <audienceUris>
        <add value="http://localhost:19851/"/>
      </audienceUris>
      <securityTokenHandlers>
        <add type="SimpleWebToken.SimpleWebTokenHandler, SimpleWebToken" />
      </securityTokenHandlers>
    </identityConfiguration>
</system.identityModel>

1
2
3
4
5
6
7
8
9
10
11
<system.identityModel.services>
<federationConfiguration identityConfigurationName="">
  <serviceCertificate>
    <certificateReference x509FindType="FindBySubjectName" findValue="localhost" storeLocation="LocalMachine" storeName="My"/>
  </serviceCertificate>
  <wsFederation passiveRedirectEnabled="true" issuer="http://localhost:62398/" realm ="http://localhost:19851/" requireHttps="false" />
  <cookieHandler mode="Default" requireSsl="false">
    <chunkedCookieHandler chunkSize="2000"/>
  </cookieHandler>
</federationConfiguration>
</system.identityModel.services>

上述配置中：
audienceUris 标签指定依赖方应用的URL;
securityTokenHandlers 标签指定处理token 的类和方法，可以使用自定义的方法或内建的方法；
issuerNameRegistry标签指定token 处理程序使用的颁发者；
配置完成后，访问依赖方应用需要身份认证的页面时会跳转至STS进行登录操作。

小结

用户授权认证是大多数应用程序都需要经过的流程，目前各种框架种类众多，基于声明的模型中用户身份由一组声明表示，通过配置一个受信任的外部身份系统为我们自己的应用程序提供关于用户的所有必要信息，在这种模型下，单点登录也能较为简单的实现，应用程序本身不处理任何用户认证相关的逻辑，并且不需要保存用户账户和密码等数据，也不用主动查询用户的详细信息，只需从受信任的令牌发布程序接受安全令牌即可。一个新的应用依赖自定义的STS进行身份认证和授权也只需要简单的配置。

发表于 |

使用Travis进行持续集成，会自动配置webhook，在push完成之后执行既定操作。

  1. 直接使用Github账号登录Travis， 勾选需要持续集成的代码库；
  2. 在项目根目录添加.travis.yml文件：
    1
    2
    3
    4
    5
    6
    7
    language: python
    python:
      - "3.6"
    install:
      - pip install -r requirements.txt
    script:
      - pytest

push代码到代码库之后脚本自动执行，在Travis可以看到执行日志；

异常情况：

  • 运行测试出错，提示找不到模块，ModuleNotFoundError: No module named ‘blockchain’
    • 在tests目录增加空的init.py 文件
  • 运行测试出错，提示找不到文件，FileNotFoundError: [Errno 2] No such file or directory: ‘../src/sites.json’
    • TODO

注：TravisCI不支持MSTest，因为MSTest只能在Windows下运行，而目前Travis只在Linux 或者OSX上通过Mono或.Net Core runtime构建C#项目；

在README.md文件增加以下内容，显示构建徽章；
[![Build Status](https://www.travis-ci.org/VincentGau/pythonScripts.svg?branch=master)](https://www.travis-ci.org/VincentGau/pythonScripts)

发表于 |

Python版本

目前python有两个大版本，Python 2 和Python 3， 这两个版本互不兼容，除了语法上的差异，一些Python 2 的类库没有对应的Python 3 版本，在Python 3中无法使用，Python 3类库也可能不能用在Python 2 中。鉴于python 社区更关注Python 3 的特性和提升，针对Python 2 的更新范围包括bug修复与安全更新，，并且越来越多的开发者企业逐渐放弃对Python 2 的支持，对于新项目Python 3 是一个更长远的选择。不过有虚拟环境的支持，使用不同版本的python也不是问题。
安装python的时候默认的解释器是使用C语言开发的CPython，它编译python代码生成字节码然后执行，同样流行的还有JPython（Java），IronPython（.Net），PyPy（python）这些实现，其中CPython的使用更广泛。

阅读全文 »