Recommend
1 
 Thumb up
 Hide
26 Posts
1 , 2  Next »   | 

BoardGameGeek» Forums » Gaming Related » Computer Based Board Gaming

Subject: Programming Challenge: Create an AI for this game! (GG prize) rss

Your Tags: Add tags
Popular Tags: [View All]
Tracy Cobbs
United States
Decatur
Alabama
flag msg tools
Avatar
mbmbmb
The Game: Wordsearch

The Prize: 10 GG + 90% of tips to this thread (I'll keep the other 10% of tips as my fee for evaluating and judging the entries). And who knows, if you create a great app, and you can acquire the appropriate rights, you might even be able to make some real money off your app.

The Deadline: June 30, 2014

The Reason/Background: Wordsearch has been one of my favorite games for years, but I have few opportunities to play human opponents. Anyone who could create a good AI opponent would have my lifelong gratitude. I think this will be an interesting challenge for programmers because the search space for this game is very large.
When I searched for already-existing implementations of this game, I came across some Javascript written by BGG user
Doug Orleans
United States
Somerville
Massachusetts
flag msg tools
designer
mbmbmbmbmb

on GitHub (https://github.com/dougo/wordsearch). That code is only the bare bones of the game though -- no AI, no multiplayer, and (as of the date of this post) an incorrect tile distribution (there should be no blanks and 5 D's in the correct distribution). But looking at that code may give you a starting point for your own implementation and may save you from "reinventing the wheel".

The Judging Criteria (roughly in order of importance):
1) All entries must use as their word source Scrabble's Official Tournament and Club Word List (a text version of the word list can be found at http://www.ericharshbarger.org/epp/2009/TWL06.txt; however, that file contains errata found in the printed version of the word list -- fixes for the errata can be found at http://www.scrabbleplayers.org/w/OTCWL). Note that the maximum length for valid plays in Wordsearch is 10 letters, while in Scrabble it is 15, so you could eliminate words of lengths 11 to 15 from that file in order to save memory.

2) AI strength -- In order to gauge AI strength, I will pit entries against each other in a round robin tournament, the exact parameters of which will be determined later (perhaps a best-of-5 match for each pair of programs?). In order to facilitate this evaluation, programs will need a feature allowing manual setup of opening positions, as discussed in 5(a) below.

3) AI scalability -- Strong AI is not necessarily fun, if it beats you every game, so having multiple skill levels for the AI will be considered a plus.

4) AI speed -- While long computation time may be acceptable for analysis of optimal moves, fun casual games should move at a reasonable pace.

5) Features -- desirable features include:
a) The ability to set up an opening position, or a position from any point in the game, for the program to analyze
b) The ability to save/resume games in progress
c) The ability to display/export/print game transcripts
d) All the usual bells and whistles of boardgame apps (graphics, animations, sound, help files/tutorials, etc.) -- definitely last on my list of criteria, but not totally irrelevant.
1 
 Thumb up
11.00
 tip
 Hide
  • [+] Dice rolls
Sebastián Koziner
Argentina
Capital Federal
Buenos Aires
flag msg tools
designer
publisher
badge
OK Art Studio - www.okartstudio.com
Avatar
mbmbmbmbmb
With all respect, you are asking someone to spend tons of programming hours for a 10 GG contest?

It's kinda insulting to dismiss how much work this is, I recommend you go and find a programmer who loves the game like you do, who love it so much he want to do it for free. Otherwise, I hope you realize you are asking hundreds (or even thousand) of dollars in programming for just 10 GG.

I hope the best for you and your idea, but as a professional game developer i'm just astonished of your request and hope it gives you some perspective.

19 
 Thumb up
0.01
 tip
 Hide
  • [+] Dice rolls
Tiger Wiccan
United States
Florida
flag msg tools
mbmbmbmbmb
SebasKO wrote:
With all respect, you are asking someone to spend tons of programming hours for a 10 GG contest?

It's kinda insulting to dismiss how much work this is, I recommend you go and find a programmer who loves the game like you do, who love it so much he want to do it for free. Otherwise, I hope you realize you are asking hundreds (or even thousand) of dollars in programming for just 10 GG.

I hope the best for you and your idea, but as a professional game developer i'm just astonished of your request and hope it gives you some perspective.



I'm not even a programmer and I 100% concur with this post.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Tracy Cobbs
United States
Decatur
Alabama
flag msg tools
Avatar
mbmbmb
With all respect, finding someone who loves the game as much as I do is exactly what I'm looking for; and how many programming hours someone devotes to this programming challenge is totally up to the people who choose to participate.
2 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Clint Herron
United States
Bethel
Ohio
flag msg tools
designer
♜ ♞ ♝ ♛ ♚ ♝ ♞ ♜ ♟ ♟ ♟ ♟ ♟ ♟ ♟ ♟
badge
♙ ♙ ♙ ♙ ♙ ♙ ♙ ♙ ♖ ♘ ♗ ♕ ♔ ♗ ♘ ♖
Avatar
mbmbmbmbmb
This is pseudocode for an exhaustive search that will guarantee to find the best word for any given board layout of tiles.

Not going to take the time to write this into the JavaScript implementation, but you can use this as a template if you want to implement it yourself. It would be an excellent learning project for someone to get started into programming.


array characterValues[26] = {0, 2, 2, 1... etc}; // This information is stored in the tileData array in wordsearch/wordsearch.js

class tile
{
int x;
int y;
int character;
letter* neighbors;
}

// This function should trigger when the AI plays, or when you click a "hint" button.
findBestWord() {

for each tile in board {
string currentWord = "" + tile.character;
// Note: Instead of storing the current word as a string, it might be best to make an array (or even a whole new class) to store a string of tiles.
permutateNeighbors(currentWord, tile);
}

// After this is done, then addWordWithScore() will have been called for every valid word on the entire board.

// Sort the list of valid words by score

// Choose the top word

// Play it and/or highlight it.
}

permutateNeighbors( currentWord, tile ) {
for each neighbor in tile.neighbors {
testWord = currentWord + tile.character;

if (isCompleteWord(testWord))
addWordWithScore(testWord);

if (isValidWordStart(testWord))
permutateNeighbors( testWord, neighbor );
}
}

bool isCompleteWord(testWord) {
// Check against SOWPODS (or some other word list) for validity
}

bool isCompleteWord(testWord) {
// Check against SOWPODS (or some other word list) to see if there are any words that this is a valid start to (regex match for testword + ".+")
}

addWordWithScore() {
// Stores the word with the associated score in some list somewhere. Potentially only store the word if it's the current highest score to optimize.
}



Beyond this, because this is a deterministic game (like tic-tac-toe), once we have reached the "best" solution, an AI competition doesn't make much sense. This isn't a particularly challenging AI -- it's really just about writing a time-efficient exhaustive search, which is an excellent high-school level software programming project.
2 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Doug Orleans
United States
Somerville
Massachusetts
flag msg tools
designer
mbmbmbmbmb
Clint, I think you misunderstand the rules of Wordsearch. A turn does not just consist of finding a word on the board; you can move any number of tiles to form a word, and each tile can move any distance in a straight line (over empty spaces). The number of legal moves, especially in the midgame, is enormous-- I would guess it's in the thousands. Compare this with Octi, which was designed to be difficult for a computer to play: its branching factor is less than 700. https://groups.yahoo.com/neo/groups/octiclub/conversations/m...
2 
 Thumb up
0.01
 tip
 Hide
  • [+] Dice rolls
Andy Latto
United States
Foxboro
Massachusetts
flag msg tools
designer
mbmbmbmbmb
DougOrleans wrote:
Clint, I think you misunderstand the rules of Wordsearch. A turn does not just consist of finding a word on the board; you can move any number of tiles to form a word, and each tile can move any distance in a straight line (over empty spaces). The number of legal moves, especially in the midgame, is enormous-- I would guess it's in the thousands. Compare this with Octi, which was designed to be difficult for a computer to play: its branching factor is less than 700. https://groups.yahoo.com/neo/groups/octiclub/conversations/m...

Yes, but in Octi, it's hard to evaluate which of those 700 resulting positions is best; you need multimove lookahead, and if you want to look 5 moves ahead without some sort of pruning of the game tree, that would be 700^5 positions to evaluate. In Wordsearch, I suspect that a program that did no lookahead at all, and just made the move that maximized its score on that turn, would be a pretty strong player compared to humans. This would have to examine thousands of positions, but that isn't that many for a computer.
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Clint Herron
United States
Bethel
Ohio
flag msg tools
designer
♜ ♞ ♝ ♛ ♚ ♝ ♞ ♜ ♟ ♟ ♟ ♟ ♟ ♟ ♟ ♟
badge
♙ ♙ ♙ ♙ ♙ ♙ ♙ ♙ ♖ ♘ ♗ ♕ ♔ ♗ ♘ ♖
Avatar
mbmbmbmbmb
DougOrleans wrote:
Clint, I think you misunderstand the rules of Wordsearch. A turn does not just consist of finding a word on the board; you can move any number of tiles to form a word, and each tile can move any distance in a straight line (over empty spaces). The number of legal moves, especially in the midgame, is enormous-- I would guess it's in the thousands. Compare this with Octi, which was designed to be difficult for a computer to play: its branching factor is less than 700. https://groups.yahoo.com/neo/groups/octiclub/conversations/m...

Ah, thanks. I missed that aspect.

So that can be done a couple of different ways, but I would probably solve this by just increasing the adjacency test for each tile to not just include adjacent tiles ,but include all tiles that can move into that adjacent space. This increases the complexity, but especially because pieces can't jump other pieces, it's not horrible IMO.

In so far as it's still a deterministic game, I would follow the same approach (of building an exhaustive search), and then Monte Carlo it to reduce the CPU workload.

Some games (such as Go) that have large branching trees aren't just valuable in that they have a large branching factor, but it's difficult to create a solid heuristic for the midgame ("is this stage better than that stage?").

But in this game, scoring happens immediately, so you don't need to think hundreds of moves in advance like you would want to for Go / Chess / other tactical games. Those games don't have a clear heuristic. WordSearch does. That's biggest difference why I think that this game is so solvable.

There is another layer to this AI, where you would want to not only maximize your own score, but minimize the maximum score achievable by your opponent(s) on the next turn(s). So once you find your "best move", run your "best move" routine again (but playing from the position that your opponent will see if you were to choose this move), and seeing what that best move is. Your best move is not the word with the largest score -- your best move is the word with the largest difference between your score and your opponent's next best possible score.

But even so, you're not thinking 100 moves in advance -- minimax only requires you to think 1 move in advance really. You can think multiple moves in advance with minimax, but it really has diminishing returns very very quickly.


I'm pretty confident that this option set is not insurmountably huge. There are what, 7 adjacent spots for each tile (8 for the first tile)? And potentially 7 tiles that could slide into each of those spots (again, 8 for the first tile)? So that's (worst case scenario) 49 (64) potentials to check for each tile. Max word length in SOWPODS is 15 or so, so that's 49 ^ 15 worst-case options, but I don't think you'd actually ever get that far. Your option tree would be MASSIVELY culled by the actual word list limitations (you don't need to check "QTTTWQR" -- you can stop at "QT" because no valid words exist with that as a start), and I don't doubt that a standard personal computer could still do an exhaustive search on a board in under 10 seconds without breaking a sweat.


This is all theoretical though, and it's fun to build sandcastles in the sky over it. I think it would be a good exercise for someone who wants to learn about AI.
2 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Doug Orleans
United States
Somerville
Massachusetts
flag msg tools
designer
mbmbmbmbmb
andylatto wrote:
In Wordsearch, I suspect that a program that did no lookahead at all, and just made the move that maximized its score on that turn, would be a pretty strong player compared to humans. This would have to examine thousands of positions, but that isn't that many for a computer.


I am not so sure. I think it's true that a human is unlikely to consistently find the maximum scoring move for a given board position, but I suspect that a human using a small amount of lookahead and strategy might beat the greedy algorithm. For a trivial endgame example, if there are two vowels left, you're probably usually better off using both of them on a suboptimal word rather than leaving one for your opponent to take another turn.

Furthermore, I think that even the greedy algorithm is not so trivial to implement. There may only be thousands of legal moves, but there are trillions of well-formed moves that are not legal words. I don't think a computer can do a brute-force search in a reasonable time.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Tracy Cobbs
United States
Decatur
Alabama
flag msg tools
Avatar
mbmbmb
Some topics relating to data structures in word-game programs that may (or may not) be helpful to people who decide to tackle this challenge:

DAWG (Directed Acyclic Word Graph):
http://en.wikipedia.org/wiki/DAWG
and a related page
http://en.wikipedia.org/wiki/Deterministic_acyclic_finite_st...

GADDAG:
http://en.wikipedia.org/wiki/GADDAG
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Dave Dyer
United States
Playa Del Rey
California
flag msg tools
designer
Avatar
mbmbmbmbmb
I once wrote a program to play Jotto (mastermind with dictionary words)
and it crushed human opponents by using obscure words as clues.

I would expect the same to be true of wordsearch. You have no chance
against a program with access to the full, finite dictionary of acceptable
words.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Tracy Cobbs
United States
Decatur
Alabama
flag msg tools
Avatar
mbmbmb
ddyer wrote:
I once wrote a program to play Jotto (mastermind with dictionary words)
and it crushed human opponents by using obscure words as clues.

I would expect the same to be true of wordsearch. You have no chance
against a program with access to the full, finite dictionary of acceptable
words.



You're probably right. That's why I included AI scalability as one of my desired features. (Judging criterion #3 in the original post.)
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Ian Richard
United States
Maine
flag msg tools
designer
Avatar
mbmbmb
Yeah... I'll pass. I'd hesitate to take this job even for a real money reward.

One flaw in your setup though...

Your test for "Strength" probably won't be any use. Because all of the words are using the same dictionary... and they are probably all using a systematic word search of some sort... they'll end up with the same results.

Your test will only show which AI had the better options available on their turn.
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Tracy Cobbs
United States
Decatur
Alabama
flag msg tools
Avatar
mbmbmb
McTeddy wrote:
Your test for "Strength" probably won't be any use. Because all of the words are using the same dictionary... and they are probably all using a systematic word search of some sort... they'll end up with the same results.

Your test will only show which AI had the better options available on their turn.


What you say would be true if "maximize score on this turn" is the optimal algorithm. I'm not convinced it is optimal, so I'm looking forward to seeing programs using various evaluation algorithms go head-to-head.

For a parallel, see the evolution of Scrabble-playing programs from early programs that always went for max score on the current turn to the Monte Carlo simulations used in the current top program, Quackle (http://people.csail.mit.edu/jasonkb/quackle/).
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Alan Monroe
United States
Columbus
Ohio
flag msg tools
Avatar
mbmbmbmbmb
Is there a full rule sheet online? I don't see one in the files section for the game. The overview doesn't explicitly say whether scored tiles are removed from the board, although it's implied by some of the photos.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Tracy Cobbs
United States
Decatur
Alabama
flag msg tools
Avatar
mbmbmb
JavaJack wrote:
Is there a full rule sheet online? I don't see one in the files section for the game. The overview doesn't explicitly say whether scored tiles are removed from the board, although it's implied by some of the photos.


I haven't been able to find the English rulesheet online (other than the low-rez image in the game's image gallery), but I did find a .pdf of the French rules at http://regle.jeuxsoc.fr/worse_rg.pdf.

Yes, scored tiles are removed from the board.

I will see what I can do about scanning and uploading the English rulesheet. (I don't own a scanner, but I think I can get access to one this weekend.) If someone beats me to the scanning/uploading, that's great.
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Alan Monroe
United States
Columbus
Ohio
flag msg tools
Avatar
mbmbmbmbmb
HanClinto wrote:
so that's 49 ^ 15 worst-case options, but I don't think you'd actually ever get that far. Your option tree would be MASSIVELY culled by the actual word list limitations (you don't need to check "QTTTWQR" -- you can stop at "QT" because no valid words exist with that as a start),


I put some work into this today and realized it's not quite that simple, because the order of tile moves is significant. So there are a lot more permutations to try if you want to do an exhaustive search. And the simple trie I created from the word list wasn't enough to help find words starting in the middle of the word. I skimmed over the GADDAG paper, but it was a bit over my head.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Tracy Cobbs
United States
Decatur
Alabama
flag msg tools
Avatar
mbmbmb
bobcatscry wrote:
I will see what I can do about scanning and uploading the English rulesheet. (I don't own a scanner, but I think I can get access to one this weekend.) If someone beats me to the scanning/uploading, that's great.


I have a scan of the English rules now, but upon reading the fine print about file uploading on BGG, I don't think they'll accept the upload because of copyright issues. I can email it to those who would like to have it, if you'll Geekmail me your address.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Eric Tung
msg tools
My day job is a software developer (though not in a gaming or AI-related field). As a hobby project, I wrote an Android port of RoboTroc, complete with AI (shameless plug: check it out!). Despite sinking about a year of spare time into the project, the AI is still not super convincing. I'd like to spend more time improving it, but the effort/reward ratio just isn't good.

I agree with others who have said you're probably vastly underestimating the effort to create a good AI or create a polished game. If someone is motivated by the love for the game, a reward is nice (but doesn't matter). If they're not, even if you guaranteed them the 10 GG reward just to enter, I think their time would still be undervalued. As is, the prospect of sinking tens or hundreds of hours into a project with a good chance for no payout is even less motivating.

Don't get me wrong, I want to believe there's a pool of developers with nothing better to do than write brilliant AI. I'm interested to hear if you get any submissions (and who does so). I just don't think it's likely.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Tracy Cobbs
United States
Decatur
Alabama
flag msg tools
Avatar
mbmbmb
etung wrote:
...even if you guaranteed them the 10 GG reward...


Just to clarify, the prize is not 10 GG, it is 10 GG + 90% of tips to this thread.

So the total prize to be awarded is 19.90 GG at this point, thanks to tips from DougOrleans and JavaJack. Thanks for your interest and support guys!

etung wrote:
I'm interested to hear if you get any submissions (and who does so).


I will definitely keep the BGG community updated about submissions.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
William McCarroll
United States
Bel Air
Maryland
flag msg tools
Check out my reviews at www.nerdbloggers.com
badge
Hi!
Avatar
mbmbmbmbmb
I agree with Clint that in this instance a Monte Carlo tree is probably the way to go. It's not exhaustive, but can get very good results after a decent number of iterations. Despite the name, Monte Carlo trees aren't completely random. They start out that way, but are weighted to spend more time in branches that have a statistically stronger change of generating a winning output.

With a method like this, the more iterations you can get in within an acceptable "thinking" period for the AI, the better. Choosing an optimal data structure to do your dictionary lookups will be of utmost importance here. My go to for word game dictionaries is usually the trie.

A BK tree may be useful as well, because as I gather from the rules, knowing edit distances (the number of insertions/deletions/changes required to move from one word to another) will help you cull the number of possible words that can be created, and significantly reduce your search domain. (If not a BK tree, anything that can quickly calculate Levenshtein Distances. The BK tree is something that can be precompiled with a known dictionary, though, and so is probably more suited than an algorithm that calculates the edit distance of two completely arbitrary words.)

What is especially nice about Monte Carlo trees, though, is that you can tune the amount of "fuzzyness" that it uses to choose the next move, which allows you to tweak the aggressiveness of the AI. A "good" AI is not a perfect AI. A perfect AI is extremely frustrating for players, and no fun at all.

I like using a rating system like Glicko2 to drive the "fuzziness" of the Decision making in the Monte Carlo tree for the AI. Both the player and AI are ranked as they play games. Over time, as the gap between the player's rating and the AI rating increases, the AI adjusts to keep it's ranking as even with the player's as possible.

Edit: added links to definitions of some of the data structures and terms used
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
William McCarroll
United States
Bel Air
Maryland
flag msg tools
Check out my reviews at www.nerdbloggers.com
badge
Hi!
Avatar
mbmbmbmbmb
HanClinto wrote:

But in this game, scoring happens immediately, so you don't need to think hundreds of moves in advance like you would want to for Go / Chess / other tactical games. Those games don't have a clear heuristic. WordSearch does. That's biggest difference why I think that this game is so solvable.


I would still think that you would want an AI that had a moderate lookahead, as a previous move changes the board layout and gamestate, so choosing words that set the board up for you to score higher value words in future turns would be useful, even if scoring does occur on a per-turn basis.

Although not as important in a completely spatial strategy game like chess or go, it seems to me that there is enough meat to want to run each simulation at least 5-10 turns into the future.
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Tracy Cobbs
United States
Decatur
Alabama
flag msg tools
Avatar
mbmbmb
Today marks the halfway point between the posting of this challenge and the deadline. (Of course, the deadline only applies to the awarding of the GeekGold prize -- any programs created after the deadline will still be welcome and appreciated.)

The prize to be awarded is currently 19.90 GG, and tips to this thread will increase that prize. If there are no entries submitted, tips received will be refunded to the tippers.

Two people requested the Wordsearch rules scan from me, but no one has indicated that they're actively working on writing a program. If there is anyone working on programming this, could you please let me know?


I did some work on quantifying the number of legal tile movements in some positions. The four game positions I looked at are the ones pictured in this thread ("Test your Wordsearch skills with these positions").

The first is an opening position. It's easy to see that there are 32 possible 1-tile slides. I counted 534 possible 2-tile slides (with the restriction that the two tiles moved to adjacent positions). There are 72 possible 10-tile slides. I did not work out the possibilities for intermediate numbers of slides.

In the 2nd, 3rd and 4th positions, I only counted 1-tile slides -- the move count would go up exponentially from these base numbers. Position 2 has 218 1-tile slides; position 3 has 264; and position 4 has 305.


Thanks to those of you who have participated in this thread so far. I appreciate your interest in and discussion of this game and the challenge of programming it.
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Tracy Cobbs
United States
Decatur
Alabama
flag msg tools
Avatar
mbmbmb
The prize deadline has passed and there were no programs submitted. Tips were returned to the two tippers.


I hope that anyone who knows a Comp. Sci. student in search of a good topic for a paper or project will recommend Wordsearch to them as a good game to try programming. Please do let me know if you hear of anyone who does anything along those lines.


Thanks to those who took an interest in this and provided some interesting discussion about approaches to programming this game. Perhaps one day I'll even get around to teaching myself to code and doing it myself. cool
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Joel Ricker
United States
Fuquay Varina
North Carolina
flag msg tools
Avatar
I'm still tinkering with a solution but I'm far from finished. I'll let you know if I come up with anything.
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
1 , 2  Next »   | 
Front Page | Welcome | Contact | Privacy Policy | Terms of Service | Advertise | Support BGG | Feeds RSS
Geekdo, BoardGameGeek, the Geekdo logo, and the BoardGameGeek logo are trademarks of BoardGameGeek, LLC.