Here is a quick algorithm puzzle that was asked during lecture.
Q: Suppose I have a data structure that is both a heap and a binary search tree. It stores N distinct elements. What is it?
A: Well, it must satisfy both the heap property (heaps) and the BST property. What are these properties?
heap property - all child elements are less than the parent element
BST property - every parent is greater than all of its subchildren on the left and less than all of its subchildren on the right.
So, how can we possibly support both of these properties in a simple, single data structure?
Easily, by creating a tree with only left children.
5
/ \
4
/ \
3
/ \
2
This is clearly both a heap and a tree.
Thursday, November 5, 2009
Tuesday, November 3, 2009
Stratego AI?
Have you ever played a capture the flag type board game such as Stratego?
current boardgame I have.
Well it may or may not be more fun than Risk. . . . It is a great game to feature as a mini game. Or perhaps make a huge 2player version.
Anyway, the AI that I always play against is horrible. I am wondering what is involved with creating a hard computer player? (That is, one with a high win %?...or one that is fast. What are the trade offs?)
Some things that I think an agent would need to do:
1) Create strong starting position (for example, don't accidentally trap key pieces) before game has even started.
2) Collect material. This comes in at least two parts:
a)Preserve your pieces. Don't risk killing valuable pieces if you are "not positive" that you will win. (This idea is called "fuzzy logic." Here is a great article from BYOND about using fuzzy logic in your game..
b)Capture when possible. Computing when exactly you should and should not capture may be difficult. It would involve the priority of each piece, and a few other things that are too much right now.
3 Save/analyze past states. Perhaps debatable. . . . Could an unbeatable agent be created if it were allowed to process the entire game? Is that fair for other players/agents?
current boardgame I have.Well it may or may not be more fun than Risk. . . . It is a great game to feature as a mini game. Or perhaps make a huge 2player version.
Anyway, the AI that I always play against is horrible. I am wondering what is involved with creating a hard computer player? (That is, one with a high win %?...or one that is fast. What are the trade offs?)
Some things that I think an agent would need to do:
1) Create strong starting position (for example, don't accidentally trap key pieces) before game has even started.
2) Collect material. This comes in at least two parts:
a)Preserve your pieces. Don't risk killing valuable pieces if you are "not positive" that you will win. (This idea is called "fuzzy logic." Here is a great article from BYOND about using fuzzy logic in your game..
b)Capture when possible. Computing when exactly you should and should not capture may be difficult. It would involve the priority of each piece, and a few other things that are too much right now.
3 Save/analyze past states. Perhaps debatable. . . . Could an unbeatable agent be created if it were allowed to process the entire game? Is that fair for other players/agents?
Monday, November 2, 2009
Internet friendships
One topic that I was recently talking to some friends about concerned online friendships. Some people had stories about onilne friends they had made over the years. These could be fellow web designers, like minded musicians, random game friendships...just random people you have ran into on the web and forged a friendship with.
Meeting people on the internet can be a challenge. . . . I find it easier in some ways, namely, that there can be as little element of prejudice as possible. Using the Internet, is it possible that we can remove all pre-judgment of perception?
Would removing all prejudice (both conscious and unconscious) even be a good context for meeting people? Or do judging people immediately (irl) protect us from the creepy old men.
Anyway, it is always interesting to discuss online friendships.
What can be gained from meeting people through online forums, games, chats, etc.?
Meeting people on the internet can be a challenge. . . . I find it easier in some ways, namely, that there can be as little element of prejudice as possible. Using the Internet, is it possible that we can remove all pre-judgment of perception?
Would removing all prejudice (both conscious and unconscious) even be a good context for meeting people? Or do judging people immediately (irl) protect us from the creepy old men.
Anyway, it is always interesting to discuss online friendships.
What can be gained from meeting people through online forums, games, chats, etc.?
hip hop hypocrites
Ah yeah, dear old hiphocrisy,
First dude I've heard use the explicit phrase, is right here.
But it is just a phrase for the same idea that other rappers have been spittin out. don't even neeed to call out the big names. Just the bullshit politics and hipocracy.
First dude I've heard use the explicit phrase, is right here.
But it is just a phrase for the same idea that other rappers have been spittin out. don't even neeed to call out the big names. Just the bullshit politics and hipocracy.
Sunday, November 1, 2009
splash page = bad
I have been interested in the idea of making the homepage immediately part of the game. New players would be taken directly to a sort of "Join the fight!" rah and "Click here to do this" crash tutorial. Returning players would be given game updates, personal news, new form/chat without having to log in.
For any players, I would have a quick "about this" message/SEO/ keyword section..but for a lot of games I think new people visiting the game want to be shown what it is.
Players might not get over the initial disappointment (mostly,need to build up trust right away).
Try to give new people seeing your game for the first time an honest impression of your game. That is, I wouldn't use a much better graphic and kickass appeal if
They don't necessarily want or need to be taken immediately into a detailed description of the game setting. Instead, show them what is currently going on in the game world. What are people/agents doing right now? What is the big forum event that everyone is talking about? Yes, I'm sure you have a great history of the game world and story you want to cram down my throat, but I will get to the details when I am good and ready!
For any players, I would have a quick "about this" message/SEO/ keyword section..but for a lot of games I think new people visiting the game want to be shown what it is.
Players might not get over the initial disappointment (mostly,need to build up trust right away).
Try to give new people seeing your game for the first time an honest impression of your game. That is, I wouldn't use a much better graphic and kickass appeal if
They don't necessarily want or need to be taken immediately into a detailed description of the game setting. Instead, show them what is currently going on in the game world. What are people/agents doing right now? What is the big forum event that everyone is talking about? Yes, I'm sure you have a great history of the game world and story you want to cram down my throat, but I will get to the details when I am good and ready!
Sunday, October 25, 2009
tabs tonight, thoughts on searching
Just had to start it off with YouTube - Paris - Martial Law, which had to rewind.
After more Paris I was just too indifferent. Made a few chess moves and what do you know, I'm struggling with google.
It was when trying to find an online chess game analysis application. I am sure this tool is available...what is interesting is that I was getting pretty irrelevant results for my initial search queries because the words were just too "general." Often, words had more than one meaning.
Eventually, I was able to narrow down on the idea.
Is there an algorithm, i wonder, for this "narrowing down" process? And if there is, I want to be able to click my way to the exact idea I am thinking of?
Predict my mind...bing. lolol bing doens't do this, does it?
Perhaps more added later...I ended up on a sourceforge page looking for a java chess jar to throw into Eclipse.
As always, everytthing stopped for some fast paced backgammon games. lots of doubles..much more of a race this time. so fun :)
After more Paris I was just too indifferent. Made a few chess moves and what do you know, I'm struggling with google.
It was when trying to find an online chess game analysis application. I am sure this tool is available...what is interesting is that I was getting pretty irrelevant results for my initial search queries because the words were just too "general." Often, words had more than one meaning.
Eventually, I was able to narrow down on the idea.
Is there an algorithm, i wonder, for this "narrowing down" process? And if there is, I want to be able to click my way to the exact idea I am thinking of?
Predict my mind...bing. lolol bing doens't do this, does it?
Perhaps more added later...I ended up on a sourceforge page looking for a java chess jar to throw into Eclipse.
As always, everytthing stopped for some fast paced backgammon games. lots of doubles..much more of a race this time. so fun :)
Monday, October 19, 2009
chess pieces automatically record PGN
Would it be possible to put some sort of sensor inside plastic chess pieces that record the movement? Or perhaps a board that detects the piece movements (but inside the pieces would be better.) After a game (or during) we could scan the PGN into the computer?
This would be great for people like me that would like to record the games but is not going to carry around a notebook.
This would be great for people like me that would like to record the games but is not going to carry around a notebook.
macros
One thing that is important as players and developers is to build smart macros. (Macros are those external programs that automatically perform certain actions. These can be things such as typing URLs, clicking locations on screen, or a script that sends HTTP requests to the game server.)
Building smart macros is sometimes difficult to do. As of late, I have been using a screen clicker (auto hot key). Sometimes you need to combine the screen clicker with a seperate page...hide any and all logic behind a browser page. (For example, have your screen clicker copy data, paste into a PHP page, then copy the resulting URL or HTTP forward and use that to advance the game page.)
There are many uses for such macro programs. First, I will discuss why this is good for players. Obviously, a player with a good macro program will be able to advance rather quickly. (This may be an over statement of course. However, lets just assume that the macro is as efficient as possible.) This can give players a competitive edge, reward smart players with high status, etc.
This is pretty obvious, and is why macro and script users are not very well liked in many communities. But, is there really anything wrong with a macro user?
To answer this question, lets now look at why macro programs are good for PBBG/online game developers. Lets say that you have built a very efficient macro for your game. (Ideally, this macro would be a built in set of commands executed by the game, or a cron script, etc. that allow you to perform any in game action.)
With your macro, you will be able to:
-balance out game statistics (ex: after running the macro you find realize you need to recaculate how long it takes to level)
-compare to the top players performance (discover if players have found loopholes in your game play)
-detect cheating (if a players activity sets off the same internal flags that the macro you built does...perhaps that player is using their own!)
As we see, there are many reasons to for PBBG develpers to create their own game macros. However, when it comes to players using macros, I think the best policy is to remove the advantage, jail the player, and update your defenses.
Also, consider taking the macro and integrating it into an "offial game macro" that you sell to players (either as a gold sink or to make real cash.)
OF course...., try to build games that cannot be macro'd. However, I understand that we all need to build a space mining game once.
Building smart macros is sometimes difficult to do. As of late, I have been using a screen clicker (auto hot key). Sometimes you need to combine the screen clicker with a seperate page...hide any and all logic behind a browser page. (For example, have your screen clicker copy data, paste into a PHP page, then copy the resulting URL or HTTP forward and use that to advance the game page.)
There are many uses for such macro programs. First, I will discuss why this is good for players. Obviously, a player with a good macro program will be able to advance rather quickly. (This may be an over statement of course. However, lets just assume that the macro is as efficient as possible.) This can give players a competitive edge, reward smart players with high status, etc.
This is pretty obvious, and is why macro and script users are not very well liked in many communities. But, is there really anything wrong with a macro user?
To answer this question, lets now look at why macro programs are good for PBBG/online game developers. Lets say that you have built a very efficient macro for your game. (Ideally, this macro would be a built in set of commands executed by the game, or a cron script, etc. that allow you to perform any in game action.)
With your macro, you will be able to:
-balance out game statistics (ex: after running the macro you find realize you need to recaculate how long it takes to level)
-compare to the top players performance (discover if players have found loopholes in your game play)
-detect cheating (if a players activity sets off the same internal flags that the macro you built does...perhaps that player is using their own!)
As we see, there are many reasons to for PBBG develpers to create their own game macros. However, when it comes to players using macros, I think the best policy is to remove the advantage, jail the player, and update your defenses.
Also, consider taking the macro and integrating it into an "offial game macro" that you sell to players (either as a gold sink or to make real cash.)
OF course...., try to build games that cannot be macro'd. However, I understand that we all need to build a space mining game once.
Sunday, October 18, 2009
Somewhere on the web, I replied to a topic suggesting that a PBBG developer create an in game political model based on "real life." Her game had something to do with players mining/farming/fighting for land, all while working for some other "Lord" player...these players were powerful ones that either were elected, or bought their way into power, etc.
Regardless, the developer wanted to create a political atmosphere. After some discussion, I think the best ways to go about this boiled down to:
1) Assembling a team of story writers
2) Polling players for their RL political ideas
1)Writing the Political Agenda
The idea behind this is that the policial arena is realized through the use of stories. These can be created by the developer, or a team of writers, or from the community itself. This is nice because you have somewhat control over the game. If you are talented, an entire history can be created...I have seen this done in a few games(link here) and it turns out pretty nice...if you expect your players to also become readers.
One thing that I dislike about this idea is that (besides the time or money that would need to be invested) is that there may not be much input from the community. This is not a big deal to some developers...but I think for this case at least, it would be difficult to create a real thriving poltical climate. (The vision here is not well understood.)
2)History Writes Itself
jk.
The idea that I had was to poll users. By asking questions designed to capture political ideas, we could build a basic profile of the players. This profile could then be used to put certain groups of users together for gaming expereince, help users to find others like them in the chat/forum/portal, or deliver targeted ads...or anything else.
You also have the option of making the data private or public...by keeping it private you could group users together and watch the reactions. This may be ethically disagreeable (I have no idea) but could be used for research as well.
One issue is, How to poll users? How do we optain this data on their political ideologies? Well, if you have every played one of those political games (like Nation States), you will have some idea. In these games, players are presented with a question and a yes/no/ignore answer. The engine then updates various "stats" about the nation. This type of model could easily be adapted but would take a while to set up. (Would need to obtain questions, answers, algorithm, then shorten the questions and rewrite them to your game setting.)
What are some other good ways to obtain this type of personal data from the user? Of course there are gaming considerations that are relevant to each individual, but I am thinking that there has got to be some discrete, clever ways of collecting this information.
Searching chat and forums for key words, writing a spider that updates a users political stats as it reads...these are interesting ways. For many game communities, I think players would think of these tactics as highly unethical. That's not the kind of idea that I am talking about, or that the OP had in mind. However, if players knew about this type of data collection (anonymous, private, trusted), there are many intersting things we as developers could do with it.
Regardless, the developer wanted to create a political atmosphere. After some discussion, I think the best ways to go about this boiled down to:
1) Assembling a team of story writers
2) Polling players for their RL political ideas
1)Writing the Political Agenda
The idea behind this is that the policial arena is realized through the use of stories. These can be created by the developer, or a team of writers, or from the community itself. This is nice because you have somewhat control over the game. If you are talented, an entire history can be created...I have seen this done in a few games(link here) and it turns out pretty nice...if you expect your players to also become readers.
One thing that I dislike about this idea is that (besides the time or money that would need to be invested) is that there may not be much input from the community. This is not a big deal to some developers...but I think for this case at least, it would be difficult to create a real thriving poltical climate. (The vision here is not well understood.)
2)History Writes Itself
jk.
The idea that I had was to poll users. By asking questions designed to capture political ideas, we could build a basic profile of the players. This profile could then be used to put certain groups of users together for gaming expereince, help users to find others like them in the chat/forum/portal, or deliver targeted ads...or anything else.
You also have the option of making the data private or public...by keeping it private you could group users together and watch the reactions. This may be ethically disagreeable (I have no idea) but could be used for research as well.
One issue is, How to poll users? How do we optain this data on their political ideologies? Well, if you have every played one of those political games (like Nation States), you will have some idea. In these games, players are presented with a question and a yes/no/ignore answer. The engine then updates various "stats" about the nation. This type of model could easily be adapted but would take a while to set up. (Would need to obtain questions, answers, algorithm, then shorten the questions and rewrite them to your game setting.)
What are some other good ways to obtain this type of personal data from the user? Of course there are gaming considerations that are relevant to each individual, but I am thinking that there has got to be some discrete, clever ways of collecting this information.
Searching chat and forums for key words, writing a spider that updates a users political stats as it reads...these are interesting ways. For many game communities, I think players would think of these tactics as highly unethical. That's not the kind of idea that I am talking about, or that the OP had in mind. However, if players knew about this type of data collection (anonymous, private, trusted), there are many intersting things we as developers could do with it.
Thursday, October 8, 2009
Free Game Reviews
If you are a developer with a PBBG (or other online game) that is looking for some constructive criticism, please post here with an intro to your game and what kind of advice you are looking for.
I have been playing, designing, and discussing web games for a number of years. I don't claim to be an expert...I am only a fellow developer that is looking to help make your game better. However, I have seen and been a part of many different web games overs the years, and I think that I can offer many people help and insight.
Anyway, what is there to lose?
I have been playing, designing, and discussing web games for a number of years. I don't claim to be an expert...I am only a fellow developer that is looking to help make your game better. However, I have seen and been a part of many different web games overs the years, and I think that I can offer many people help and insight.
Anyway, what is there to lose?
Welcome
Welcome to a cool, stimulating, late night blog where I discuss many different things related to online browser games (PBBGs). I would like to discuss trends and ideas in pbbgs, new and interesting development ideas, and theory and philosophy behind PBBGs and other social networking tools.
This blog will at times be technical, others philosophical, and stil others a mystery. I am always interested in discussing social networking.
I am a college student at times very busy, but I hope to at least keep updated on certain games, etc. I would like to start reviewing different PBBGs, based on different criteria than the standard "graphics look nice, lots of different armor options, etc."
I hope to create an atmosphere open to discussion. I lurk at a few different forums and am active on a few others...so at times there may be cross over posts (haha.) but I welcome anyone and everyone to just leave a comment. It doesn't matter if the discussion was a few months ago or if you are responding to an impulse. Any and all discussion is welcomed on the subjects of PBBGs, game theory, social networking, and game reviews. (Developers, please feel free to comment with a link to your blog or forum.)
Mike
Also, as an after thought, I reserve the right to post hip hop videos and chess articles. Which will probably happen more than I expect...
This blog will at times be technical, others philosophical, and stil others a mystery. I am always interested in discussing social networking.
I am a college student at times very busy, but I hope to at least keep updated on certain games, etc. I would like to start reviewing different PBBGs, based on different criteria than the standard "graphics look nice, lots of different armor options, etc."
I hope to create an atmosphere open to discussion. I lurk at a few different forums and am active on a few others...so at times there may be cross over posts (haha.) but I welcome anyone and everyone to just leave a comment. It doesn't matter if the discussion was a few months ago or if you are responding to an impulse. Any and all discussion is welcomed on the subjects of PBBGs, game theory, social networking, and game reviews. (Developers, please feel free to comment with a link to your blog or forum.)
Mike
Also, as an after thought, I reserve the right to post hip hop videos and chess articles. Which will probably happen more than I expect...
Subscribe to:
Posts (Atom)