I have made a frozen executable of the Blackboard Scraper for easy use on Mac OSX. Check it out here.
A little project I worked on for the last day was getting a program to make downloading a list of songs off youtube easier. Initially it was just going to be command line, import from a CSV file. But this only works when you know the first hit will be the correct song. So I decided to flesh it out into a GUI.
This was inspired by looking at the sexy lists on the Triple J Hottest 100 Wikipedia page and deciding there should be a way to grab all those songs easily.
Unfortunately, the Google API restricts this kind of thing. But I’m sick of this project now, so here it is. You’re limited to downloading about ten songs at a time, otherwise you get service abuse messages. Hopefully in the future I can find a better method of searching for songs.
I have finally gotten around to making the Blackboard Scraper stand alone so you no longer need to install lots of different things to get it working.
Hopefully this makes it easier for non-computing students to access and use. It still only works on Curtin’s blackboard system, however a UWA one is in the works.
Head to the Blackboard Scraper page to give it a whirl.
Uther Party is a custom mini-game map for the game Warcraft 3. Our local university LAN club has a weird obsession with it. Basically there is a box with a number on it, and the game is to not be holding the box when it lands on 0. You pass the box to the person next to you by pressing either Q, which decrements it by 1 or W which decrements it by 2. If the box is on 1 and you decrement it by 2, it explodes before you pass it.
The game is pretty frustrating, so I decided to make a script to tell me the optimal choice to make. The script works by generating a minmax tree of all possible choices. Each leaf has an array the size of the amount of players, which has a 1 in the field if the player doesn’t die in that playthrough or a 0 if they do. It then goes up the tree with each level of the tree corresponding to a different players turn which attempts to maximise their index in the array. If the two choices have the same chance of death, it takes the average of both children’s chances.
The solver works pretty well, however it assumes that the players aren’t colluding and are only looking to maximise their own score which is a fair assumption, but may not be the case 100% of the time.
You can download the solver here (it has prompt, command and GUI modes). It only requires python, but optionally can use ete2 to print out a graph of the tree if you are really sadistic.
If you want to try it out, I’ve also made a module for the ComSSA IRC bot to facilitate a text based game of mystery box.
So for reasons I won’t get into, I have a faulty main camera on my Samsung Galaxy S III.
It turns out Snapchat still allows me to take pictures and save them without crashing, due to it having front camera on by default. But I found myself needing a barcode scanner or QR Code scanner for 2-Factor authentication.
Most barcode scanner apps, which automatically boot into scanning mode will just crash straight away. I spent quite a while trying poorly written bar code scanners (even the one Google Authenticator suggests) which just crash if the back camera is broken.
Eventually I found a solution. QuickMark Barcode Scanner doesn’t crash right away and allows you to switch to your front camera. It has a pretty decent UI, and they also have a pretty good Windows app for scanning barcodes on your screen. Good job on the developers for handling erroneous situations gracefully.
Pong is a classic game, you could even say it is the classic game. I have been looking for things to help me learn Scratch recently, which is used to teach kids to code, as well as things to help me procrastinate exam study. So I decided to see if I could make the best damn Pong AI in Scratch that I could. This isn’t exactly simple, Scratch doesn’t really have “functions” like a regular programming language, so things get messy really quick. As Wikipedia says;
There is a strong contrast between the powerful multimedia functions and multi-threaded programming style and the rather limited scope of the Scratch programming language.
So before we start, let’s define the world and its parameters. I have just come fresh out of an AI unit which did not have nearly enough coding, so I am itching to actually apply my knowledge. We will start off with a PEAS definition:
- Performance: We want to minimize the number of balls which we miss, and maximize the number of balls which the opponent misses. AKA we want Max(Computer Score – Player Score).
- Environment: We are playing in a 480×360 playing field. The top and bottom are walls where the ball will bounce off and when the ball hits the sides that player loses. When hitting a wall, the ball’s Y vector is reflected across the X axis. When hitting a players paddle, the paddles velocity is added to the Y velocity (assuming the Y velocity of the ball isn’t the maximum) and then the remainder speed is the X velocity (going in the reverse direction). The ball is always going at a constant speed. Lets have a look at the environment characteristics, The world is:
- Fully Observable: All variables are available to the AI (Scratch hasn’t really caught on to Information Hiding principals)
- Deterministic: The only thing the AI cannot predict is the movement of the Player Paddle, everything it can figure out (there is no randomness)
- Episodic: After each paddle hit the AI can practically forget everything that just happened.
- Dynamic: The Paddles and the Ball are all constantly moving.
- Continuous: Because positions and velocities can go down to the decimal, the data is continuous, this isn’t a big deal though because it doesn’t actually affect the decisions much (you can just round).
- Multiple Agent: There are two agents, the Player (a person) and the Computer (the AI). They are competitive agents, one agent succeeding means the other agent fails.
- Actuators: We have two actuators in this game, the up accelerator which when on it increases velocity until it reaches the maximum and the down accelerator which decreases velocity until it reaches the negative maximum
- Sensors: We can sense the X and Y coordinates of both paddles and the ball. We can also sense the Y velocity of both paddles and the X and Y velocity of the ball.
I developed four different pong agents, each building on the lessons from the last one. I also updated and refined the world in which they interact. The first agent uses very hacky code such as bounce “when touching color red”. For a more complex AI to work well, we will need the game to be as deterministic as possible.
The Reflex Agents
Reflex agents are pretty simple. They read in sensor data and react to it. In our case my first agent will read in the position of the ball and if it is above, fire the up accelerator and if it is below fire the down accelerator. This is a very naive approach. It works well when the Y velocity of the ball is less than the maximum Y velocity of the paddle, but once it goes over, the paddle can’t cope. Furthermore, the paddle can’t just change directions, it must first decelerate. This means a ball with a high Y velocity will whiz past the paddle before it can turn around.
We can definitely do better than that. One issue is that the paddle starts following the ball too early and goes too far up or down to get back. So in the second agent, the paddle returns to the centre after hitting the ball and then only following the ball when it passes a certain point. This doesn’t really help it that much, and the steep Y moves still get the better of it. It looks smarter though.
The Model Based Agent
So it seems a bit stupid to have the paddle start moving upwards if the ball ends up below it. The thing is, we can figure out where the ball ends up using data gained from our “sensors”. Now the agent can just calculate the position the ball will hit based on its vector and move into position. This is almost perfect. I had to change the world around to keep the challenge on the agent. Now when the ball hits a paddle, its speed increases. This means the eventually the paddle won’t be able to get to it in time if it is too far away. I also cleaned up quite a bit of the code, relying more on variables and less on hit boxes to make it more consistent.
See if you can beat the agent. It’s interesting that the big issue for the first two agents, balls with high Y velocity, are a walk in the park for this agent. What this agent really struggles with is balls with a high X velocity aimed at its corners.
The Utility Based Agent
So now the AI is pretty good, but there is one problem. Right now the agent only plays defense, which makes it rely on the Player making a mistake. As the cheesy movie actors say, the best defense is a good offense. In order to allow a good offense, we want to design a utility based agent.
Utility based agents have a happiness function, which evaluates how happy a particular action will make the agent. The best offensive moves are moves that get the ball the furthest away from the other player with the highest X velocity, hopefully making it impossible for the Player to reach the ball on time. Note that actually hitting the ball isn’t a part of the happiness function – any plan which involves the AI missing the ball is immediately thrown out. Happiness is based on increasing our chances of winning and if we miss the ball the chance of winning is zero.
There are only 21 different velocities a paddle can hit the ball at, so to plan a move, we just generate all the states (assuming the ball would be able to be hit), test to see which will make the agent the happiest and then make a plan for the agent to follow. If the plan reaches a dead end, it finds the next happiest state. If it can’t find a state where it reaches the ball, it is quite likely the ball is too far away and going too fast. Having the paddle sit there without a plan looks a bit weird to a Player, they want to see it try and fail! So if it doesn’t find a state, it goes to the default state, which is moving as fast as possible toward the point where the ball is predicted to land. The agent would think this is futile, but it must appease the silly humans. And who knows, maybe a rounding error could mean it actually just makes it.
This agent is the most polished and challenging by far. I have also cleaned up the code some more, while simultaneously making it super dirty. Give it a go!
So that’s the best AI we have so far. If anyone has any comments on improving it (or if you found any bugs), or if you would like me to explain in more detail the algorithms used, leave a comment! When I have time, I plan on making it semi modular, so I can pit AIs against each other.
Sigh. If only we had this kind of programming integrated in our Artificial Machine Intelligence unit.
Understanding is not cued knowledge: performance is never the sum of drills; problems are not exercises; mastery is not achieved by the unthinking application of algorithms. – Wiggins, 1993
Now when I say We, I really mean Curtin University. I’m going to assume other universities teach in a similar way. To start off, let us have a look at the break down of some second and third year Computer Science (did I say Computer Science? Surely I mean Bachelor of Science (Science) majoring in Computing!) units at Curtin.
In this table, Tests and Exams are things where you have to sit for a certain amount of time with nothing but pen and paper and complete questions. Programming and Written Assessments include things like projects, programming tasks and reports, usually these things are mixed together as an ‘Assignment’.
|Unit||No. Tests||% Tests||No. Prog/Writ||% Prog/Writ|
Now if I was asked to rate these units on a combination of how effective I learned the unit outcomes, overall enjoyment and how much I remember the concepts to this day I would probably produce this list.
Now I know correlation doesn’t mean causation, so I’ll state it clearly.
I hate tests.
There are so many reasons why tests suck in computing that I just have to make a list.
1. It Is a Bad Test of Understanding
When designing computer programs, we usually judge the requirements on inputs and outputs. So if I input X into your program or function, it should output Y. We write test cases around this principal in order to see if the program does what it is supposed to. Unfortunately, people are not programs. When given a programming assignment, if I get given the test case, I can easily produce a program that outputs the solution in one line after calculating the solution manually and telling the program to print the solution. Unfortunately I would get zero marks after my tutor inspected the code.
So if simple input/outputs isn’t enough to test a student’s code, why should it be enough to test their knowledge of the concept. A graduate programmer will seldom be far from a computer able to produce any of the information that has been rote learned at university, so why do we focus so much on this technique?
2. It Does Not Help Students Learn
I can now hear the voices of all my lecturers at once:
“Tests aren’t for learning Jason! They’re for assessing!”
They sure are, Unnamed Lecturer. That’s why every unit ever has somewhere around half of the assessment marks as a formal, summative exam at the end of the semester, a time when everyone stays up late memorising every useless fact in their book in the hopes that they will recall an obscure fact which gives them a higher mark than their peers. Maybe, just maybe this will get them a higher grade so that Company Inc. will think they will be a better employee. This is so disconnected from reality I cannot fathom the reasons why we would want more of this type of assessment.
When studying for a test, what do students do? Normally, we would go through lecture slides, tutorials and past tests/examinations to see what topics are generally tested. We then repeatedly do practice questions (in the case of algorithms or calculations) or try to commit things to recall memory by writing notes and repetition. This is a good strategy to pass tests but this is not a good way to learn.
To contrast, a well structured assignment task will encourage students to go and research concepts and implement them (in the case of programming tasks) or write about them (in the case of reports/essays). While you can easily learn via rote in order to pass tests, implementing an algorithm requires a deeper understanding. The marker can then confirm this understanding by reading your implementation and comments around it. There is also a bonus, programming and to a smaller degree essay writing, has the rote learning of concepts built in. With both programming and writing, you inherently read and reread concepts over and over as you debug and edit your work.
3. There Is No Portfolio
When you complete a programming task, your result automatically goes into a portfolio of code you can publish as an example of your skills when joining the workforce. This is a bonus for people who are vocation oriented (read: at university just to get a job). While high marks always look attractive on a resume, employers will also be looking for experience in certain languages and fields of development. Saying “I did good in a test” is much less impressive than “I implemented an encryption protocol in C in two weeks”.
4. There Are No Goals
Goals are important. There are entire industries based around teaching people to set goals and achieve them. The current buzz around education and marketing (both which are weirdly linked) is gamification: the use of things like scores, points and achievements to help motivate people. Gamification, when used correctly, can increase user engagement and retention. A programming assessment, probably unknowingly, borrows many concepts from gamafication. Usually they will consist of a few different features worth a certain amount of marks (or points, if you see where I’m headed here). When a student completes a feature, they can test it using test input and once they get the correct output, they have “achieved” that feature.
The difference in these programming assessments which makes them almost automatically gamified compared to assignments in other degrees is the ability for instant gratification. A programmer knows when they have reached a milestone, because they can test each part compartmentally. Many Computer Science students tend to enjoy playing video games, so much so that a large chunk of the events our local CS club run are LAN’s. I don’t think this is a coincidence. Our teachers should acknowledge this connection and start designing assessment tasks with it in mind.
You Just Need to Study Harder, You’re an Adult! Formulate Your Own Learning Goals!
This is the response I expect to get from educators reading this. This is what I would expect they would think to themselves when they read my unit feedback (almost every one has been “Less tests, more assignments”). I reject this assumption completely.
University is not an accreditation factory, we don’t attend for the tests, we attend to learn. In this day and age of Khan Academy, Code Academy, Coursera and with all the fancy university offering free MOOCs (Massively Open Online Courses), the difference between learning online and attending a university has narrowed. Students expect that the university will not only make learning content available and test their summative knowledge in a 60 minute session a few times per semester. Students expect that their learning institution will assist them in setting achievable goals which are formative across the unit.
A good way to do that is more practical, programming assessments with theoretical reports/analysis. Giving students feedback through both automatic methods such as providing sample test input/output as well as feedback from instructors which goes beyond “this did not fit the marking guide, this was the answer” will improve student engagement, retention and results.
Lastly, the one issue with encouraging more practical assignments is the issue of cheating and ghost writing. This is the one thing exams are good for, and why they will always have their place at the end of a unit as the summative assessment for the entire semester.
Today was the last day of linux.conf.au :(. Arguably some of my favorite talks were today.
This is a last continuation of this post here about my first Linux.conf.au, here.
The Keynote today was Deploying software updates to ArduSat in orbit by Jonathan Oxer [ Video ]. Basically this was a project which got it’s funding from kickstarter which allows low-cost experiments to occur on arduinos on cube satellites in Lower Earth Orbit. This really was a the future is now type talk. Never before would you have thought regular people would have a chance to do anything with space other than look at it.
Raspberry Pi Hacks: Building Great Pi Projects by Ruth Suehle and Tom Callaway [ Video ] was a pretty light talk about some different projects the speakers and others had achieved with the raspberry pi. It’s actually convinced me to give the pi another shot. I bought one when they first came out and used one for a bit as a torrent server however I found it kinda sucked with stability but I think part of that now has to do with my power adapter (apparently they have to be 5v 1A regulated) and the fact it was the original model (apparently things have been fixed in the newer ones). They also had written a book on the pi for sale here (the discount code AUTHD gives you 40% off!)
The Rust language: memory, ownership and lifetimes by Nicholas Matsakis [ Video ] was an introduction to the new Rust language being developed by Mozilla. Now I’m not an expert on rust, but from the talk my impression is that it is C++ with some extra checks to avoid memory management issues. Basically you have an owner (like a variable/pointer) of a piece of memory that the owner can lend memory to others or transfer ownership. This prevents aliasing and means there doesn’t need to be garbage collection which worries about reference counting and other things. Obviously there are some other additions, but this is the one that was mainly emphasised. Rust sounds like an interesting language, I hate memory issues as much as the next guy. However, one issue I had with this talk was that programming languages were evaluated on this zero sum balancing act between safety and control. C++ gives you lots of control but sucks at safety. Haskell is very safe, you have basically no side effects but you don’t have much control or freedom which is why it isn’t used much. Python is pitched as being somewhere in the middle. Rust however is pitched at being simultaneously giving lots of control and lots of safety, which I feel like was extending the truth a bit. Rust gives safety through the ownership system which forbids dangerous things like aliasing and shared memory. Rust offers C++ like freedom by having unsafe blocks, which do allow these things. Clearly an unsafe block is not safe. So can a language offer high control and high safety at the same time? I’m unconvinced, but I haven’t used rust, so maybe somebody could comment on how it makes their programs more safe. It seems to me like Rust mostly just enforces a commenting policy of marking areas of code where memory management is messy. I do believe Rust has the potential, because of these rules, to improve code readability and debugging, but only compared to poorly documented code.
Pettycoin: Losing Tiny Amounts of Bitcoin At Scale! by Rusty Russell [ Video ] – I was looking forward to this talk. I’m a fan of the Bitcoin protocol so generally new ideas excite me, plus Rusty Russell is super nice to newcomers which is always great! Rusty also admitted the idea and implementation is in it’s infancy. Firstly, let me say I like that he is thinking out of the box and I am so glad there are people out there making things that aren’t more alt-coins. Stop making alt-coins people! Rusty talks about some good ideas. Sharding the network is pretty smart, so is sending out double spend alerts and shirking transaction size. However it is fundamentally flawed. The reason is Gateways. Bitcoin is supposed to be decentralized and gateways are centralised. It seems like the whole protocol relies on gateways and because of this I don’t see any advantage this would have over sending your bitcoins to a dedicated, centralised micro-payment service (like paypal lite or something). I would even argue a dedicated micro-payment service would be more secure as there is no risk of double spends, only traditional hacking.
Finally there were lighting talks at the end. Mostly used as an opportunity for people to spruke their open source project or group, these are usually hit and miss. I’m excited I discovered DLect after mostly giving up on my blackboard scraper project, it turns out somebody from University of Queensland has had the same idea but gotten a lot further. Hopefully I can get it working with Curtin. There were also a couple of talks on Bitcoin. Lightning talks are free as in free speech, so they’re sometimes not the greatest. Here is my quick guide if you’re interested in spreading the word of bitcoin.
Don’t talk about it like it’s an investment or stock
Don’t talk about it like it’s gone to make money (saving money (from fees) is OK)
Don’t be misleading by refering to thousands of % growth
Don’t talk about how it’s a “store of value”
Do talk about the lack of fees for transferring
Do talk about the decentralised nature of the protocol
Do talk about the safeguards against hacking (eg Proof of Work)
There tend to be two views on bitcoin, one is that it is a ponzi scheme and one that it is the future of money transfer. I think it’s both. There is no doubt that a lot of ‘early adopters’ will become very rich (or have done already) if bitcoin becomes mainstream, and many of them have become mouthpieces for bitcoin, but I think this does not detract from the theoretical qualities of bitcoin and that the protocol will still exist even when all the scheming has died down and the ponzi schemers have lost all their money.
So after that slightly divergent rant, LCA2014 is now at a close. LCA2015 was announced to be held in Auckland so maybe I’ll see everybody there next year! I’ve had a great time and I recommend any other student interested in Linux to take advantage of the cheap student entry.