Industry X.0
AI 是個很有趣的領域，他充滿了各種數學理論以及演算法。AI 對我來說就是一種策略 (Strategy) 上的一種方式：如何根據數學模型與演算法，決定接下來的行動。 用踩地雷 (Minesweeper) 0 為例，就可以發展出若干種策略來進行遊戲
全亂數
最簡單也是最無效的策略就是全亂數的決策方式：這種決策方式表示不考慮任何已知的情報， 用隨機的方式決定接下來的行動。在 Minesweeper 的例子中，可以使用 random 函數中的 choice 來隨機選取目前未知的可能性 (safeStep)。因為不考慮任何已知的情報， 故可以快速地估算出成功的機率約為 $\prod_{k=0}^{S-n}\frac{S-n-k}{S-k}$_。
在 S=289、n=18 的情況下，成功的機率約為 $5.6 * 10^{-29}$。 在 S=49、n=5 的情況下，成功的機率約為 $5.2 * 10^{-7}$。 然而在實際運作中，我們可以先排除掉已經知道的結果，所以機率會比估算值還要高。在 AlgoFullRandom 的情況下，大約有 6% 的機率可以獲勝 (4/49/500 round)。
class AI(object):
def AlgoFullRandom(cls, debug=False):
import random
agent = Minesweeper(1, 1, cls.size)
while len(agent):
if debug:
print agent
agent.step(*random.choice(agent.safeStep))
基本策略
基本策略表示我們會參考到目前已知的線索，而非利用全亂數的方式來實作策略：在這個策略中， 我們計算預計觸發的位子中，附近八格的已知線索來計算這個位子是炸彈的機率。 計算的方式利用 $\frac{未知的位子}{已知的炸彈數}$ 來計算機率。根據這個策略， 我們可以獲得遠高於全亂數的結果：在 (4/49/500 round) 的情況下，我們獲勝的機率已經高達 7 成， 更嚴苛的 (11/121/500 round) 的情況下，也有 27% 的獲勝機會。
def AlgoSimpleStrategy(cls, debug=False, default=0.3):
def ratio(cls, x, y):
fn = lambda x, y: cls[x, y]/float(cls.empty(x, y))
nr = [[_x, _y] for _x in range(x-1, x+2) for _y in (y-1, y+1) if 0 < cls[_x, _y]]
nr += [[_x, y] for _x in (x-1, x+1) if 0 < cls[_x, y]]
if nr:
return max([fn(*_) for _ in nr])
else:
return default
agent = Minesweeper(1, 1, cls.size, debug=debug)
while len(agent):
if debug: print agent, len(agent)
steps = [[_, ratio(agent, *_)] for _ in agent.safeStep]
steps = sorted(steps, key=lambda x: x[1])
agent.step(*steps[0][0])
Minesweeper Sample Code
class Minesweeper(object):
'''
>>> for _ in range(100):
... agent = Minesweeper(1, 1, debug=True)
'''
def __init__(cls, x, y, size=16, ratio=0.1, debug=False):
from random import randint
cls.size, cls.debug = size, debug
cls._board_ = [['_' for w in range(size)] for h in range(size)]
bomb = int(ratio*size**2)
while 0 != bomb:
pos = [randint(0, size-1) for _ in range(2)]
if pos == [x, y]:
continue
cls._board_[pos[0]][pos[1]] = 'X'
bomb -= 1
cls.step(x, y)
def __str__(cls, hidden=True):
FMT = '{0} {1}{0}' ## Board, data
s = cls.size
header = ['{0}-'.format('-' if 0 != idx%5 else idx%10) for idx in range(cls.size)]
header = FMT.format('+', ''.join(header))
data = [['_ ' if hidden and 'X' == _ else '{0} '.format(_) for _ in line] for line in cls._board_]
data = [''.join(line) for line in data]
data = [FMT.format('|' if 0 != idx%5 else '{0}'.format(idx%10), line) for idx, line in enumerate(data)]
data = '\n'.join(data)
return '{0}\n{1}\n{0}'.format(header, data)
def __call__(cls):
try:
nr = len(cls.safeStep)
while len(cls) != nr:
print agent
try:
x, y = raw_input('{0} / {1}> '.format(len(cls), nr)).split()
except Exception as e:
continue
cls.step(int(x), int(y))
nr = len(cls.safeStep)
print 'Win'
except KeyboardInterrupt as e:
print 'Ctrl+C'
def __len__(cls):
if not hasattr(cls, "bombs"):
cls.bombs = sum([1 for line in cls._board_ for _ in line if 'X' == _])
return len(cls.safeStep) - cls.bombs
def __getitem__(cls, args):
x, y = args
def _fn_(x):
if x.isdigit():
return int(x)
elif '_' == x or 'X' == x:
return -1
elif ' ' == x:
return 0
else:
raise IOError('[{0}]'.format(x))
if 0 <= x < cls.size and 0 <= y < cls.size:
return _fn_(cls._board_[x][y])
else:
return 0
@property
def safeStep(cls):
if not hasattr(cls, '_safeStep_'):
_safeStep_ = [[x, y] for x in range(cls.size) for y in range(cls.size) if 0 > cls[x, y]]
_safeStep_ = [[x, y] for x, y in _safeStep_ if 0 > cls[x, y]]
return _safeStep_
def empty(cls, x, y):
nr = [1 for _x in range(x-1, x+2) for _y in (y-1, y+1) if 0 > cls[_x, _y]]
nr += [1 for _x in (x-1, x+1) if 0 > cls[_x, y]]
return sum(nr)
def check(cls, x, y):
if x < 0 or x >= cls.size or y <0 or y >= cls.size:
return False
return 'X' == cls._board_[x][y]
def step(cls, x, y):
if 0 == cls._step_(x, y):
for _x in range(x-1, x+2):
for _y in range(y-1, y+2):
if [_x, _y] == [x, y]:
continue
cls.step(_x, _y)
def _step_(cls, x, y):
if x < 0 or x >= cls.size or y <0 or y >= cls.size:
''' Out-of boundary'''
return -1
elif 'X' == cls._board_[x][y]:
cls._board_[x][y] = '@'
if cls.debug:
print cls.__str__(False)
raise IOError("Bomb")
elif 0 <= cls[x, y]:
''' Already done '''
return -1
else:
cnt = [cls.check(_x, _y) for _x in range(x-1, x+2) for _y in range(y-1, y+2)]
cnt = sum(cnt)
if cnt:
cls._board_[x][y] = str(cnt)
else:
cls._board_[x][y] = ' '
return cnt