- },
- {
- "cell_type": "code",
- "collapsed": false,
- "input": [
- "class PlayerAdaptive:\n",
- " def __init__(self, words):\n",
- " self.candidate_words = words\n",
- " \n",
- " def guess(self, discovered, missed, lives):\n",
- " self.filter_candidate_words(discovered, missed)\n",
- " self.set_ordered_letters()\n",
- " return [l for l in self.ordered_letters if l not in discovered + missed][0]\n",
- " \n",
- " def filter_candidate_words(self, discovered, missed):\n",
- " pass\n",
- " \n",
- " def set_ordered_letters(self):\n",
- " counts = collections.Counter(l.lower() \n",
- " for l in ''.join(self.candidate_words) + string.ascii_lowercase \n",
- " if l in string.ascii_letters)\n",
- " self.ordered_letters = [p[0] for p in counts.most_common()]\n",
- "\n",
- " def match(self, pattern, target, excluded=None):\n",
- " if not excluded:\n",
- " excluded = ''\n",
- " if len(pattern) != len(target):\n",
- " return False\n",
- " for m, c in zip(pattern, target):\n",
- " if m == '_' and c not in excluded:\n",
- " # true\n",
- " pass\n",
- " elif m != '_' and m == c:\n",
- " # true\n",
- " pass\n",
- " else:\n",
- " return False\n",
- " return True "
- ],
- "language": "python",
- "metadata": {},
- "outputs": [],
- "prompt_number": 39
- },
- {
- "cell_type": "code",
- "collapsed": false,
- "input": [
- "class PlayerAdaptiveLength(PlayerAdaptive):\n",
- " def __init__(self, words):\n",
- " super().__init__(words)\n",
- " self.word_len = None\n",
- " self.ordered_letters = None\n",
- " \n",
- " def filter_candidate_words(self, discovered, missed):\n",
- " if not self.word_len:\n",
- " self.word_len = len(discovered)\n",
- " self.candidate_words = [w for w in self.candidate_words if len(w) == self.word_len]\n",
- " \n",
- " def set_ordered_letters(self):\n",
- " if not self.ordered_letters:\n",
- " super().set_ordered_letters()"
- ],
- "language": "python",
- "metadata": {},
- "outputs": [],
- "prompt_number": 40
- },
- {
- "cell_type": "code",
- "collapsed": false,
- "input": [
- "class PlayerAdaptiveIncludedLetters(PlayerAdaptive):\n",
- " def filter_candidate_words(self, discovered, missed):\n",
- " self.candidate_words = [w for w in self.candidate_words if self.match(discovered, w)]"
- ],
- "language": "python",
- "metadata": {},
- "outputs": [],
- "prompt_number": 41
- },
- {
- "cell_type": "code",
- "collapsed": false,
- "input": [
- "class PlayerAdaptiveExcludedLetters(PlayerAdaptive):\n",
- " def filter_candidate_words(self, discovered, missed):\n",
- " if missed:\n",
- " empty_target = '_' * len(discovered)\n",
- " self.candidate_words = [w for w in self.candidate_words if self.match(empty_target, w, missed)] "
- ],
- "language": "python",
- "metadata": {},
- "outputs": [],
- "prompt_number": 42
- },
- {
- "cell_type": "code",
- "collapsed": false,
- "input": [
- "class PlayerAdaptivePattern(PlayerAdaptive):\n",
- " def filter_candidate_words(self, discovered, missed):\n",
- " attempted_letters = [l for l in discovered if l != '_'] + missed\n",
- " self.candidate_words = [w for w in self.candidate_words if self.match(discovered, w, attempted_letters)]"
- ],
- "language": "python",
- "metadata": {},
- "outputs": [],
- "prompt_number": 43
- },
- {
- "cell_type": "code",
- "collapsed": false,
- "input": [
- "%%timeit\n",
- "\n",
- "wins = 0\n",
- "for _ in range(1000):\n",
- " g = Game(random.choice(WORDS), player=PlayerAdaptiveLength(WORDS))\n",
- " g.play_game()\n",
- " if g.game_won:\n",
- " wins += 1\n",
- "print(wins)"
- ],
- "language": "python",
- "metadata": {},
- "outputs": [
- {
- "output_type": "stream",
- "stream": "stdout",
- "text": [
- "472\n",
- "460"
- ]
- },
- {
- "output_type": "stream",
- "stream": "stdout",
- "text": [
- "\n",
- "462"
- ]
- },
- {
- "output_type": "stream",
- "stream": "stdout",
- "text": [
- "\n",
- "484"
- ]
- },
- {
- "output_type": "stream",
- "stream": "stdout",
- "text": [
- "\n",
- "1 loops, best of 3: 17 s per loop\n"
- ]
- }
- ],
- "prompt_number": 44
- },
- {
- "cell_type": "code",
- "collapsed": false,
- "input": [
- "%%timeit\n",
- "\n",
- "wins = 0\n",
- "for _ in range(1000):\n",
- " g = Game(random.choice(WORDS), player=PlayerAdaptiveIncludedLetters(WORDS))\n",
- " g.play_game()\n",
- " if g.game_won:\n",
- " wins += 1\n",
- "print(wins)"
- ],
- "language": "python",
- "metadata": {},
- "outputs": [
- {
- "output_type": "stream",
- "stream": "stdout",
- "text": [
- "988\n",
- "985"
- ]
- },
- {
- "output_type": "stream",
- "stream": "stdout",
- "text": [
- "\n",
- "987"
- ]
- },
- {
- "output_type": "stream",
- "stream": "stdout",
- "text": [
- "\n",
- "988"
- ]
- },
- {
- "output_type": "stream",
- "stream": "stdout",
- "text": [
- "\n",
- "1 loops, best of 3: 49.3 s per loop\n"
- ]
- }
- ],
- "prompt_number": 45
- },
- {
- "cell_type": "code",
- "collapsed": false,
- "input": [
- "%%timeit\n",
- "\n",
- "wins = 0\n",
- "for _ in range(1000):\n",
- " g = Game(random.choice(WORDS), player=PlayerAdaptiveExcludedLetters(WORDS))\n",
- " g.play_game()\n",
- " if g.game_won:\n",
- " wins += 1\n",
- "print(wins)"
- ],
- "language": "python",
- "metadata": {},
- "outputs": [
- {
- "output_type": "stream",
- "stream": "stdout",
- "text": [
- "575\n",
- "611"
- ]
- },
- {
- "output_type": "stream",
- "stream": "stdout",
- "text": [
- "\n",
- "583"
- ]
- },
- {
- "output_type": "stream",
- "stream": "stdout",
- "text": [
- "\n",
- "607"
- ]
- },
- {
- "output_type": "stream",
- "stream": "stdout",
- "text": [
- "\n",
- "1 loops, best of 3: 5min 10s per loop\n"
- ]
- }
- ],
- "prompt_number": 46
- },
- {
- "cell_type": "code",
- "collapsed": false,
- "input": [
- "%%timeit\n",
- "\n",
- "wins = 0\n",
- "for _ in range(1000):\n",
- " g = Game(random.choice(WORDS), player=PlayerAdaptivePattern(WORDS))\n",
- " g.play_game()\n",
- " if g.game_won:\n",
- " wins += 1\n",
- "print(wins)"
- ],
- "language": "python",
- "metadata": {},
- "outputs": [
- {
- "output_type": "stream",
- "stream": "stdout",
- "text": [
- "990\n",
- "992"
- ]
- },
- {
- "output_type": "stream",
- "stream": "stdout",
- "text": [
- "\n",
- "995"
- ]
- },
- {
- "output_type": "stream",
- "stream": "stdout",
- "text": [
- "\n",
- "991"
- ]
- },
- {
- "output_type": "stream",
- "stream": "stdout",
- "text": [
- "\n",
- "1 loops, best of 3: 39.1 s per loop\n"
- ]
- }
- ],
- "prompt_number": 47
- },
- {
- "cell_type": "code",
- "collapsed": false,
- "input": [
- "for _ in range(1000):\n",
- " g = Game(random.choice(WORDS), player=PlayerAdaptivePattern(WORDS))\n",
- " g.play_game()\n",
- " if not g.game_won:\n",
- " print(g.target, g.discovered, g.wrong_letters)"
- ],
- "language": "python",
- "metadata": {},
- "outputs": [
- {
- "output_type": "stream",
- "stream": "stdout",
- "text": [
- "puffy ['p', 'u', '_', '_', 'y'] ['s', 'e', 'a', 'o', 'i', 'm', 'l', 'n', 'r', 't']\n",
- "jar"
- ]
- },
- {
- "output_type": "stream",
- "stream": "stdout",
- "text": [
- " ['_', 'a', 'r'] ['t', 'p', 'g', 'w', 'd', 'm', 'b', 'y', 'f', 'o']\n",
- "fate"
- ]
- },
- {
- "output_type": "stream",
- "stream": "stdout",
- "text": [
- " ['_', 'a', '_', 'e'] ['l', 'r', 'm', 'p', 's', 'g', 'd', 'k', 'v', 'b']\n",
- "robs"
- ]
- },
- {
- "output_type": "stream",
- "stream": "stdout",
- "text": [
- " ['_', 'o', 'b', 's'] ['e', 'a', 't', 'h', 'g', 'f', 'l', 'c', 'm', 'j']\n"
- ]
- }
- ],
- "prompt_number": 48
- },
- {
- "cell_type": "markdown",
- "metadata": {},
- "source": [
- "##Better strategy 6: divide and conquer\n",
- "This is a general approach to solving big problems: divide the candidate set into two equal halves, so that a simple test can discard half the candidates. \n",
- "\n",
- "For Hangman, we want to guess the letter that will eliminate half the `candidate_words`. For each letter that's present in all of the candidate words, score the letter +1 for every word it appears in, and -1 for every word it doesn't appear in. The closer the total is to zero, the closer letter is to being in half the `candidate_words`. We then pick the unguesses letter with the score closest to zero.\n",
- "\n",
- "As the `PlayerAdaptivePattern` seems to work well, we'll use that to keep track of the `candidate_words`. This variant changes the order of the letters, so it's a rewrite of `set_ordered_letters()`."