Java实现HangMan自动答题程序-初涉AI
Java实现HangMan自动解题程序---初涉AI
实现程序：
在对单词按单词的位数归好类之后，现在就是随机生一个需要猜的字符串。
接下来做的事情就是自动判断程序：
文件操作类：
猜单词游戏（英文：Hangman，“上吊的人”之意）是一个双人游戏。一位玩家想一个字，另一位尝试猜该玩家所想的字中的每一个字母。
要猜的字以一列横线表示，让玩家知道该字有多少个字母。如果猜字的玩家猜中其中一个字母，另一位便须于该字母出现的所有位置上写上该字母。如果猜的字母没有于该字中出现，另一位玩家便会画吊颈公仔的其中一笔。游戏会在以下情况结束：
“我要t字。”“有， 在第八和第十一位。”
· 猜字的玩家猜完所有字母，或猜中整个字
· 另一位玩家画完整幅图：
这幅图其实是设计得像一个吊颈的人。尽管这幅图的品味曾经引起争议，却一直沿用至今。
这幅图的本质各有不同；有玩家在游戏开始前画绞刑架，在游戏期间画人的身体（传统上先画头，再画躯干，然后是左手、同右手，最后是左脚、右脚）。
有玩家在开始时不会画任何图，将绞刑架的每一笔当作游戏的一部分，这种做法实际上给予玩家更多机会。
历史
《牛津字母游戏指南》(The Oxford Guide to Word Games)（牛津大学出版社）作者东尼·欧加迪(Tony Augarde)说：“猜单词游戏的起源已经无从考究，但似是在维多利亚时代开始流行起来。”
爱丽丝·比加·歌美(Alice Bertha Gomme)于1894年出版的《传统游戏》(Traditional Games)中曾提及这游戏，书中称之为“雀、兽、鱼”(“Birds, Beasts and Fishes”)。规则很简单；一个玩家写下一种动物的首尾两个字母，由另外一位猜该字的中间部份。
其他出处中这游戏被称为“绞刑架”(Gallows)或“吊颈游戏”(The Game of Hanging)。
自动解题报告算法思路：
模拟人脑思考即初步设计AI 算法。
第一步：电脑随机出一个单词M，唯一传递出来的信息就是这个单词的位数，即字母的个数。
对应解决办法：那么根据这一点，首先在单词库中对所有的单词进行分析，并且以单词的位数进行分类，最后得到单词位数从1-N 的一个单词集合。后面的操作都是对这个单词集合的操作。那么这里我们得到集合 X，表示指定位数的单词集合。
第二步：猜第一个字母，以大脑来思考的话，那么就应该是在X集合中出现次数最多的字母。
对应解决办法：首先在X集合中找到所有可能出现的字母，然后依次对出现的字母做一个试探性的猜测性分析，即：我如果猜这个字母，那么会有多少个单词会被命中，最后找出命中单词最大的那么字母。
第三步：从第二步会得出一个字母A(假设) ，那么就有两种可能性，M包含这个字母，那么第四步，否则的话，在集合X 中删除所有包含字母A 的单词，缩小猜测的范围。然后继续第二步。
第四步： 在猜中第一个字母后，做一个全匹配删除，即假设单词M 为“hello”，字母A 为 小写‘e’,那么可以得出在第二个位置上有一个字母’e’，同样就可以将第二个位置上不含有字母’e’的单词全部删除，缩小范围。返回第二步。
算法优化
1.在每一次猜中一个字母之后就检测当前剩余的单词库X集合中的单词数，如果小于出错的次数，那么做一个遍历，可以肯定一定可以在指定的出错次数内猜出来。
2.将每一次猜中的字母记录下来，形成一个 Test 字符串，并每次都与单词库做一个匹配操作。
可能存在的更高效的优化：
对所有单词进行分析，找出单词之间在构词法之间的相同点。
详细解决步骤：
利用jsoup 从网上爬单词，组成单词库，这里爬的是四级词汇。
调用程序：
private void getToken() {
File file = new File("doc.txt");
if(file.exists()){
return;
}
String[] str = { "ab", "bc", "cd", "df", "fh", "hl", "lo", "or", "rt",
"tw", "wz" };
htmlHelp html = new htmlHelp();
for (int i = 0; i < str.length; i++) {
String url = "http://cet.hjenglish.com/zt/sijicihui" + str[i] + "/";
String s = html.getContent(url, str[i]);
if (s != null && !"".equals(s))
html.parseDocument(s);
}
html.writeFileByFileWriter("doc.txt", html.list);
}
这里爬的是沪江英语四级的单词汇，就借来用用学学，貌似没有侵权吧.......(*^__^*) 嘻嘻……
下面的具体的实现程序：
package html;
import java.io.File;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Vector;
import org.jsoup.Jsoup;
import org.jsoup.nodes.Document;
import org.jsoup.nodes.Element;
public class htmlHelp {
public List<String> list=null;
public String getContent(String url, String ch)
{
String s = null;
try {
Document doc = Jsoup.connect(url).get();
/*
* 沪江英语的源码在这里wz 都相同,可是标题又不同，一个Bug
* */
if(ch.equals("wz")) ch = "tw";
String cc = ch.toUpperCase();
Element title = doc.getElementById(cc);
if(title!=null)
s = title.toString();
} catch (IOException e) {
e.printStackTrace();
}
return s;
}
public void parseDocument(String str)
{
if(list==null) list = new ArrayList<String>();
int fromIndex=0, judge=0, judge2=0;
String s = "<br />", tmp="";
while((judge = str.indexOf(s, fromIndex)) != -1)
{
if((judge2 = str.indexOf(s, judge+5))!=-1){
for(int i=judge+6; i < judge2; i++)
tmp += str.charAt(i);
list.add(tmp);
fromIndex = judge2;
tmp = "";
}else break;
}
}
public void writeFileByFileWriter(String filePath, List<String> list2){
File file = new File(filePath);
boolean result=true;
if(!file.exists()){
try {
result = file.createNewFile();
} catch (IOException e) {
e.printStackTrace();
}
}
if(result)
{
synchronized (file) {
try {
FileWriter fw = new FileWriter(filePath);
Iterator<String> it = list2.iterator();
while(it.hasNext()){
fw.write(it.next()+'\n');
}
fw.close();
} catch (IOException e) {
e.printStackTrace();
}
}
}
}
}
在爬好了单词库，对单词库按单词的位数进行分析归类。
调用程序：
private void parseToken() {
parseToken = new ParseToken();
parseToken.parseToken();
}
实现程序：
package tangman_01;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import FileHelp.fileHelp;
public class ParseToken {
public ArrayList<String> []tokenString=null;
public List<String> allString = null;
@SuppressWarnings("unchecked")
public void parseToken(){
List<String> list = fileHelp.readFileByLines("doc.txt");
Iterator<String> it = list.iterator();
String token=null, tmp=null;
tokenString = new ArrayList[20];
for(int i=0; i < tokenString.length; i++)
tokenString[i] = new ArrayList<String>();
if(allString==null) allString = new ArrayList<String>();
while(it.hasNext())
{
token="";
tmp = it.next();
int i;
for(i=0; i < tmp.length(); i++){
/*
* 沪江英语的又一个bug ，只有单词解释，却没有单词，之前在爬单词时没有发现，
* 现在只有在这里做一个判断
* */
if(isChinese(tmp.charAt(i))) break;
if(tmp.charAt(i)!= ' ') token += tmp.charAt(i);
else break;
}
if(i!=0)
{
tokenString[i].add(token);
allString.add(token);
}
}
}
public boolean isChinese(char c) {
Character.UnicodeBlock ub = Character.UnicodeBlock.of(c);
if (ub == Character.UnicodeBlock.CJK_UNIFIED_IDEOGRAPHS
|| ub == Character.UnicodeBlock.CJK_COMPATIBILITY_IDEOGRAPHS
|| ub == Character.UnicodeBlock.CJK_UNIFIED_IDEOGRAPHS_EXTENSION_A
|| ub == Character.UnicodeBlock.GENERAL_PUNCTUATION
|| ub == Character.UnicodeBlock.CJK_SYMBOLS_AND_PUNCTUATION
|| ub == Character.UnicodeBlock.HALFWIDTH_AND_FULLWIDTH_FORMS) {
return true;
}
return false;
}
}
在对单词按单词的位数归好类之后，现在就是随机生一个需要猜的字符串。
private String randomSelect() {
int size = parseToken.allString.size();
Random rdl = new Random();
String str = parseToken.allString.get(rdl.nextInt(size));
return str;
}
接下来做的事情就是自动判断程序：
package tangman_01;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import javax.swing.text.StyledEditorKit.ItalicAction;
public class autoJudge {
private String judgeString; // 随机出来的字符串
private List<String> wrongChar = null;// 收集猜错的字母
private List<String> correctChar = null;// 收集猜对的字母
private ParseToken parseToken = null;// 初始的涵盖单词位数的字符串集合
private List<String> nextAllString = null;// 结果筛选之后的字符串集合
private char[] test = null;// 测试字符串，记录猜对的字母和字母所在的位置
private int[] num = null; // 记录字母在字符串匹配中的个数和位置
private int count = 0;// 记录猜错的次数 最大为8；
boolean resu = false;// 结果为true 即为猜出结果否则为没猜出来
// 传入需要匹配的字符串，和原始单词位数的集合
autoJudge(String str, ParseToken parseToken) {
judgeString = str;
this.parseToken = parseToken;
}
public void getResult() {
correctChar = new ArrayList<String>();
wrongChar = new ArrayList<String>();
test = new char[judgeString.length() + 5];
for (int i = 0; i < judgeString.length() + 5; i++) {
test[i] = ' ';
}
// 猜第一个字母;
char c1 = getFirst();
// 判断是否正确，错误返回-1， 正确返回正确的位数，并更新num 数组
/*
* 在一个单词中因为存在重复的字母出现,比如 hello,当猜字母 l 时，那么返回的结果就是2，num中记录2个l 所在的位置
*/
int isHas = containKey(c1);
// begin
// 拿到第一个符合字母
if (isHas == -1) {
count++;// 猜错计数器加 1
wrongChar.add(c1 + "");
// 将包含错误字母的单词全删除，更新所在位数的单词库
deleteDoc(c1);
// 猜下一个字母
char c2 = getNext();
isHas = containKey(c2);
if (isHas == -1) {
/* 循环猜，直到找到第一个匹配的单词 */
while (isHas == -1) {
count++;
wrongChar.add(c2 + "");
// 单字符删除
deleteDoc2(c2);
c2 = getNext();
isHas = containKey(c2);
if (count == 8)
break;
}
correctChar.add(c2 + "");
for (int i = 0; i < isHas; i++) {
test[num[i]] = c2;
}
} else {
correctChar.add(c2 + "");
for (int i = 0; i < isHas; i++) {
test[num[i]] = c2;
}
}
} else {
correctChar.add(c1 + "");
for (int i = 0; i < isHas; i++) {
test[num[i]] = c1;
}
nextAllString = parseToken.tokenString[judgeString.length()];
}// end
if (count < 8) {
// 猜对了第一个字母之后，做全匹配删除
deleteDoc3();
nextBack();
}
if (resu) {
System.out.println("随机出来的字符串是：" + judgeString);
System.out.println("错误匹配的次数为：" + count);
System.out.print(" 错误匹配的字符/字符串分别为：");
for (int i = 0; i < wrongChar.size(); i++)
System.out.print(wrongChar.get(i) + " ");
System.out.println();
System.out.print("正确匹配的字符为：");
for (int i = 0; i < correctChar.size(); i++) {
System.out.print(correctChar.get(i) + " ");
}
System.out.println();
}
}
private void nextBack() {
if (resu)
return;
if (count > 8)
return;
/*
* getNext2() 函数会判断这一次取的字母不是已经在正确匹配字符串中的字母
*/
char c = getNext2();
int isHas = containKey(c);
if (isHas == -1) {
count++;
wrongChar.add(c + "");
deleteDoc2(c);// 单字符匹配删除
} else {
correctChar.add(c + "");
// 更新test
for (int i = 0; i < isHas; i++) {
test[num[i]] = c;
}
deleteDoc3();// 全匹配删除
}
// 剩余单词分析
if (!parseRemain() || !isSuccess()) {
nextBack();
} else
return;
}
// 测试输出结果----调试用
// private void put() {
// System.out.println(judgeString);
// for(int i=0; i < test.length; i++)
// System.out.print(test[i]);
// System.out.println();
// System.out.println(nextAllString.size());
// System.out.println("count = " + count);
// Iterator<String> it = nextAllString.iterator();
// while(it.hasNext()){
// System.out.println(it.next());
// }
//
// }
// 剩余的字符串分析，如果找到则返回true 否则返回false;
/*
* 如果剩余的字符小于还可以错误的次数则可以保证得出正确结果.
* */
private boolean parseRemain() {
if (nextAllString.size() <= (8 - count)) {
Iterator<String> it = nextAllString.iterator();
while (it.hasNext()) {
String tmp = it.next();
if (tmp.equals(judgeString)) {
resu = true;
System.out.println("_________________在剩余分析中找到结果是：" + tmp);
return true;
} else {
wrongChar.add(tmp);
count++;
}
}
}
return false;
}
private char getNext2() {
boolean[] ch = new boolean[100];
Iterator<String> it = nextAllString.iterator();
// 统计出现的字母
while (it.hasNext()) {
String tmp = it.next();
for (int i = 0; i < tmp.length(); i++) {
// 剔除不常用的符号 比如'-'
if (tmp.charAt(i) < 'A')
break;
ch[tmp.charAt(i) - 'A'] = true;
}
}
// 拿到出现的字母中最大的单词包含量
int[] count = new int[100];
int max = 0, maxPos = -1;
for (int i = 0; i < ch.length; i++) {
if (ch[i]) {
if (isExist((char) ('A' + i)))
continue;
count[i] = getNextCount((char) ('A' + i));
if (count[i] > max) {
max = count[i];
maxPos = i;
}
}
}
char c = (char) (maxPos + 'A');
return c;
}
/*
* 判断当前的单词是否已经出现过
* 出现过返回true
* */
private boolean isExist(char c) {
Iterator<String> it = correctChar.iterator();
while (it.hasNext()) {
String tmp = it.next();
if (tmp.charAt(0) == c)
return true;
}
return false;
}
// 匹配成功返回 true 否则 false;
private boolean isSuccess() {
int i;
for (i = 0; i < judgeString.length(); i++) {
if (judgeString.charAt(i) != test[i])
break;
}
if (i != judgeString.length())
return false;
// 直接打印结果
System.out.print("当前分析中找到的结果__________:");
for (i = 0; i < test.length; i++)
System.out.print(test[i]);
System.out.println();
resu = true;
return true;
}
/*
* 全字符匹配删除
* */
private void deleteDoc3() {
List<String> tmpString = new ArrayList<String>();
Iterator<String> it = nextAllString.iterator();
while (it.hasNext()) {
String tmp = it.next();
int j;
for (j = 0; j < test.length; j++) {
if (test[j] != ' ') {
if (tmp.charAt(j) != test[j])
break;
}
}
if (j == test.length) {
tmpString.add(tmp);
}
}
nextAllString = tmpString;
}
/*
* 单字符匹配删除
* */
private void deleteDoc2(char c2) {
List<String> tmpString = new ArrayList<String>();
Iterator<String> it = nextAllString.iterator();
while (it.hasNext()) {
String tmp = it.next();
int i;
for (i = 0; i < tmp.length(); i++) {
if (tmp.charAt(i) == c2)
break;
}
if (i == tmp.length()) {
tmpString.add(tmp);
}
}
nextAllString = tmpString;
}
/*
* 猜下一个可能出现的字母
* */
private char getNext() {
boolean[] ch = new boolean[100];
Iterator<String> it = nextAllString.iterator();
// 统计出现的字母
while (it.hasNext()) {
String tmp = it.next();
for (int i = 0; i < tmp.length(); i++) {
// 剔除不常用的符号 比如'-'
if (tmp.charAt(i) < 'A')
break;
ch[tmp.charAt(i) - 'A'] = true;
}
}
// 拿到出现的字母中最大的单词包含量
int[] count = new int[100];
int max = 0, maxPos = -1;
for (int i = 0; i < ch.length; i++) {
if (ch[i]) {
count[i] = getNextCount((char) ('A' + i));
if (count[i] > max) {
max = count[i];
maxPos = i;
}
}
}
char c = (char) (maxPos + 'A');
return c;
}
/*
* 拿到字母在当前所有字符串中出现的个数
* */
private int getNextCount(char c) {
Iterator<String> it = nextAllString.iterator();
int count = 0;
while (it.hasNext()) {
String tmp = it.next();
for (int i = 0; i < tmp.length(); i++) {
if (tmp.charAt(i) == c) {
count++;
break;
}
}
}
return count;
}
private void deleteDoc(char c1) {
nextAllString = new ArrayList<String>();
int length = judgeString.length();
Iterator<String> it = parseToken.tokenString[length].iterator();
while (it.hasNext()) {
String tmp = it.next();
int i;
for (i = 0; i < tmp.length(); i++) {
if (tmp.charAt(i) == c1)
break;
}
if (i == tmp.length()) {
nextAllString.add(tmp);
}
}
}
/*
* 判断猜的字母是否在匹配的字符串中，如果
* 存在那么返回存在的位数，否则返回-1
* */
private int containKey(char c1) {
int tmp[] = new int[10];
int length = 0;
int i;
for (i = 0; i < judgeString.length(); i++) {
if (judgeString.charAt(i) == c1) {
tmp[length++] = i;
}
}
num = tmp;
if (length > 0)
return length;
else
return -1;
}
/*
* 第一次猜
* */
private char getFirst() {
int length = judgeString.length();
boolean[] ch = new boolean[100];
Iterator<String> it = parseToken.tokenString[length].iterator();
while (it.hasNext()) {
String tmp = it.next();
for (int i = 0; i < tmp.length(); i++) {
// 剔除不常用的符号 比如'-'
if (tmp.charAt(i) < 'A')
break;
ch[tmp.charAt(i) - 'A'] = true;
}
}
int[] count = new int[100];
int max = 0, maxPos = -1;
for (int i = 0; i < ch.length; i++) {
if (ch[i]) {
count[i] = getCount((char) ('A' + i));
if (count[i] > max) {
max = count[i];
maxPos = i;
}
}
}
char c = (char) (maxPos + 'A');
return c;
}
private int getCount(char c) {
int length = judgeString.length();
Iterator<String> it = parseToken.tokenString[length].iterator();
int count = 0;
while (it.hasNext()) {
String tmp = it.next();
for (int i = 0; i < tmp.length(); i++) {
if (tmp.charAt(i) == c) {
count++;
break;
}
}
}
return count;
}
}
最后是一些其他的主调用程序：
main ：
package tangman_01;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import FileHelp.fileHelp;
import html.htmlHelp;
public class main {
public static void main(String[] args) {
int size = 10;
Start []start = new Start[size];
for(int i=0; i < size; i++)
{
start[i] = new Start();
start[i].startGame();
System.out.println("--------------------------");
}
}
}
start 类：
package tangman_01;
import html.htmlHelp;
import java.io.File;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Random;
import FileHelp.fileHelp;
public class Start {
ParseToken parseToken = null;
public void startGame() {
// 拿到单词库
getToken();
// 分析单词库，即将单词以字母的位数做分析
parseToken();
// 生成的随机单词
String str = randomSelect();
autoJudge resu = new autoJudge(str, parseToken);
resu.getResult();
}
private String randomSelect() {
int size = parseToken.allString.size();
Random rdl = new Random();
String str = parseToken.allString.get(rdl.nextInt(size));
return str;
}
private void parseToken() {
parseToken = new ParseToken();
parseToken.parseToken();
}
private void getToken() {
File file = new File("doc.txt");
if(file.exists()){
return;
}
String[] str = { "ab", "bc", "cd", "df", "fh", "hl", "lo", "or", "rt",
"tw", "wz" };
htmlHelp html = new htmlHelp();
for (int i = 0; i < str.length; i++) {
String url = "http://cet.hjenglish.com/zt/sijicihui" + str[i] + "/";
String s = html.getContent(url, str[i]);
if (s != null && !"".equals(s))
html.parseDocument(s);
}
html.writeFileByFileWriter("doc.txt", html.list);
}
}
文件操作类：
package FileHelp;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
public class fileHelp {
public static List<String> readFileByLines(String filePath){
File file = new File(filePath);
if(!file.exists() || !file.isFile()){
return null;
}
List<String> content = new ArrayList<String>();
try {
FileInputStream fileInputStream = new FileInputStream(file);
InputStreamReader inputStreamReader = new InputStreamReader(fileInputStream, "GBK");
BufferedReader reader = new BufferedReader(inputStreamReader);
String lineContent = "";
while ((lineContent = reader.readLine()) != null) {
content.add(lineContent);
}
fileInputStream.close();
inputStreamReader.close();
reader.close();
} catch (FileNotFoundException e) {
e.printStackTrace();
} catch (IOException e) {
e.printStackTrace();
}
return content;
}
}