Category name:Python

MasterMind(bulls and cows)

10/19/2014 / No Comments

Mastermind很经典的一个小游戏,有各种不同的版本,这边就介绍一个猜数字的版本。
在这个游戏中有两个角色,一个是code maker,另外一个是code breaker。游戏开始时,code maker提供一个secret code(4 non-repeated digitals),然后breaker就开始猜,code maker会对code breaker的guess进行评估,并给出相应的feedback:xAyB,x代表位置和数值都猜对的数量,y代表数值猜对但位置猜错的数量。假设secret是’2345′,guess是’3275’,对应的feedback就是1A2B,1代表数字5,2代表数字2和3.
分析:secret code为0-9的4位排列,所以共有10*9*8*7=5040种情况。初始时secret有5040种可能,然后我们逐步通过每次的feedback将错误的code去掉,直到我们剩下一个code,这个code就是我们的secret code.
code set = all 5040 codes
如果利用feedback去掉错误code,假如一个code与guess的feedback与secret和guess的feedback不相同,那么这个code肯定不是secret code。
if feedback(guess, code) != feedback(guess, secret): remove code from code set.
然后我们在code set中随便选一个code作为我们的下一个guess,直到猜对为止。
这种方法也是最蠢的方法,worst case需要9步才能猜对。但是我们班的老美竟然还有很多average都是20多步的,真是醉了。

这个问题其实也算是一个搜索问题,和下象棋差不多。在搜索问题中有一种很经典的方法,叫做启发式(Heuristic),启发式其实可以理解为评估式,这种方法有一个启发方程(Heuristic Function)用来对当前状态的每一个successor进行评估。在mastermind中,启发方程就会对我们所有可选的guess进行评估,然后选取最好的guess.
那么在mastermind中,如何定义好与不好。最直观的定义就是我们选取这个值作为guess,可以去掉多少错误的code。
目前我研究过两种效果不错的评估方法,一种是minimal maximal subset size,另外种就是subset number。
minimal maximal subset size:
这种方法实际上是利用了minimax的思想,如果我们选择一个值的话,使用这种选择最坏的后果去对这次选择做出评估(做出这个选择最糟糕的后果是什么),然后我们在所有的选择中选择最不糟糕的(无期总好过死刑吧)。每一个guess都能将code set划分成很多个feedback相同的subset,secret可能在subset中的任何一个,因为我们要做最坏的打算,所以最坏的情况下我们的code就在这个最大subset中。然后在所有的code中,我们选择maximal subset size最小的作为下一个guess。

另一种其实可以理解为期望subset size,因为所有subset size的总和是一样的,等于code set的大小。subset size的期望值就等于subset size的总和除以subset的数量。

Missionaries and cannibals problem

10/11/2014 / No Comments

最近爱上了python,作业好多,没时间刷题了。
Missionaries and cannibals problem,also known as jealous husbands problem。
这个问题是一个很经典的AI问题,搜索问题。
问题是,有三个传教士和三个食人族在一条河的左边,有一条能载客两人的船,当食人族的数量超过传教士的时候,传教士就会被吃掉,现在要求如何将传教士和食人族安全的运到对岸。
问题分析:搜索问题一般有以下几个组成部分。
状态空间(state space)
转换方程(successor function)
初始状态(initial state)
目标(goal)
从开始状态开始,依次执行以下步骤:
1.判断当前状态是否为目标状态
2.若当前状态不是目标状态,将当前状态标记为已访问
3.通过转换方程计算出当前状态的有效(是否已访问,传教士是否会被吃掉)后续状态集
4.依次访问后续状态

使用一个五元组来表示当前环境的状态,(canLeft, missLeft, boat, canRight, missRight)依次为(左岸食人族数量,左岸传教士数量,船的位置,右岸食人族数量,右岸传教士数量)
转换方程,首先判断船的位置,如果船在左岸,后续状态为:
(canLeft – 1, missLeft, ‘right’, canRight + 1, missRight)
(canLeft – 2, missLeft, ‘right’, canRight + 2, missRight)
(canLeft – 1, missLeft – 1, ‘right’, canRight + 1, missRight + 1)
(canLeft, missLeft – 1, ‘right’, canRight, missRight + 1)
(canLeft, missLeft – 2, ‘right’, canRight, missRight + 2)

如果船在右岸,后续状态为:
(canLeft + 1, missLeft, ‘left’, canRight – 1, missRight)
(canLeft + 2, missLeft, ‘left’, canRight – 2, missRight)
(canLeft + 1, missLeft + 1, ‘left’, canRight – 1, missRight – 1)
(canLeft, missLeft + 1, ‘left’, canRight, missRight – 1)
(canLeft, missLeft + 2, ‘left’, canRight, missRight – 2)

依次判断这十个状态是否有效 if state not in visited and if state.isValid(),有一种特殊情况,就是目标状态,由于到达目标状态的路径可能有多个,所以要特殊处理if (state not in visited or state.isGoal()) and state.isValid()
将有效的状态添加到后续状态集

代码没怎么注释,但是应该很容易就懂了。