AI / Automate: WordGame

After Flappy Bird I sat down and tried to automate an other game. Github provides a search function which helped me locate games with words. A found WordGame by headshota which is a simplified version of Scrabble.

Making AI possible

I didn’t have to change much – basically I didn’t have to change anymore. But because I’m lazy I put the dictionary variable in global scope so that I don’t have to load it myself.

The algorithm

The algorithm is pretty easy. We have two inputs. Firstly, we have some letters. Secondly, we have a dictionary of valid works.

Sort our dictionary

There are several approaches to this problem. I choose one which is pretty easy. So, firstly I created two dictionaries. There’s our common standard dictionaries with English words which is used for the game. It includes words like HELLO or TREE. From this dictionary I created a second one which has sorted characters. So instead of hello it saves EHLLO and instead of tree it stores EERT. I stored this in a list but with the same index as the original. That is when HELLO is the 68th element in the original dictionary EHLLO is the 68th element in the sorted one.

The great thing about this approach is that you don’t need to generate permutations. Instead you can just generate substrings of our available letters.

Generate possible words

Now, we have some available letters. Again, we sort these. Now we have a sorted list of letters. We can take this list and generate all possible subpattern from this list. We can do this pretty easy using suffixes and prefixes. The cool thing is that we don’t have to change the position. Let’s say that we have these letters: AEEMRT.

AEEMRT
 EEMRT
  EMRT
   MRT
    RT
     T

AEEMRT
AEEMR
AEEM
AEE
AE
A

AEEMRT
A EMRT
A  MRT
A   RT
A    T

AE MRT
AE  RT
AE   T

AEEMRT
 EEMRT
 EE RT
 EE  T

You can see that there are basically three operations. Firstly, we generate suffixes, then prefixes and put them together. That’s it. Really easy algorithm.

Are these real words?

The next step is to check if our generated words are actually valid, real words. That’s also pretty simple. You probably remember our sorted dictionary. Now we just have to check if any of our generated words is in this dictionary. For example, we can see that EERT is in our generated words. We check it and see that EERT is in position 68. Now I convert it to it’s English equivalent – index 68 in the dictionary and return the list with valid words.

What’s the best word?

Most likely we can form different words. The next and last step is to find the best word. The rule depends on the game, in this game the rule is that each letter gets one point. So we just sort the list using a comparison function. In this case it’s a simple function that compares word lengths.

legalWords.sort(function(a, b) {
    return b.length - a.length;
});

Now we can just return the first element in our list. An advantage of this approach is that we can easily adjust to the game rules. Let’s say for example, that the letter Z brings additional 3 points. We just adjust the comparison function to include the extra 3 points.

And that’s it. The algorithm, although it’s written in JS, is faster than necessary. So there’s no problem. I actually put it on a half a second timer and sped up the original game’s timers.

Video

Again I recorded this screencapture with recordit which just works out of the box which is great.

RAD web development please

I don’t like working on the UI. In the same article I wrote about the ambiguity of user interfaces in general. The idea of right and wrong isn’t so strong in the UI field than, e.g., in database programming.

Bootstrap is pretty good

Regarding HTML I liked the approach Bootstrap has taken. They make HTML more HTML-like which sounds crazy. But given that the standard elements look so terrible it allows you to use them again and at least it looks decent. Even better is that a lot of templates build on Bootstrap which means you can just buy / download a good-looking template and still just write your bootstrap code. Pretty good.

Web frameworks

I have to say that I’m still now satisfied with web frameworks. I still have to do to much work. Thinking back about using software like Borland’s C++Builder. Sure it wasn’t the greatest bit of software. But you know what? I could create a decent UI in a few minutes and just add my get and setters.

I didn’t need to care about events, or UI synchronization, or underlying threads and all that stuff. And I have to with modern web frameworks.

I think I said it again and again. I love my prototypes and PoCs. I don’t want to create the greatest looking site with the best UX but rather a decent one with least effort.

I want to demonstrate this with an example.

TODO app

Let’s take a standard simple web app like an TODO app. What do we want?

  • Login
  • Registration
  • Add Task (what? deadline?)
  • Delete Task
  • List Task for today, tomorrow, all

Pretty simple. Here’s the thing. It’s basically just a database with an UI. Everything could be replicated with a database. I wouldn’t recommend doing it this was but I want to show how easy an TODO app could be.

Login

psql -d database -U user << password

Registering

CREATE USER user WITH PASSWORD 'password';

Add Task (what? deadline?)

INSERT INTO tasks VALUES (what, deadline);

Delete task

DELETE FROM tasks WHERE id = id;

List Task for today, tomorrow, all

SELECT * FROM tasks WHERE deadline = CURRENT_DATE;
SELECT * FROM tasks WHERE deadline = CURRENT_DATE + interval '1 day';
SELECT * FROM tasks;

Let’s also create the boilerplate:

CREATE TABLE tasks (id bigserial primary key, what text, deadline date);

And that’s basically it. This may take you 5 to 15 minutes. It’s easy, it’s decently abstracted and it’s fun because you are so powerful. That’s also something I see when people write LISP or LISP-dialects. They try to create powerful code.

The problem of course is the rest you have to do when writing this web app. Creating HTML files, caring about user authentication, checking values, etc. etc. And that’s why I liked tools for rapid application development so much – I didn’t have to care about it.

Going in the right direction

I actually like that the web development goes towards using APIs to abstract the application and then building on top. I think that that’s the right way to do it – your presentation should be independent of the rest. And I really like what meteor is doing. And that being said

Thinking about it. I would be more than happy if there would be a tool to prototype an UI – and I mean prototype – no fiddling. There are interface builders for bootstrap out there – which is great. The next step is to integrate one of the JS frameworks – like Angular.js or Ember.js.

Example

Let me build my interface around a REST api. I know my calls just let me bind them to elements and their events. Let’s take the TODO app example. I build a quick interface using jetstrap:

todo_app

This took me maybe 10 minutes. You see that it’s not ideal (e.g. the button is not aligned) and the UI creating the interface is a bit fiddly but it’s okay. The next thing I want to do is to bind REST API calls to actions and events in the interface. This is sadly not possible yet but here’s how the workflow could look like.

For example: I select the submission button and create the REST call URL using information provided by the builder. E.g. POST /task {‘task’: <TASK>, ‘until’: <UNTIL>}

The same could be done on the open tasks. I just describe the URL call and the return format and the rest is handed by the framework. E.g. GET /tasks {‘task’: <TASK>, ‘until’: <UNTIL>}.The server side can be handled with a few lines of code thanks to micro frameworks. And that’s it.

Something about writing code

Projects are pretty fun. Currently, I restrict myself to small projects (less than 8 hours) because I don’t know if I have the motivation to do more. But I started a small project again today – this morning and it was great. I’ve written quite a few lines of code and they worked pretty fine.

I remember when I first started learning to program. I was happy if a line of code worked after my third try. It was pretty funny. Even a bit later when I first learned C++ I was happy if one or two lines worked without debugging.

One of the most demanding tasks was writing assembler on paper. Actually, this was even included in our finals. The programs were rather simple of course, e.g. a traffic light circuit but thinking about all the registers and stuff was pretty hard. Especially, because I couldn’t test the code.

One thing about writing code is familiarity. And this was one aspect I didn’t consider in the past. When I looked at source code from some experts in a field, e.g. from Peter Norvig I was always overwhelmed. Everything was so clever and well thought through. After I read more and more code from Norvig I’ve learned that he uses the same techniques in different pieces of code. I started to learn his techniques and applied them in my code. And whoosh suddenly it looked also pretty clever.

Also these people are exceptional and have tons of experience. Norvig is in the field over 20 years.

What helped me is learning functional programming languages. Especially my python code improved a ton when I learned Scheme and Haskell. I started to use more list comprehensions and thought more in functional terms. For me, that meant I thought about map, reduce, filter, zip, etc.

A simple example is that you need to manipulate a list of strings for example. The idea is that you want to replace each $ with USD.

A C-type Python-inspired code looks like this:

lst = ["23.56$", "8.43$", "$95.02", "$2.99"]

new_lst = []
for l in lst:
    new_lst.append(l.replace("$", "USD"))

I just didn’t include the very C-ish approach using an index.

A more pythonic approach – which I would probably use – looks like this:

lst = ["23.56$", "8.43$", "$95.02", "$2.99"]

new_lst = [l.replace("$", "USD") for l in lst]

Alternatively, a functional approach:

lst = ["23.56$", "8.43$", "$95.02", "$2.99"]

new_lst = map(lambda l: l.replace("$", "USD"), lst)

I normally, fall back to using map and its friend when I want very performant code because it’s faster.

And I see that a lot of beginners have problems writing pythonic code. It doesn’t help that their teachers often don’t know how to write pythonic code or just write C-like code in Python.

But still it has to do with habit and familiarity. When I’m familiar with a domain I know how to structure my code, how to write functions and how to solve problems. This results in two things: a) I’m pretty fast and b) the code is more robust and nicer.

I think my best-known area of expertise is bots or automation in the web field. Yeah, we say the latter is a better description. I just understand how the web works. How APIs work, how the HTTP protocol works, how JS works, etc. I can quickly do things which other people think is impossible.

It’s funny because I often heard old school hackers talk about younger people who wanted the source code to fix problems while they just disassembled the binary and fixed it there. In the same spirit I see people today who say you can’t write code for some service because they don’t have an API. I just write my own.

When I think back I started writing bots without even using a url library. Everything was sockets and I wrote my HTTP requests by hand. The same for cookie or session handling. Probably, not very people will that do today but I have a great advantage because of this. I have no fear of diving into a new protocol because I know how to deal with sockets. I have no fear of services without an API because I know how to write one myself. Pretty cool.

pip destroys my memory

I spent about 4 hours today debugging pip which sucks up memory when using the outdated command. It’s pretty insane. In my test case with 8 med-sized packages it takes up 60mb just to see if any of them is outdated.

So I actually took a look at the debugging tool chain for Python. There are good built-in debugger called pdb which handles the basics very similar to gdb – as far as I can tell.

A cool feature is that you can write python code in the debugger and inject it into the running program. Which of course is more problematic with C binaries. So, I debugged the different steps look at the time it takes, look deeper into the functions and saw a lot of stuff which can cause the problem.

I still can’t see the main problem however I think it lies somewhere in caching websites. As far as I can see pip downloads all version of pages of a package and caches them. This could cause the problem.

Actually, while writing this article I thought that has to be an work-around. And actually there is a pretty easy one.

pip list works without problems and it lists all packages. We can remove the version numbers with sed and join all the files with tr. Now we have a list of all packages. If we run it through pip install -U we just try to upgrade all the packages.

pip install -U $(pip list | sed 's/(.*//' | tr "\\n" " ")

It works wonderfully. I think I don’t debug anymore and just create an alias.