Parking Site

A castle on the cloud.

0%

拼字游戏Scrabble：人类cf计算机

Posted on Edited on In

项目简介

本项目中包括两个版本的简单拼字文字游戏。

前一版本中，我们让由人类玩家参与游戏过程，后者则交给计算机来执行设定的游戏策略。

这种拼字游戏的完成版就是常在报纸上见到的填字游戏，欧美国家的游客在旅途上似乎非常喜欢这个游戏。

Version1：人类玩家版本

编程策略上，我们将大的模块分解成功能清晰且小的函数，这将便于测试和调试。

首先我们可以完成辅助性的函数模块：

辅助性模块

  1. loadWords()
  2. getFrequencyDict(sequence)

它们分别用来读取词库、将列表中的字母按照 字母 和 频次 进行输出

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
def loadWords():
    """
    Returns a list of valid words. Words are strings of lowercase letters.
    
    Depending on the size of the word list, this function may
    take a while to finish.
    """
    print("Loading word list from file...")
    # inFile: file
    inFile = open(WORDLIST_FILENAME, 'r')
    # wordList: list of strings
    wordList = []
    for line in inFile:
        wordList.append(line.strip().lower())
    print("  ", len(wordList), "words loaded.")
    return wordList

def getFrequencyDict(sequence):
    """
    Returns a dictionary where the keys are elements of the sequence
    and the values are integer counts, for the number of times that
    an element is repeated in the sequence.

    sequence: string or list
    return: dictionary
    """
    # freqs: dictionary (element_type -> int)
    freq = {}
    for x in sequence:
        freq[x] = freq.get(x,0) + 1
    return freq

基本函数

getWordScore(word, n) ，用于计算在本次拼字尝试中的得分

计算得分的规则为：
score = 总和（字母分值）* 长度 + bonus（50）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def getWordScore(word, n):
    """
    Returns the score for a word. Assumes the word is a valid word.

    The score for a word is the sum of the points for letters in the
    word, multiplied by the length of the word, PLUS 50 points if all n
    letters are used on the first turn.

    Letters are scored as in Scrabble; A is worth 1, B is worth 3, C is
    worth 3, D is worth 2, E is worth 1, and so on (see SCRABBLE_LETTER_VALUES)

    word: string (lowercase letters)
    n: integer (HAND_SIZE; i.e., hand size required for additional points)
    returns: int >= 0
    """
    # 
    score = 0
    for elm in word:
        score += SCRABBLE_LETTER_VALUES[elm]
    score *= len(word)
    if len(word) == n:
        score += 50
    return score

displayHand(hand)，对当前拼字尝试在控制台上进行输出，便于游戏玩家查看

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def displayHand(hand):
    """
    Displays the letters currently in the hand.

    For example:
    >>> displayHand({'a':1, 'x':2, 'l':3, 'e':1})
    Should print out something like:
       a x x l l l e
    The order of the letters is unimportant.

    hand: dictionary (string -> int)
    """
    for letter in hand.keys():
        for j in range(hand[letter]):
             print(letter,end=" ")       # print all on the same line
    print()                             # print an empty line

dealHand(n) 随机生成新一轮拼字的题目，即乱序的字母，需要包含一定的元音

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def dealHand(n):
    """
    Returns a random hand containing n lowercase letters.
    At least n/3 the letters in the hand should be VOWELS.

    Hands are represented as dictionaries. The keys are
    letters and the values are the number of times the
    particular letter is repeated in that hand.

    n: int >= 0
    returns: dictionary (string -> int)
    """
    hand={}
    numVowels = n // 3
    
    for i in range(numVowels):
        x = VOWELS[random.randrange(0,len(VOWELS))]
        hand[x] = hand.get(x, 0) + 1
        
    for i in range(numVowels, n):    
        x = CONSONANTS[random.randrange(0,len(CONSONANTS))]
        hand[x] = hand.get(x, 0) + 1
        
    return hand

updateHand(hand, word)

用于在下一轮拼字猜测之前，删除上一轮已被成功使用过的字母。遗留在字典中的字母可以输出，以提示用户

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def updateHand(hand, word):
    """
    Assumes that 'hand' has all the letters in word.
    In other words, this assumes that however many times
    a letter appears in 'word', 'hand' has at least as
    many of that letter in it. 

    Updates the hand: uses up the letters in the given word
    and returns the new hand, without those letters in it.

    Has no side effects: does not modify hand.

    word: string
    hand: dictionary (string -> int)    
    returns: dictionary (string -> int)
    """
    # TO DO ... <-- Remove this comment when you code this function
    new = hand.copy()
    for letter in word:
        new[letter] -= 1
    return new

isValidWord(word, hand, wordList)

验证拼字时的猜测是否能构成有效的单词。 预先以及提供了一份有效单词的列表，存储在wordList中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def isValidWord(word, hand, wordList):
    """
    Returns True if word is in the wordList and is entirely
    composed of letters in the hand. Otherwise, returns False.

    Does not mutate hand or wordList.
   
    word: string
    hand: dictionary (string -> int)
    wordList: list of lowercase strings
    """
    # TO DO ... <-- Remove this comment when you code this function
    if word not in wordList:
        return False
    for a in word:
        if hand.get(a,0) < getFrequencyDict(word)[a]:
            return False
    return True

这个函数也可以直接用一行写完。但似乎在可读性和效率上，也没有一行写完的必要？

1
2
# 2rd solution : one line 
# return word in wordList and all(hand.get(a, 0) >= b for a, b in getFrequencyDict(word).items())

calculateHandlen(hand)

计算拼字猜测中，总计包含的字母数量

1
2
3
4
5
6
7
8
9
10
11
12
def calculateHandlen(hand):
    """ 
    Returns the length (number of letters) in the current hand.
    
    hand: dictionary (string-> int)
    returns: integer
    """
    # TO DO... <-- Remove this comment when you code this function
    sum = 0
    for i in range(len(hand.keys())):
        sum += list(hand.values())[i]
    return sum

这个比较适合一行写完

1
2
# 2rd solution:
# return sum(x for x in hand.values())

进入正题

playHand(hand, wordList, n)

包含：

  • 一轮猜测中所需要处理的交互（用户输入、控制台输出）
  • 控制流程
  • 计算得分
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
50
51
52
53
54
def playHand(hand, wordList, n):
    """
    Allows the user to play the given hand, as follows:

    * The hand is displayed.
    * The user may input a word or a single period (the string ".") 
      to indicate they're done playing
    * Invalid words are rejected, and a message is displayed asking
      the user to choose another word until they enter a valid word or "."
    * When a valid word is entered, it uses up letters from the hand.
    * After every valid word: the score for that word is displayed,
      the remaining letters in the hand are displayed, and the user
      is asked to input another word.
    * The sum of the word scores is displayed when the hand finishes.
    * The hand finishes when there are no more unused letters or the user
      inputs a "."

      hand: dictionary (string -> int)
      wordList: list of lowercase strings
      n: integer (HAND_SIZE; i.e., hand size required for additional points)
      
    """
    score = 0
    # As long as there are still letters left in the hand:
    while calculateHandlen(hand) > 0:
        # Display the hand
        print("Current Hand:",end = ' ')
        displayHand(hand)
        # Ask user for input
        newin = input("Enter word, or a '.' to indicate that you are finished: ")
        # If the input is a single period:
        if newin == ".":
            # End the game (break out of the loop)
            break
        # Otherwise (the input is not a single period):
        else:
            # If the word is not valid:
            if isValidWord(newin, hand, wordList) == False:
                # Reject invalid word (print a message followed by a blank line)
                print("Invalid word, please try again.")
            # Otherwise (the word is valid):
            else:
                # Tell the user how many points the word earned, and the updated total score, in one line followed by a blank line
                current_score = getWordScore(newin, n)
                score += current_score
                print(newin + " earned " + str
                      (current_score) + " points. Total: " + str(score))
                # Update the hand 
                hand = updateHand(hand, newin)
    # Game is over (user entered a '.' or ran out of letters), so tell user the total score
    if newin == '.':
        print('Goodbye! Total score:', score, 'points.')
    else:
        print('Run out of letters. Total score:', score, 'points.')

playGame(wordList) 正式游戏开始

主要包含一些用户与计算机的交互操作：

  • 继续游戏？
  • 重新开始？
  • 结束游戏？
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
def playGame(wordList):
    """
    Allow the user to play an arbitrary number of hands.

    1) Asks the user to input 'n' or 'r' or 'e'.
      * If the user inputs 'n', let the user play a new (random) hand.
      * If the user inputs 'r', let the user play the last hand again.
      * If the user inputs 'e', exit the game.
      * If the user inputs anything else, tell them their input was invalid.
 
    2) When done playing the hand, repeat from step 1    
    """
    n = HAND_SIZE
    hand= {}
    while True:
        choice = input("Enter n to deal a new hand, r to replay the last hand, or e to end game: ")
        if choice == 'r':
            if not hand:
                print('You have not played a hand yet. Please play a new hand first!')
            else:
                playHand(hand, wordList, n)
        elif choice == 'n':
            hand = dealHand(n)
            playHand(hand, wordList, n)
        elif choice == 'e':
             break
        else:
            print("Invalid command.")

游戏主程序

导入需要的库、进行全局变量的定义

1
2
3
4
5
6
7
8
9
10
11
12
import random
import string

VOWELS = 'aeiou'
CONSONANTS = 'bcdfghjklmnpqrstvwxyz'
HAND_SIZE = 7

SCRABBLE_LETTER_VALUES = {
    'a': 1, 'b': 3, 'c': 3, 'd': 2, 'e': 1, 'f': 4, 'g': 2, 'h': 4, 'i': 1, 'j': 8, 'k': 5, 'l': 1, 'm': 3, 'n': 1, 'o': 1, 'p': 3, 'q': 10, 'r': 1, 's': 1, 't': 1, 'u': 1, 'v': 4, 'w': 4, 'x': 8, 'y': 4, 'z': 10
}

WORDLIST_FILENAME = "words.txt"

进行程序的执行

1
2
3
4
5
# Build data structures used for entire session and play game
#
if __name__ == '__main__':
    wordList = loadWords()
    playGame(wordList)
Loading word list from file...
   83667 words loaded.
Enter n to deal a new hand, r to replay the last hand, or e to end game: e

测试样例

已通过单元测试和整体测试，篇幅关系不再赘述

Version2 ：计算机玩家版本

计算机版本中，辅助性函数和基本函数没有改变，仅在游戏交互和流程上多了一些内容。

用户可以选择是否由计算机执行拼字操作。

由此，我们能够观察到最终策略导致的得分差异。

导入需要的模块

1
2
from ps4a import *
import time

基本策略部分

版本 2 中 ，我们还需要在版本 1 的基础上写全新的计算机处理的基本策略部分。

分为 ** compChooseWord(hand, wordList, n) ** 和** compPlayHand(hand, wordList, n)** 两部分

compChooseWord(hand, wordList, n)

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
def compChooseWord(hand, wordList, n):
    """
    Given a hand and a wordList, find the word that gives 
    the maximum value score, and return it.

    This word should be calculated by considering all the words
    in the wordList.

    If no words in the wordList can be made from the hand, return None.

    hand: dictionary (string -> int)
    wordList: list (string)
    n: integer (HAND_SIZE; i.e., hand size required for additional points)

    returns: string or None
    """
    # Create a new variable to store the maximum score seen so far (initially 0)
    bestScore = 0
    # Create a new variable to store the best word seen so far (initially None)  
    bestWord = None
    # For each word in the wordList
    for word in wordList:
        # If you can construct the word from your hand
        if isValidWord(word, hand, wordList):
            # find out how much making that word is worth
            score = getWordScore(word, n)
            # If the score for that word is higher than your best score
            if (score > bestScore):
                # update your best score, and best word accordingly
                bestScore = score
                bestWord = word
    # return the best word you found
    return bestWord

compPlayHand(hand, wordList, n)函数

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
50
def compPlayHand(hand, wordList, n):
    """
    Allows the computer to play the given hand, following the same procedure
    as playHand, except instead of the user choosing a word, the computer 
    chooses it.

    1) The hand is displayed.
    2) The computer chooses a word.
    3) After every valid word: the word and the score for that word is 
    displayed, the remaining letters in the hand are displayed, and the 
    computer chooses another word.
    4)  The sum of the word scores is displayed when the hand finishes.
    5)  The hand finishes when the computer has exhausted its possible
    choices (i.e. compChooseWord returns None).
 
    hand: dictionary (string -> int)
    wordList: list (string)
    n: integer (HAND_SIZE; i.e., hand size required for additional points)
    """
    # Keep track of the total score
    totalScore = 0
    # As long as there are still letters left in the hand:
    while (calculateHandlen(hand) > 0) :
        # Display the hand
        print("Current Hand: ", end=' ')
        displayHand(hand)
        # computer's word
        word = compChooseWord(hand, wordList, n)
        # If the input is a single period:
        if word == None:
            # End the game (break out of the loop)
            break
            
        # Otherwise (the input is not a single period):
        else :
            # If the word is not valid:
            if (not isValidWord(word, hand, wordList)) :
                print('This is a terrible error! I need to check my own code!')
                break
            # Otherwise (the word is valid):
            else :
                # Tell the user how many points the word earned, and the updated total score 
                score = getWordScore(word, n)
                totalScore += score
                print('"' + word + '" earned ' + str(score) + ' points. Total: ' + str(totalScore) + ' points')              
                # Update hand and show the updated hand to the user
                hand = updateHand(hand, word)
                print()
    # Game is over (user entered a '.' or ran out of letters), so tell user the total score
    print('Total score: ' + str(totalScore) + ' points.')

主程序部分

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
50
51
52
53
54
55
56
57
58
59
60
def playGame(wordList):
    """
    Allow the user to play an arbitrary number of hands.
 
    1) Asks the user to input 'n' or 'r' or 'e'.
        * If the user inputs 'e', immediately exit the game.
        * If the user inputs anything that's not 'n', 'r', or 'e', keep asking them again.

    2) Asks the user to input a 'u' or a 'c'.
        * If the user inputs anything that's not 'c' or 'u', keep asking them again.

    3) Switch functionality based on the above choices:
        * If the user inputted 'n', play a new (random) hand.
        * Else, if the user inputted 'r', play the last hand again.
      
        * If the user inputted 'u', let the user play the game
          with the selected hand, using playHand.
        * If the user inputted 'c', let the computer play the 
          game with the selected hand, using compPlayHand.

    4) After the computer or user has played the hand, repeat from step 1

    wordList: list (string)
    """
    # TO DO... <-- Remove this comment when you code this function
    # print("playGame not yet implemented.") # <-- Remove this when you code this function
    n = HAND_SIZE
    hand= {}
    while True:
        choice = input("Enter n to deal a new hand, r to replay the last hand, or e to end game: ")
        if choice == 'n':
            hand = dealHand(n)
            while True:
                who = input("Enter u to have yourself play, c to have the computer play: ")
                if who not in ['u','c']:
                    print('Invalid command.')
                else:
                    break
            if who == 'u':
                playHand(hand, wordList, n)
            else:
                compPlayHand(hand, wordList, n)
        elif choice == 'e':
            break
        elif choice == 'r':
            if not hand:
                print('You have not played a hand yet. Please play a new hand first!')
            else:
                while True:
                    who = input("Enter u to have yourself play, c to have the computer play: ")
                    if who not in ('u', 'c'):
                        print('Invalid command.')
                    else:
                        break
                if who == 'u':
                    playHand(hand, wordList, n)
                elif who == 'c':
                    compPlayHand(hand, wordList, n)
        else:
            print("Invalid command.")

游戏运行

1
2
3
if __name__ == '__main__':
    wordList = loadWords()
    playGame(wordList)
Loading word list from file...
   83667 words loaded.
Enter n to deal a new hand, r to replay the last hand, or e to end game: n
Enter u to have yourself play, c to have the computer play: c
Current Hand:  u e w c x f n 
"enuf" earned 28 points. Total: 28 points

Current Hand:  w c x 
Total score: 28 points.
Enter n to deal a new hand, r to replay the last hand, or e to end game: r
Enter u to have yourself play, c to have the computer play: u
Current Hand: u e w c x f n 
Enter word, or a '.' to indicate that you are finished: 。
Invalid word, please try again.
Current Hand: u e w c x f n 
Enter word, or a '.' to indicate that you are finished: .
Goodbye! Total score: 0 points.
Enter n to deal a new hand, r to replay the last hand, or e to end game: e

项目参考资料

  1. John V. Guttag - Introduction to Computation and Programming Using Python_ With Application to Understanding Data (2016, The MIT Press)
  2. Advanced Python http://www.scipy-lectures.org/advanced/advanced_python/index.html
  3. Python Documentation https://docs.python.org/3/index.html